|
|||||
|
|
On some geometric problems of color-spanning sets |
|
| Authors: | Wenqi Ju Chenglin Fan Jun Luo Binhai Zhu Ovidiu Daescu |
| Institution: | 1. Institute of Computing Technology, Chinese Academy of Sciences, Beijing, China 2. Graduate University of the Chinese Academy of Sciences, Beijing, China 3. Shenzhen Institutes of Advanced Technology, Chinese Academy of Sciences, Shenzhen, China 4. Department of Computer Science, Montana State University, Bozeman, MT, USA 5. Department of Computer Science, University of Texas at Dallas, Dallas, TX, USA |
| Abstract: | In this paper we study several geometric problems of color-spanning sets: given n points with m colors in the plane, selecting m points with m distinct colors such that some geometric properties of the m selected points are minimized or maximized. The geometric properties studied in this paper are the maximum diameter, the largest closest pair, the planar smallest minimum spanning tree, the planar largest minimum spanning tree and the planar smallest perimeter convex hull. We propose an O(n 1+ε ) time algorithm for the maximum diameter color-spanning set problem where ε could be an arbitrarily small positive constant. Then, we present hardness proofs for the other problems and propose two efficient constant factor approximation algorithms for the planar smallest perimeter color-spanning convex hull problem. |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ | |