Approximation Algorithms for the Minimum Convex Partition Problem

DOI10.1007/11785293_23zbMATH Open1142.68615OpenAlexW1608309968MaRDI QIDQ5757909FDOQ5757909

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

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

Mathematics Subject Classification ID

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

Cited In (24)

• Solving the minimum convex partition of point sets with integer programming
• Approximation algorithms for Min-k-overlap problems using the principal lattice of partitions approach
• Title not available (Why is that?)
• Minimum weight convex Steiner partitions
• Convex Partitions of Polyhedra: A Lower Bound and Worst-Case Optimal Algorithm
• Computing optimal islands
• Title not available (Why is that?)
• Minimum convex partition of a constrained point set
• Tight Time Bounds for the Minimum Local Convex Partition Problem
• A Convex Approach to Minimal Partitions
• A simplified convergence proof for the cone partitioning algorithm
• Approximation algorithms for the partial assignment problem
• Minimization and parameterized variants of vertex partition problems on graphs
• 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
• Least-cost partition algorithms
• Convex partitions with 2-edge connected dual graphs
• Title not available (Why is that?)
• Decomposing a simple polygon into pseudo-triangles and convex polygons
• A fixed parameter algorithm for optimal convex partitions
• Better Approximations for the Minimum Common Integer Partition Problem
• An Approximation Algorithm for Minimum Convex Cover with Logarithmic Performance Guarantee
• Partitioning strategies for the block Cimmino algorithm

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)