| Full text | |
| Author(s): |
Total Authors: 3
|
| Affiliation: | [1] Univ Estadual Campinas, Inst Comp, Campinas - Brazil
Total Affiliations: 1
|
| Document type: | Journal article |
| Source: | COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS; v. 99, DEC 2021. |
| Web of Science Citations: | 0 |
| Abstract | |
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 |