Solving the minimum convex partition of point sets with integer programming

Autor(es)

Sapucaia, Allan ^[1] ; Rezende, Pedro J. de ^[1] ; Souza, Cid C. de ^[1]

Afiliação do(s) autor(es)

^[1] Univ Estadual Campinas, Inst Comp, Campinas - Brazil

• Tipo de documento: Artigo Científico
• Fonte: COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS; v. 99, DEC 2021.
• Citações Web of Science: 0

Resumo

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)

• Processo FAPESP: 18/14883-5 - Problemas geométricos de decomposição
• Beneficiário: Allan Sapucaia Barboza
• Modalidade de apoio: Bolsas no Brasil - Doutorado Direto
• Processo FAPESP: 18/26434-0 - Algoritmos exatos e heurísticos para solução de problemas difíceis relacionados a geometria computacional
• Beneficiário: Pedro Jussieu de Rezende
• Modalidade de apoio: Auxílio à Pesquisa - Regular
• Processo FAPESP: 14/12236-1 - AnImaLS: Anotação de Imagem em Larga Escala: o que máquinas e especialistas podem aprender interagindo?
• Beneficiário: Alexandre Xavier Falcão
• Modalidade de apoio: Auxílio à Pesquisa - Temático