Covering points with orthogonal polygons

DOI10.1016/J.DAM.2012.01.018MaRDI QIDQ496708zbMATH OpenOpenAlexFDO

Authors Cem Evrendilek, Burkay Genç, Brahim Hnich

Publication date 22 September 2015

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2012.01.018

zbMATH Keywords

NP-completenesscoveringorthogonal polygon

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial aspects of finite geometries (05B25) Polytopes and polyhedra (52B99) Packing and covering in (2) dimensions (aspects of discrete geometry) (52C15)

Recommendations

• Covering oriented points in the plane with orthogonal polygons is NP-complete
• Covering points with orthogonally convex polygons
• Covering points with minimum/maximum area orthogonally convex polygons
• Covering Polygons Is Hard
• Covering Orthogonal Polygons with Non-Piercing Rectangles

Cites work

• scientific article; zbMATH DE number 4062601 (Why is no real title available?)
• Connected Rectilinear Graphs on Point Sets
• Covering oriented points in the plane with orthogonal polygons is NP-complete
• Covering points with orthogonally convex polygons
• On the definition and computation of rectilinear convex hulls
• Reconstructing orthogonal polyhedra from putative vertex sets
• The complexity of detecting crossingfree configurations in the plane

Cited in

(7)

• On point covers of \(c-\)oriented polygons
• Covering orthogonal polygons with star polygons: The perfect graph approach
• Covering points with minimum/maximum area orthogonally convex polygons
• Covering points with orthogonally convex polygons
• Orthogonally convex covering of orthogonal polygons without holes
• Covering oriented points in the plane with orthogonal polygons is NP-complete
• Covering a set of points in a plane using two parallel rectangles

This page was built for publication: Covering points with orthogonal polygons

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