Edge Sparsification for Geometric Tour Problems

Abstract: We study a variety of sparsification approaches for a spectrum of geometric optimization problems related to tour problems, such as the Angular TSP, the Minimum Perimeter Problem, and the Minimum/Maximum Area Polygon Problem. To this end, we conduct a thorough study that compares the solution quality and runtime achieved by integer programming solvers on geometrically reduced edge sets to the exact solution on the full edge set; considered sparsification techniques include a variety of triangulations (Delaunay, Greedy, Minimum Weight), Theta and Yao graphs, Well-Separated Pair Decomposition, and Onion graphs. We demonstrate that edge sparsification often leads to significantly reduced runtimes. For several of the considered problems, we can compute within a few seconds solutions that are very close to being optimal for instances that could not be solved to provable optimality within an hour; for other problems, we encounter a significant loss in solution quality. However, for almos.... https://www.cgt-journal.org/index.php/cgt/article/view/20

Object Details

• Location: Deutsche Nationalbibliothek Frankfurt am Main
• Extent: Online-Ressource
• Language: Englisch

References and Relationships

• Bibliographic citation: Edge Sparsification for Geometric Tour Problems ; volume:3 ; number:1 ; year:2024 ; Computing in Geometry and Topology ; 3, Heft 1 (2024)

Contributors, Places and Time

• Creator: Fekete, Sándor ; Keldenich, Phillip ; Krupke, Dominik ; Niehs, Eike

Further information

• DOI: 10.57717/cgt.v3i1.20
• URN: urn:nbn:de:101:1-2024030306543106266291
• Rights: Open Access; Der Zugriff auf das Objekt ist unbeschränkt möglich.
• Last update: 14.08.2025, 10:58 AM CEST