Advanced search
Start date
(Reference retrieved automatically from Web of Science through information on FAPESP grant and its corresponding number as mentioned in the publication by the authors.)

Solving the minimum convex partition of point sets with integer programming

Full text
Sapucaia, Allan [1] ; Rezende, Pedro J. de [1] ; Souza, Cid C. de [1]
Total Authors: 3
[1] Univ Estadual Campinas, Inst Comp, Campinas - Brazil
Total Affiliations: 1
Document type: Journal article
Web of Science Citations: 0

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. (C) 2021 Elsevier B.V. All rights reserved. (AU)

FAPESP's process: 18/14883-5 - Geometric decomposition problems
Grantee:Allan Sapucaia Barboza
Support Opportunities: Scholarships in Brazil - Doctorate (Direct)
FAPESP's process: 18/26434-0 - Exact and heuristic algorithms for solving difficult problems related to computational geometry
Grantee:Pedro Jussieu de Rezende
Support Opportunities: Regular Research Grants
FAPESP's process: 14/12236-1 - AnImaLS: Annotation of Images in Large Scale: what can machines and specialists learn from interaction?
Grantee:Alexandre Xavier Falcão
Support Opportunities: Research Projects - Thematic Grants