Abstract | ||
---|---|---|
Let $P$ be a set of $n$ colored points in the plane. Introduced by Hart (1968), a consistent subset of $P$, is a set $Ssubseteq P$ such that for every point $p$ in $Psetminus S$, the closest point of $p$ in $S$ has the same color as $p$. The consistent subset problem is to find a consistent subset of $P$ with minimum cardinality. This problem is known to be NP-complete even for two-colored point sets. Since the initial presentation of this problem, aside from the hardness results, there has not been a significant progress from the algorithmic point of view. In this paper we present the following algorithmic results: 1. The first subexponential-time algorithm for the consistent subset problem. 2. An $O(nlog n)$-time algorithm that finds a consistent subset of size two in two-colored point sets (if such a subset exists). Towards our proof of this running time we present a deterministic $O(n log n)$-time algorithm for computing a variant of the compact Voronoi diagram; this improves the previously claimed expected running time. 3. An $O(nlog^2 n)$-time algorithm that finds a minimum consistent subset in two-colored point sets where one color class contains exactly one point; this improves the previous best known $O(n^2)$ running time which is due to Wilfong (SoCG 1991). 4. An $O(n)$-time algorithm for the consistent subset problem on collinear points; this improves the previous best known $O(n^2)$ running time. 5. A non-trivial $O(n^6)$-time dynamic programming algorithm for the consistent subset problem on points arranged on two parallel lines. To obtain these results, we combine tools from planar separators, additively-weighted Voronoi diagrams with respect to convex distance functions, point location in farthest-point Voronoi diagrams, range trees, paraboloid lifting, minimum covering of a circle with arcs, and several geometric transformations. |
Year | Venue | Field |
---|---|---|
2018 | arXiv: Computational Geometry | Discrete mathematics,Dynamic programming,Binary logarithm,Combinatorics,Point location,Transformation geometry,Cardinality,Regular polygon,Parallel,Voronoi diagram,Mathematics |
DocType | Volume | Citations |
Journal | abs/1810.09232 | 0 |
PageRank | References | Authors |
0.34 | 0 | 7 |
Name | Order | Citations | PageRank |
---|---|---|---|
Ahmad Biniaz | 1 | 44 | 20.67 |
Sergio Cabello | 2 | 33 | 4.91 |
Anil Maheshwari | 3 | 869 | 104.47 |
Paz Carmi | 4 | 321 | 43.14 |
Saeed Mehrabi | 5 | 0 | 3.38 |
Jean-Lou De Carufel | 6 | 76 | 22.63 |
Michiel H. M. Smid | 7 | 550 | 93.58 |