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

DOI10.1016/J.ENDM.2010.05.039zbMATH Open1237.90272OpenAlexW1989582986MaRDI QIDQ2883577FDOQ2883577

Authors: Cem Evrendilek, Burkay Genç, Brahim Hnich 

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

Recommendations

• Covering points with orthogonal polygons
• Covering Polygons Is Hard
• Further NP-hard problems for minimal polygon coverings
• Covering points with orthogonally convex polygons
• scientific article; zbMATH DE number 975343

zbMATH Keywords

computational geometrycoveringNP-completeorthogonal polygon

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Reconstructing orthogonal polyhedra from putative vertex sets
• The complexity of detecting crossingfree configurations in the plane

Cited In (6)

• Covering points with minimum/maximum area orthogonally convex polygons
• A polygon is determined by its angles
• Covering points with orthogonal polygons
• Covering points with orthogonally convex polygons
• Reconstructing polygons from scanner data
• Title not available (Why is that?)

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

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