The complexity of separating points in the plane

DOI10.1145/2462356.2462383zbMath1305.68099OpenAlexW1981830579MaRDI QIDQ5174498

Panos Giannopoulos, Sergio Cabello

Publication date: 17 February 2015

Published in: Proceedings of the twenty-ninth annual symposium on Computational geometry (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-path-condition1-barrierfundamental cycle methodpoints 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 (2)

Semi-dynamic Connectivity in the Plane ⋮ Approximation algorithms for the geometric firefighter and budget fence problems

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