Optimal area polygonization problems: Exact solutions through geometric duality

Autor(es)

Ramos, Natanael ; de Rezende, Pedro J. ; de Souza, Cid C.

• Tipo de documento: Artigo Científico
• Fonte: Computers & Operations Research; v. 145, p. 10-pg., 2022-05-06.

Resumo

In this paper, we describe exact methods to solve two problems: given a set S of n points in the plane, find a simple polygon whose set of vertices is precisely S and has minimum (MIN-AREA) or maximum (MAX-AREA) area. These problems are strongly related to the Euclidean TSP, whilst the goal here is to min/max-imize the finite area bounded by the cycle. Both problems are known to be NP-complete. Previous works focused on heuristic methods, specially in 2019, where considerable attention was given to them due to a worldwide contest that took place as part of the Computational Geometry Week. Moreover, to the best of our knowledge, there is only one work aimed to solve these problems exactly. Our main contributions include a novel Integer Linear Programming (ILP) formulation for these problems, along with preprocessing and formulation strengthening techniques to improve its performance in practice. We conducted an extensive experimental study to assess the effectiveness of our model and its variants, and to compare our results to the literature. With respect to the latter analysis, we achieved a speedup of approximately 11.46 (2.21) on average for MIN-AREA (MAX-AREA), when compared to the best known model. (AU)

• 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