Orthogonal segment stabbing

DOI10.1016/j.comgeo.2004.07.002zbMath1162.68751OpenAlexW2032825554MaRDI QIDQ705557

Yuval Nir, Joseph S. B. Mitchell, Matthew J. Katz

Publication date: 31 January 2005

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.comgeo.2004.07.002

zbMATH Keywords

Dynamic programmingNP-completenessOptimizationCoveringLine segmentsRaysStabbing

Mathematics Subject Classification ID

Dynamic programming (90C39) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (11)

On dominating set of some subclasses of string graphs ⋮ Geometric hitting set, set cover and generalized class cover problems with half-strips in opposite directions ⋮ Cooperative mobile guards in grids ⋮ Complexity and approximation for discriminating and identifying code problems in geometric setups ⋮ The parameterized complexity of stabbing rectangles ⋮ On Guarding Orthogonal Polygons with Sliding Cameras ⋮ Guarding orthogonal art galleries with sliding \(k\)-transmitters: hardness and approximation ⋮ Recognition and drawing of stick graphs ⋮ Grid intersection graphs and order dimension ⋮ Graphs with equal domination and covering numbers ⋮ Red-blue covering problems and the consecutive ones property

Cites Work

• Unnamed Item
• Unnamed Item
• Minimum-link watchman tours
• Optimal packing and covering in the plane are NP-complete
• On grid intersection graphs
• Some simplified NP-complete graph problems
• A left-first search algorithm for planar graphs
• An Algorithmic Approach to Network Location Problems. I: Thep-Centers
• Visibility preserving terrain simplification

This page was built for publication: Orthogonal segment stabbing