ON THE TIME BOUND FOR CONVEX DECOMPOSITION OF SIMPLE POLYGONS

DOI10.1142/S0218195902000803zbMATH1152.68670OpenAlexW2109083408WikidataQ56970708MaRDI QIDQ4818554FDOQ4818554

Authors Mark J. Keil, Jack 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 programmingconvex decompositionsimple polygons

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 3986641
• Decomposing a simple polygon into pseudo-triangles and convex polygons
• Decomposing the boundary of a nonconvex polyhedron
• Decomposing the boundary of a nonconvex polyhedron
• Triangulating a nonconvex polytope

Cites work

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

Cited in

(17)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4818554)