Approximation Algorithms for the Minimum Convex Partition Problem

DOI10.1007/11785293_23MaRDI QIDQ5757909zbMATHOpenAlexFDO

Authors Christian Knauer, Andreas Spillner

Publication date 7 September 2007

Published in Algorithm Theory – SWAT 2006 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11785293_23

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Recommendations

• Minimum convex partition of point sets
• A fixed parameter algorithm for optimal convex partitions
• Minimum convex partition of a constrained point set
• Minimum weight convex Steiner partitions
• Minimum perimeter-sum partitions in the plane

Cited in

(32)

• scientific article; zbMATH DE number 1877049 (Why is no real title available?)
• A simplified convergence proof for the cone partitioning algorithm
• scientific article; zbMATH DE number 1830733 (Why is no real title available?)
• Geometric partitioning and robust ad-hoc network design
• Tight Time Bounds for the Minimum Local Convex Partition Problem
• Approximating a planar convex set using a sparse grid
• A Convex Approach to Minimal Partitions
• Computing optimal islands
• A fixed parameter algorithm for optimal convex partitions
• Convex Partitions of Polyhedra: A Lower Bound and Worst-Case Optimal Algorithm
• An Approximation Algorithm for Minimum Convex Cover with Logarithmic Performance Guarantee
• scientific article; zbMATH DE number 6381654 (Why is no real title available?)
• Solving the minimum convex partition of point sets with integer programming
• Better Approximations for the Minimum Common Integer Partition Problem
• Minimum weight convex Steiner partitions
• Conical partition algorithm for maximizing the sum of dc ratios
• An analysis of the LPT algorithm for the max-min and the min-ratio partition problems
• A Fixed Parameter Algorithm for the Minimum Number Convex Partition Problem
• Covering points with convex sets of minimum size
• Minimum convex partition of a constrained point set
• Hardness and approximation of minimum convex partition
• Minimum convex partition of point sets
• Minimum convex partitions and maximum empty polytopes
• Least-cost partition algorithms
• Approximation algorithms for the partial assignment problem
• Decomposing a simple polygon into pseudo-triangles and convex polygons
• Minimum perimeter-sum partitions in the plane
• Partitioning strategies for the block Cimmino algorithm
• Computing low-cost convex partitions for planar point sets based on tailored decompositions (CG challenge)
• Convex partitions with 2-edge connected dual graphs
• Minimization and parameterized variants of vertex partition problems on graphs
• Approximation algorithms for Min-k-overlap problems using the principal lattice of partitions approach

This page was built for publication: Approximation Algorithms for the Minimum Convex Partition Problem

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