Untangling Segments in the Plane
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916575571869696 |
|---|---|
| author | da Fonseca, Guilherme D. Gerard, Yan Rivier, Bastien |
| author_facet | da Fonseca, Guilherme D. Gerard, Yan Rivier, Bastien |
| contents | A set of n segments in the plane may form a Euclidean TSP tour, a tree, or a matching, among others. Optimal TSP tours as well as minimum spanning trees and perfect matchings have no crossing segments, but several heuristics and approximation algorithms may produce solutions with crossings. If two segments cross, then we can reduce the total length with the following flip operation. We remove a pair of crossing segments, and insert a pair of non-crossing segments, while keeping the same vertex degrees. In this paper, we consider the number of flips performed under different assumptions, using a new unifying framework that applies to tours, trees, matchings, and other types of (multi)graphs. Within this framework, we prove several new bounds that are sensitive to whether some endpoints are in convex position or not. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_12306 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Untangling Segments in the Plane da Fonseca, Guilherme D. Gerard, Yan Rivier, Bastien Computational Geometry A set of n segments in the plane may form a Euclidean TSP tour, a tree, or a matching, among others. Optimal TSP tours as well as minimum spanning trees and perfect matchings have no crossing segments, but several heuristics and approximation algorithms may produce solutions with crossings. If two segments cross, then we can reduce the total length with the following flip operation. We remove a pair of crossing segments, and insert a pair of non-crossing segments, while keeping the same vertex degrees. In this paper, we consider the number of flips performed under different assumptions, using a new unifying framework that applies to tours, trees, matchings, and other types of (multi)graphs. Within this framework, we prove several new bounds that are sensitive to whether some endpoints are in convex position or not. |
| title | Untangling Segments in the Plane |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2501.12306 |