Covering oriented points in the plane with orthogonal polygons is NP-complete

DOI10.1016/j.endm.2010.05.039zbMath1237.90272OpenAlexW1989582986MaRDI QIDQ2883577

Brahim Hnich, Cem Evrendilek, Burkay Genç

Publication date: 13 May 2012

Published in: Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.endm.2010.05.039

zbMATH Keywords

coveringNP-completecomputational geometryorthogonal polygon

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)

Related Items

Covering points with minimum/maximum area orthogonally convex polygons ⋮ A polygon is determined by its angles ⋮ Covering points with orthogonal polygons ⋮ Reconstructing polygons from scanner data

Cites Work

• Unnamed Item
• Reconstructing orthogonal polyhedra from putative vertex sets
• The complexity of detecting crossingfree configurations in the plane

This page was built for publication: Covering oriented points in the plane with orthogonal polygons is NP-complete