Edge Sparsification for Geometric Tour Problems





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 almost all problems we considered, we find good solutions much earlier in the search process than for the complete edge set; thus, our methods can at least be used to provide initial bounds for the exact solution, demonstrating their usefulness even if optimality cannot be established.




How to Cite

Fekete, S., Keldenich, P., Krupke, D., & Niehs, E. (2024). Edge Sparsification for Geometric Tour Problems. Computing in Geometry and Topology, 3(1), 1:1–1:23. https://doi.org/10.57717/cgt.v3i1.20



Original Research Articles