ON THE TIME BOUND FOR CONVEX DECOMPOSITION OF SIMPLE POLYGONS

DOI10.1142/S0218195902000803MaRDI QIDQ4818554zbMATH OpenOpenAlexWikidataFDO

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

convex decompositiondynamic programmingsimple polygons

Mathematics Subject Classification ID

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

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

(19)

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

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)