Solving the minimum convex partition of point sets with integer programming

DOI10.1016/J.COMGEO.2021.101794zbMATH Open1482.90188arXiv2012.03381OpenAlexW3170225863MaRDI QIDQ824341FDOQ824341

Authors: Allan Sapucaia, Pedro J. de Rezende, Cid Carvalho de Souza 

Publication date: 15 December 2021

Published in: Computational Geometry (Search for Journal in Brave)

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 $P$ in the plane is a subdivision of the convex hull of $P$ whose edges are segments with both endpoints in $P$ 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.

Full work available at URL: https://arxiv.org/abs/2012.03381

Recommendations

• Minimum convex partition of point sets
• Minimum convex partition of a constrained point set
• EXACT SOLUTIONS OF RECTANGULAR PARTITIONS VIA INTEGER PROGRAMMING
• Approximation Algorithms for the Minimum Convex Partition Problem
• A fixed parameter algorithm for optimal convex partitions

zbMATH Keywords

combinatorial optimizationcomputational geometryminimum convex partition

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Integer programming (90C10)

Cites Work

• Algorithm 966: A practical iterative algorithm for the art gallery problem using integer linear programming
• Triangulations. Structures for algorithms and applications
• Selected Topics in Column Generation
• The ellipsoid method and its consequences in combinatorial optimization
• The nature and meaning of perturbations in geometric computing
• Branch-and-price: Column generation for solving huge integer programs
• Using the primal-dual interior point algorithm within the branch-price-and-cut method
• Title not available (Why is that?)
• Title not available (Why is that?)
• An Integer Programming Approach to the Vehicle Scheduling Problem
• Title not available (Why is that?)
• A note on convex decompositions of a set of points in the plane
• Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms
• Approximation Algorithms for the Minimum Convex Partition Problem
• Minimum convex partition of a constrained point set
• Edge insertion for optimal triangulations
• A fixed parameter algorithm for optimal convex partitions
• The number of edges of many faces in a line segment arrangement
• Arc-based integer programming formulations for three variants of proportional symbol maps
• Solving the geometric firefighter routing problem via integer programming
• Minimum convex partition of point sets
• The continuous 1.5D terrain guarding problem: discretization, optimal solutions, and PTAS
• Computing MaxMin edge length triangulations
• Computing nonsimple polygons of minimum perimeter

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)