Journal of Computer Science and Technology
Quick Search in JCST
 Advanced Search 
      Home | PrePrint | SiteMap | Contact Us | FAQ
Indexed by   SCIE, EI ...
Bimonthly    Since 1986
Journal of Computer Science and Technology 2014, Vol. 29 Issue (5) :879-886    DOI: s11390-014-1475-0
Theory and Algorithms Current Issue | Archive | Adv Search << Previous Articles | Next Articles >>
On some proximity problems of colored sets
Cheng-Lin Fan1(范成林), Jun Luo1,2,*(罗 军), Wen-Cheng Wang3(王文成), Member, ACM, IEEE, Fa-Rong Zhong4(钟发荣), Binhai Zhu5(朱滨海), Member, ACM
1. Shenzhen Institutes of Advanced Technology, Chinese Academy of Sciences, Shenzhen 518055, China;
2. Huawei Noah's Ark Laboratory, Shatin, Hong Kong, China;
3. State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing 100190, China;
4. College of Mathematics, Physics and Information Technology, Zhejiang Normal University, Jinhua 321004, China;
5. Department of Computer Science, Montana State University, Bozeman, MT 59717, U. S. A.

Related Articles
Download: [PDF 6608KB]     Export: BibTeX or EndNote (RIS)  
Abstract 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.
Articles by authors
Cheng-Lin Fan
Jun Luo
Wen-Cheng Wang
Fa-Rong Zhong
Binhai Zhu
KeywordsComputational Geometry   Colored Sets   Algorithms     
Received 2014-01-15;

This research was supported by the International Science and Technology Cooperation Program of China under Grant No. 2010DFA92720, and the National Natural Science Foundation of China under Grant Nos. 11271351, 60928006, and 61379087.

About author: Cheng-Lin Fan is an assistant researcher in Shenzhen Institutes of Advanced Technology, Chinese Academy of Sciences. He received his M.S. degree in computer science and technology from Central South University, Changsha, in 2011. His research interests are in algorithm design and analysis, and computational geometry.
Cite this article:   
Cheng-Lin Fan, Jun Luo, Wen-Cheng Wang, Fa-Rong Zhong, Binhai Zhu.On some proximity problems of colored sets[J]  Journal of Computer Science and Technology, 2014,V29(5): 879-886
Copyright 2010 by Journal of Computer Science and Technology