On the minimum consistent subset problem

DOI10.1007/s00453-021-00825-8OpenAlexW4206558651MaRDI QIDQ5918312

Anil Maheshwari, Ahmad Biniaz, Jean-Lou De Carufel, Michiel H. M. Smid, Sergio Cabello, Paz Carmi, Saeed Mehrabi

Publication date: 30 June 2021

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1810.09232

zbMATH Keywords

point locationplanar separatorsrange treesconsistent subsetadditively-weighted Voronoi diagramsfarthest-point Voronoi diagramsparaboloid lifting

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Data structures (68P05)

Related Items

Minimum consistent subset of simple graph classes

Cites Work

• Unnamed Item
• Finding small simple cycle separators for 2-connected planar graphs
• The slab dividing approach to solve the Euclidean \(P\)-center problem
• A compact piecewise-linear Voronoi diagram for convex sites in the plane
• Algorithms and hardness results for nearest neighbor problems in bicolored point sets
• Consistent subset problem with two labels
• NEAREST NEIGHBOR PROBLEMS
• Computation of Non-dominated Points Using Compact Voronoi Diagrams
• Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams
• Linear Programming in Linear Time When the Dimension Is Fixed
• An algorithm for a selective nearest neighbor decision rule (Corresp.)
• OPTIMAL BINARY SPACE PARTITIONS FOR SEGMENTS IN THE PLANE
• Near-Optimal Sample Compression for Nearest Neighbors