计算机科学技术学报（英文版）
計算機科學技術學報（英文版）
계산궤과학기술학보（영문판）
JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY
2014年
5期
879-886
,共8页
范成林%罗军%王文成%钟发荣%朱滨海
範成林%囉軍%王文成%鐘髮榮%硃濱海
범성림%라군%왕문성%종발영%주빈해
computational geometry%colored set%algorithm%maximum diameter color-spanning set problem
The maximum diameter color-spanning set problem (MaxDCS) is defined as follows: given n points with m colors, select m points with m distinct colors such that the diameter of the set of chosen points is maximized. In this paper, we design an optimal O(n log n) time algorithm using rotating calipers for MaxDCS in the plane. Our algorithm can also be used to solve the maximum diameter problem of imprecise points modeled as polygons. We also give an optimal algorithm for the all farthest foreign neighbor problem (AFFN) in the plane, and propose algorithms to answer the farthest foreign neighbor query (FFNQ) of colored sets in two- and three-dimensional space. Furthermore, we study the problem of computing the closest pair of color-spanning set (CPCS) in d-dimensional space, and remove the log m factor in the best known time bound if d is a constant.
