ON THE TIME BOUND FOR CONVEX DECOMPOSITION OF SIMPLE POLYGONS

DOI10.1142/S0218195902000803zbMath1152.68670OpenAlexW2109083408WikidataQ56970708 ScholiaQ56970708MaRDI QIDQ4818554

Mark J. Keil, Jack Scott Snoeyink

Publication date: 29 September 2004

Published in: International Journal of Computational Geometry & Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0218195902000803

zbMATH Keywords

dynamic programmingsimple polygonsconvex decomposition

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational aspects related to convexity (52B55) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (15)

Planar and Toroidal Morphs Made Easier ⋮ Convex Partitions with 2-Edge Connected Dual Graphs ⋮ Computing conforming partitions of orthogonal polygons with minimum stabbing number ⋮ Exact and approximation algorithms for computing optimal fat decompositions ⋮ Convex partitions with 2-edge connected dual graphs ⋮ Computing the Fréchet distance between simple polygons ⋮ Decomposing a simple polygon into pseudo-triangles and convex polygons ⋮ Decompositions, partitions, and coverings with convex polygons and pseudo-triangles ⋮ Approximating the maximum overlap of polygons under translation ⋮ Minimum convex partition of a constrained point set ⋮ Weighted skeletons and fixed-share decomposition ⋮ Minimum weight convex Steiner partitions ⋮ Polygon decomposition for efficient construction of Minkowski sums ⋮ A practical algorithm for decomposing polygonal domains into convex polygons by diagonals ⋮ A fixed parameter algorithm for optimal convex partitions

Cites Work

• Visibility and intersection problems in plane geometry
• Ray shooting in polygons using geodesic triangulations
• Fast triangulation of the plane with respect to simple polygons
• Decomposing a Polygon into Simpler Components
• A linear algorithm for computing the visibility polygon from a point

This page was built for publication: ON THE TIME BOUND FOR CONVEX DECOMPOSITION OF SIMPLE POLYGONS