On some geometric problems of color-spanning sets
On some geometric problems of color-spanning sets
复制标题
DOI：
10.1007/s10878-012-9458-y
复制
发表时间：
2011-05
影响因子：
1
通讯作者：
Wenqi Ju;Chenglin Fan;Jun Luo;B. Zhu;O. Daescu
中科院分区：
文献类型：
--
作者：
Wenqi Ju;Chenglin Fan;Jun Luo;B. Zhu;O. Daescu
本文研究了色生成集的几个几何问题：给定平面上m个点，选择m个不同颜色的点，使它们的某些几何性质最小化或最大化。本文研究的几何性质是最大直径、最大最近对、平面最小最小生成树、平面最大最小生成树和平面最小周长凸船体。本文提出了一个求解最大直径色生成集问题的O（n1+ε）时间算法，其中ε可以是任意小的正常数.然后，我们给出了其他问题的困难证明，并提出了两个有效的常数因子近似算法的平面最小周长的颜色跨越凸船体问题。
In this paper we study several geometric problems of color-spanning sets: givennpoints withmcolors in the plane, selectingmpoints withmdistinct colors such that some geometric properties of themselected 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 anO(n1+ε) 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.