A Linear Time Algorithm for Finding Minimum Flip Sequences between Plane Spanning Paths in Convex Point Sets
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910017147371520 |
|---|---|
| author | Aichholzer, Oswin Dorfer, Joseph |
| author_facet | Aichholzer, Oswin Dorfer, Joseph |
| contents | We provide a linear time algorithm to determine the flip distance between two plane spanning paths on a point set in convex position. At the same time, we show that the happy edge property does not hold in this setting. This has to be seen in contrast to several results for reconfiguration problems where the absence of the happy edge property implies algorithmic hardness of the flip distance problem. Further, we show that our algorithm can be adapted for (1) compatible flips (2) local flips and (3) flips for plane spanning paths in simple polygons. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_02740 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Linear Time Algorithm for Finding Minimum Flip Sequences between Plane Spanning Paths in Convex Point Sets Aichholzer, Oswin Dorfer, Joseph Computational Geometry We provide a linear time algorithm to determine the flip distance between two plane spanning paths on a point set in convex position. At the same time, we show that the happy edge property does not hold in this setting. This has to be seen in contrast to several results for reconfiguration problems where the absence of the happy edge property implies algorithmic hardness of the flip distance problem. Further, we show that our algorithm can be adapted for (1) compatible flips (2) local flips and (3) flips for plane spanning paths in simple polygons. |
| title | A Linear Time Algorithm for Finding Minimum Flip Sequences between Plane Spanning Paths in Convex Point Sets |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2507.02740 |