Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

Solving the minimum convex partition of point sets with integer programming

Texto completo
Autor(es):
Sapucaia, Allan [1] ; Rezende, Pedro J. de [1] ; Souza, Cid C. de [1]
Número total de Autores: 3
Afiliação do(s) autor(es):
[1] Univ Estadual Campinas, Inst Comp, Campinas - Brazil
Número total de Afiliações: 1
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