Covering orthogonal polygons with star polygons: The perfect graph approach
From MaRDI portal
Publication:918225
DOI10.1016/0022-0000(90)90017-FzbMath0705.68082MaRDI QIDQ918225
Huzur Saran, Rajeev Motwani, Arvind U. Raghunathan
Publication date: 1990
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
perfect graphorthogonal polygonsstar polygonscombinatorial structure of visibilitypolygon covering problem
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Related Items
Dimensions of staircase kernels in orthogonal polygons, Tight bounds for conflict-free chromatic guarding of orthogonal art galleries, Covering grids and orthogonal polygons with periscope guards, POLYGON DECOMPOSITION AND THE ORTHOGONAL ART GALLERY PROBLEM, A Krasnosel'skij theorem for staircase paths in orthogonal polygons, Unions of orthogonally convex or orthogonally starshaped polygons, Algorithms for weakly triangulated graphs, Staircase visibility and computation of kernels, Note on covering monotone orthogonal polygons with star-shaped polygons, A Scheme for Computing Minimum Covers within Simple Regions, Specifying the staircase kernel of a two-fold connected orthogonal polygon, Visibility in semi-convex spaces, On orthogonally guarding orthogonal polygons with bounded treewidth, Staircase kernels for orthogonal \(d\)-polytopes, A 3-Approximation Algorithm for Guarding Orthogonal Art Galleries with Sliding Cameras, Minimum r-Star Cover of Class-3 Orthogonal Polygons, A hybrid heuristic for the rectilinear picture compression problem, A scheme for computing minimum covers within simple regions, Planar compact sets whose intersections are starshaped via orthogonally convex paths, Finding minimum witness sets in orthogonal polygons, Rectangle blanket problem: binary integer linear programming formulation and solution algorithms, LINEAR-TIME 3-APPROXIMATION ALGORITHM FOR THE r-STAR COVERING PROBLEM, On guarding the vertices of rectilinear domains, Linear-Time 3-Approximation Algorithm for the r-Star Covering Problem, Unnamed Item, Staircase kernels in orthogonal polygons, An efficient algorithm for finding a two-pair, and its applications, Altitude terrain guarding and guarding uni-monotone polygons, Krasnosel'skii-type theorems for dent edges in orthogonal polygones, Staircase \(k\)-kernels for orthogonal polygons, Polyominos and perfect graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Weakly triangulated graphs
- It’s Hard to Color Antirectangles
- Decomposing a Polygon into Simpler Components
- Perfect Graphs and Orthogonally Convex Covers
- Covering Regions with Squares
- Some NP-hard polygon decomposition problems
- Algorithmic Aspects of Vertex Elimination on Graphs
- Covering Polygons Is Hard
- Covering Regions by Rectangles
- A Class of Perfect Graphs
- A Class of Perfect Graphs Associated with Planar Rectilinear Regions
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
