Solving the minimum convex partition of point sets with integer programming

DOI10.1016/j.comgeo.2021.101794zbMath1482.90188arXiv2012.03381OpenAlexW3170225863MaRDI QIDQ824341

Allan Sapucaia, Pedro J. de Rezende, Cid Carvalho De Souza

Publication date: 15 December 2021

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

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

zbMATH Keywords

combinatorial optimizationminimum convex partitioncomputational geometry

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Using the primal-dual interior point algorithm within the branch-price-and-cut method
• Triangulations. Structures for algorithms and applications
• A fixed parameter algorithm for optimal convex partitions
• The ellipsoid method and its consequences in combinatorial optimization
• The number of edges of many faces in a line segment arrangement
• The nature and meaning of perturbations in geometric computing
• Arc-based integer programming formulations for three variants of proportional symbol maps
• Solving the geometric firefighter routing problem via integer programming
• A note on convex decompositions of a set of points in the plane
• Minimum convex partition of point sets
• Edge insertion for optimal triangulations
• Branch-and-Price: Column Generation for Solving Huge Integer Programs
• Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms
• An Integer Programming Approach to the Vehicle Scheduling Problem
• Computing maxmin edge length triangulations
• Algorithm 966
• Selected Topics in Column Generation
• Computing nonsimple polygons of minimum perimeter
• Approximation Algorithms for the Minimum Convex Partition Problem
• Minimum convex partition of a constrained point set