Decomposing a Polygon into Simpler Components

DOI10.1137/0214056zbMath0575.68077OpenAlexW2041437464MaRDI QIDQ3694719

J. Mark Keil

Publication date: 1985

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0214056

zbMATH Keywords

dynamic programmingconvex polygonpolygon decompositionstar-shaped polygonmonotone polygonspiral polygon

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Dynamic programming (90C39) Discrete mathematics in relation to computer science (68R99)

Related Items (38)

POLYGON DECOMPOSITION AND THE ORTHOGONAL ART GALLERY PROBLEM ⋮ On gallery watchmen in grids ⋮ Partitioning Graph Drawings and Triangulated Simple Polygons into Greedily Routable Regions ⋮ Recognizing polygons, or how to spy ⋮ Decomposition and intersection of simple splinegons ⋮ ON THE TIME BOUND FOR CONVEX DECOMPOSITION OF SIMPLE POLYGONS ⋮ INNER-COVER OF NON-CONVEX SHAPES ⋮ A Shape-Newton Approach to the Problem of Covering with Identical Balls ⋮ GEOMETRIC ALGORITHMS FOR STATIC LEAF SEQUENCING PROBLEMS IN RADIATION THERAPY ⋮ Optimal 2-coverage of a polygonal region in a sensor network ⋮ Cooperative search by multiple unmanned aerial vehicles in a nonconvex environment ⋮ Computing conforming partitions of orthogonal polygons with minimum stabbing number ⋮ Exact and approximation algorithms for computing optimal fat decompositions ⋮ Triangulations, visibility graph and reflex vertices of a simple polygon ⋮ Minimum r-Star Cover of Class-3 Orthogonal Polygons ⋮ Approximation algorithms for decomposing octilinear polygons ⋮ A Dynamic Programming Approach to the Dominating Set Problem on k-Trees ⋮ Rectangularization of digital objects and its relation with straight skeletons ⋮ Minimum k-partitioning of rectilinear polygons ⋮ Covering orthogonal polygons with star polygons: The perfect graph approach ⋮ A generalized Winternitz theorem ⋮ Algorithms for the decomposition of a polygon into convex polygons ⋮ Decomposing a simple polygon into pseudo-triangles and convex polygons ⋮ Detecting the intersection of convex objects in the plane ⋮ Decompositions, partitions, and coverings with convex polygons and pseudo-triangles ⋮ On covering orthogonal polygons with star-shaped polygons ⋮ Minimum convex partition of a constrained point set ⋮ Minimum convex partition of a polygon with holes by cuts in given directions ⋮ The distance between convex sets with Minkowski sum structure: application to collision detection ⋮ Approximate convex decomposition of polygons ⋮ LOCATING GUARDS FOR VISIBILITY COVERAGE OF POLYGONS ⋮ Polygon decomposition for efficient construction of Minkowski sums ⋮ Linear-Time 3-Approximation Algorithm for the r-Star Covering Problem ⋮ A practical algorithm for decomposing polygonal domains into convex polygons by diagonals ⋮ Clique-width of point configurations ⋮ Polynomial-time instances of the minimum weight triangulation problem ⋮ On partitioning rectilinear polygons into star-shaped polygons ⋮ Polygon Area Decomposition for Multiple-Robot Workspace Division

This page was built for publication: Decomposing a Polygon into Simpler Components