Computing conforming partitions of orthogonal polygons with minimum stabbing number

DOI10.1016/j.tcs.2017.05.035zbMath1372.68264MaRDI QIDQ2402271

Saeed Mehrabi, Stephane Durocher

Publication date: 7 September 2017

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2017.05.035

zbMATH Keywords

approximation algorithms; orthogonal polygons; stabbing number; conforming partitions

Mathematics Subject Classification ID

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

68W25: Approximation algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Minimizing the stabbing number of matchings, trees, and triangulations
• Algorithms for minimum length partitions of polygons
• Triangulating a simple polygon
• Approximation algorithms for partitioning a rectangle with interior points
• Rectilinear decompositions with low stabbing number
• Computing Partitions of Rectilinear Polygons with Minimum Stabbing Number
• GUARDING ORTHOGONAL ART GALLERIES WITH SLIDING CAMERAS
• Decomposing a Polygon into Simpler Components
• K-Sum Linear Programming
• The Problem of Compatible Representatives
• ON THE TIME BOUND FOR CONVEX DECOMPOSITION OF SIMPLE POLYGONS
• A Pedestrian Approach to Ray Shooting: Shoot a Ray, Take a Walk
• On Rectilinear Partitions with Minimum Stabbing Number
• Approximation algorithms for computing partitions with minimum stabbing number of rectilinear and simple polygons