The complexity of separating points in the plane

DOI10.1007/s00453-014-9965-6zbMath1332.68066OpenAlexW2010762400MaRDI QIDQ262254

Panos Giannopoulos, Sergio Cabello

Publication date: 29 March 2016

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: http://openaccess.city.ac.uk/id/eprint/21509/1/Accepted.pdf

zbMATH Keywords

NP-hardness3-paths propertyconnected curvespoint separation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (3)

Two optimization problems for unit disks ⋮ On the complexity of barrier resilience for fat regions and bounded ply ⋮ On the shortest separating cycle

Cites Work

• Unnamed Item
• Embeddings of graphs with no short noncontractible cycles
• On Isolating Points Using Disks
• Terrain Guarding is NP-Hard
• Minimum Cell Connection in Line Segment Arrangements
• Minimum-weight triangulation is NP-hard
• Planar Formulae and Their Uses
• The Problem of Compatible Representatives
• Surface Approximation and Geometric Partitions
• Planar Embeddings of Graphs with Specified Edge Lengths
• Finding shortest non-trivial cycles in directed graphs on surfaces

This page was built for publication: The complexity of separating points in the plane