[1810.09232] On The Minimum Consistent Subset Problem - ArXiv

Computer Science > Computational Geometry arXiv:1810.09232 (cs) [Submitted on 22 Oct 2018 (v1), last revised 26 Nov 2018 (this version, v2)] Title:On the Minimum Consistent Subset Problem Authors:Ahmad Biniaz, Sergio Cabello, Paz Carmi, Jean-Lou De Carufel, Anil Maheshwari, Saeed Mehrabi, Michiel Smid View a PDF of the paper titled On the Minimum Consistent Subset Problem, by Ahmad Biniaz and 6 other authors View PDF

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 $S\subseteq P$ such that for every point $p$ in $P\setminus 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(n\log 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(n\log^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.

Comments:	24 pages
Subjects:	Computational Geometry (cs.CG)
Cite as:	arXiv:1810.09232 [cs.CG]
(or arXiv:1810.09232v2 [cs.CG] for this version)
https://doi.org/10.48550/arXiv.1810.09232 Focus to learn more arXiv-issued DOI via DataCite

Submission history

From: Ahmad Biniaz [view email] [v1] Mon, 22 Oct 2018 13:10:05 UTC (996 KB) [v2] Mon, 26 Nov 2018 14:19:04 UTC (997 KB) Full-text links:

Access Paper:

View a PDF of the paper titled On the Minimum Consistent Subset Problem, by Ahmad Biniaz and 6 other authors
• View PDF
• TeX Source

view license Current browse context: cs.CG < prev | next > new | recent | 2018-10 Change to browse by: cs

References & Citations

• NASA ADS
• Google Scholar
• Semantic Scholar

DBLP - CS Bibliography

listing | bibtex Ahmad BiniazSergio CabelloAnil MaheshwariPaz CarmiSaeed Mehrabi … export BibTeX citation

BibTeX formatted citation

× loading... Data provided by:

Bookmark

Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Code, Data and Media Associated with this Article alphaXiv Toggle alphaXiv (What is alphaXiv?) Links to Code Toggle CatalyzeX Code Finder for Papers (What is CatalyzeX?) DagsHub Toggle DagsHub (What is DagsHub?) GotitPub Toggle Gotit.pub (What is GotitPub?) Huggingface Toggle Hugging Face (What is Huggingface?) Links to Code Toggle Papers with Code (What is Papers with Code?) ScienceCast Toggle ScienceCast (What is ScienceCast?) Demos Demos Replicate Toggle Replicate (What is Replicate?) Spaces Toggle Hugging Face Spaces (What is Spaces?) Spaces Toggle TXYZ.AI (What is TXYZ.AI?) Related Papers Recommenders and Search Tools Link to Influence Flower Influence Flower (What are Influence Flowers?) Core recommender toggle CORE Recommender (What is CORE?)

• Author
• Venue
• Institution
• Topic

About arXivLabs arXivLabs: experimental projects with community collaborators

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.

Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)