scientific article; zbMATH DE number 3986641

MaRDI QIDQ3750120zbMATH OpenFDO

Authors David P. Dobkin, Bernard Chazelle

Publication date 1985

zbMATH Keywords

decomposition of a simple polygon into a minimum number of convex polygonsdynamic programminggeometric complexityoptimal convex decompositionpolynomial timeSteiner points

Mathematics Subject Classification ID

Polyhedra and polytopes; regular figures, division of spaces (51M20) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 4211553
• ON THE TIME BOUND FOR CONVEX DECOMPOSITION OF SIMPLE POLYGONS
• Decomposing a simple polygon into pseudo-triangles and convex polygons
• Algorithms for the decomposition of a polygon into convex polygons
• Approximate convex decomposition of polygons

Cited in

(45)

• A practical algorithm for decomposing polygonal domains into convex polygons by diagonals
• Decomposition and intersection of simple splinegons
• On decomposing polygons into uniformly monotone parts
• Triangulations, visibility graph and reflex vertices of a simple polygon
• Detecting the intersection of convex objects in the plane
• DECOPOL -- Codes for decomposing a polygon into convex subpolygons
• On convex partitions of polygonal regions
• Cooperative search by multiple unmanned aerial vehicles in a nonconvex environment
• A decompositin theorem for convexity spaces
• Algorithms for the decomposition of a polygon into convex polygons
• A virtual element method for transversely isotropic hyperelasticity
• Convexity and closure in optimal allocations determined by decomposable measures
• Approximation algorithms for decomposing octilinear polygons
• Locking-free compressible quadrilateral finite elements: Poisson's ratio-dependent vector interpolants
• Decompositions, partitions, and coverings with convex polygons and pseudo-triangles
• Approximate convex decomposition of polygons
• 3-colored triangulation of 2D maps
• Decomposition of Catalan numbers and convex polygon triangulations
• scientific article; zbMATH DE number 6387439 (Why is no real title available?)
• Polygon decomposition and switching function minimization
• scientific article; zbMATH DE number 4211553 (Why is no real title available?)
• Decomposing a Polygon into Simpler Components
• scientific article; zbMATH DE number 519872 (Why is no real title available?)
• scientific article; zbMATH DE number 1159075 (Why is no real title available?)
• ON THE TIME BOUND FOR CONVEX DECOMPOSITION OF SIMPLE POLYGONS
• scientific article; zbMATH DE number 1424299 (Why is no real title available?)
• SFCDecomp: multicriteria optimized tool path planning in 3D printing using space-filling curve based domain decomposition
• A bound on a convexity measure for point sets
• Computational Science and Its Applications – ICCSA 2004
• Convex Partitions with 2-Edge Connected Dual Graphs
• Partitioning Graph Drawings and Triangulated Simple Polygons into Greedily Routable Regions
• Polygon decomposition for efficient construction of Minkowski sums
• Exact and approximation algorithms for computing optimal fat decompositions
• A worst-case optimal algorithm to compute the Minkowski sum of convex polytopes
• Graph problems arising from parameter identification of discrete dynamical systems
• Minimum convex partition of a polygon with holes by cuts in given directions
• Convex partitions with 2-edge connected dual graphs
• Uniformly monotone partitioning of polygons
• Minimum star partitions of simple polygons in polynomial time
• Monotone partitions of simple polygons
• Polygon vertex extremality and decomposition of polygons
• A worst-case optimal algorithm to compute the Minkowski sum of convex polytopes
• Complete and robust no-fit polygon generation for the irregular stock cutting problem
• Minimum k-partitioning of rectilinear polygons
• Decomposing a simple polygon into pseudo-triangles and convex polygons

This page was built for publication:

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