scientific article; zbMATH DE number 3986641

zbMATH Open0609.68035MaRDI QIDQ3750120FDOQ3750120

Authors: David P. Dobkin, Bernard Chazelle 

Publication date: 1985

Title of this publication is not available (Why is that?)

Recommendations

• scientific article
• 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

zbMATH Keywords

dynamic programmingSteiner pointspolynomial timegeometric complexityoptimal convex decompositiondecomposition of a simple polygon into a minimum number of convex polygons

Mathematics Subject Classification ID

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

Cited In (39)

• Decomposing a Polygon into Simpler Components
• A Bound on a Convexity Measure for Point Sets
• SFCDecomp: Multicriteria Optimized Tool Path Planning in 3D Printing using Space-Filling Curve Based Domain Decomposition
• A virtual element method for transversely isotropic hyperelasticity
• On decomposing polygons into uniformly monotone parts
• Complete and robust no-fit polygon generation for the irregular stock cutting problem
• A decompositin theorem for convexity spaces
• Locking-free compressible quadrilateral finite elements: Poisson's ratio-dependent vector interpolants
• Polygon vertex extremality and decomposition of polygons
• Algorithms for the decomposition of a polygon into convex polygons
• Approximate convex decomposition of polygons
• Decompositions, partitions, and coverings with convex polygons and pseudo-triangles
• Uniformly monotone partitioning of polygons
• A practical algorithm for decomposing polygonal domains into convex polygons by diagonals
• Polygon decomposition and switching function minimization
• Exact and approximation algorithms for computing optimal fat decompositions
• DECOPOL -- Codes for decomposing a polygon into convex subpolygons
• Minimum convex partition of a polygon with holes by cuts in given directions
• On convex partitions of polygonal regions
• Decomposition of Catalan numbers and convex polygon triangulations
• Cooperative search by multiple unmanned aerial vehicles in a nonconvex environment
• Computational Science and Its Applications – ICCSA 2004
• Convex Partitions with 2-Edge Connected Dual Graphs
• Polygon decomposition for efficient construction of Minkowski sums
• A worst-case optimal algorithm to compute the Minkowski sum of convex polytopes
• Graph problems arising from parameter identification of discrete dynamical systems
• 3-colored triangulation of 2D maps
• Minimum k-partitioning of rectilinear polygons
• Decomposition and intersection of simple splinegons
• Title not available (Why is that?)
• Detecting the intersection of convex objects in the plane
• Title not available (Why is that?)
• Convex partitions with 2-edge connected dual graphs
• ON THE TIME BOUND FOR CONVEX DECOMPOSITION OF SIMPLE POLYGONS
• Decomposing a simple polygon into pseudo-triangles and convex polygons
• Convexity and closure in optimal allocations determined by decomposable measures
• Partitioning Graph Drawings and Triangulated Simple Polygons into Greedily Routable Regions
• A worst-case optimal algorithm to compute the Minkowski sum of convex polytopes
• Triangulations, visibility graph and reflex vertices of a simple polygon

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)