Solving the minimum convex partition of point sets with integer programming
From MaRDI portal
Abstract: The partition of a problem into smaller sub-problems satisfying certain properties is often a key ingredient in the design of divide-and-conquer algorithms. For questions related to location, the partition problem can be modeled, in geometric terms, as finding a subdivision of a planar map -- which represents, say, a geographical area -- into regions subject to certain conditions while optimizing some objective function. In this paper, we investigate one of these geometric problems known as the Minimum Convex Partition Problem (MCPP). A convex partition of a point set in the plane is a subdivision of the convex hull of whose edges are segments with both endpoints in and such that all internal faces are empty convex polygons. The MCPP is an NP-hard problem where one seeks to find a convex partition with the least number of faces. We present a novel polygon-based integer programming formulation for the MCPP, which leads to better dual bounds than the previously known edge-based model. Moreover, we introduce a primal heuristic, a branching rule and a pricing algorithm. The combination of these techniques leads to the ability to solve instances with twice as many points as previously possible while constrained to identical computational resources. A comprehensive experimental study is presented to show the impact of our design choices.
Recommendations
Cites work
- scientific article; zbMATH DE number 1312984 (Why is no real title available?)
- scientific article; zbMATH DE number 1062478 (Why is no real title available?)
- scientific article; zbMATH DE number 7124428 (Why is no real title available?)
- A fixed parameter algorithm for optimal convex partitions
- A note on convex decompositions of a set of points in the plane
- Algorithm 966: A practical iterative algorithm for the art gallery problem using integer linear programming
- An Integer Programming Approach to the Vehicle Scheduling Problem
- Approximation Algorithms for the Minimum Convex Partition Problem
- Arc-based integer programming formulations for three variants of proportional symbol maps
- Branch-and-price: Column generation for solving huge integer programs
- Computing MaxMin edge length triangulations
- Computing nonsimple polygons of minimum perimeter
- Edge insertion for optimal triangulations
- Minimum convex partition of a constrained point set
- Minimum convex partition of point sets
- Selected Topics in Column Generation
- Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms
- Solving the geometric firefighter routing problem via integer programming
- The continuous 1.5D terrain guarding problem: discretization, optimal solutions, and PTAS
- The ellipsoid method and its consequences in combinatorial optimization
- The nature and meaning of perturbations in geometric computing
- The number of edges of many faces in a line segment arrangement
- Triangulations. Structures for algorithms and applications
- Using the primal-dual interior point algorithm within the branch-price-and-cut method
Cited in
(6)- Olp: An R package for optimal linear partitions of finite sets of points on the plane
- Minimum convex partition of point sets
- Minimum convex partition of a constrained point set
- Computing Low-Cost Convex Partitions for Planar Point Sets with Randomized Local Search and Constraint Programming (CG Challenge)
- Computing Low-Cost Convex Partitions for Planar Point Sets Based on a Memetic Approach (CG Challenge)
- A Fixed Parameter Algorithm for the Minimum Number Convex Partition Problem
This page was built for publication: Solving the minimum convex partition of point sets with integer programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q824341)
