The complexity of separating points in the plane

DOI10.1007/S00453-014-9965-6MaRDI QIDQ262254zbMATH OpenOpenAlexFDO

Authors S. Cabello, Panos Giannopoulos

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

3-paths propertyconnected curvesNP-hardnesspoint separation

Mathematics Subject Classification ID

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

Recommendations

• The complexity of separating points in the plane
• The complexity of computing minimum separating polygons
• scientific article; zbMATH DE number 742976
• Separating point sets in polygonal environments
• SEPARATING POINT SETS IN POLYGONAL ENVIRONMENTS

Cites work

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

Cited in

(7)

• The complexity of computing minimum separating polygons
• On the shortest separating cycle
• Two optimization problems for unit disks
• The complexity of separating points in the plane
• The complexity of point configurations
• The shortest separating cycle problem
• On the complexity of barrier resilience for fat regions and bounded ply

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q262254)