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

DOI10.1016/J.ENDM.2010.05.039MaRDI QIDQ2883577zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

computational geometrycoveringNP-completeorthogonal polygon

Mathematics Subject Classification ID

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

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

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• 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
• scientific article; zbMATH DE number 3903967 (Why is no real title available?)

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)