---
_id: '5986'
abstract:
- lang: eng
text: "Given a triangulation of a point set in the plane, a flip deletes an edge
e whose removal leaves a convex quadrilateral, and replaces e by the opposite
diagonal of the quadrilateral. It is well known that any triangulation of a point
set can be reconfigured to any other triangulation by some sequence of flips.
We explore this question in the setting where each edge of a triangulation has
a label, and a flip transfers the label of the removed edge to the new edge. It
is not true that every labelled triangulation of a point set can be reconfigured
to every other labelled triangulation via a sequence of flips, but we characterize
when this is possible. There is an obvious necessary condition: for each label
l, if edge e has label l in the first triangulation and edge f has label l in
the second triangulation, then there must be some sequence of flips that moves
label l from e to f, ignoring all other labels. Bose, Lubiw, Pathak and Verdonschot
formulated the Orbit Conjecture, which states that this necessary condition is
also sufficient, i.e. that all labels can be simultaneously mapped to their destination
if and only if each label individually can be mapped to its destination. We prove
this conjecture. Furthermore, we give a polynomial-time algorithm (with \U0001D442(\U0001D45B8)
being a crude bound on the run-time) to find a sequence of flips to reconfigure
one labelled triangulation to another, if such a sequence exists, and we prove
an upper bound of \U0001D442(\U0001D45B7) on the length of the flip sequence.
Our proof uses the topological result that the sets of pairwise non-crossing edges
on a planar point set form a simplicial complex that is homeomorphic to a high-dimensional
ball (this follows from a result of Orden and Santos; we give a different proof
based on a shelling argument). The dual cell complex of this simplicial ball,
called the flip complex, has the usual flip graph as its 1-skeleton. We use properties
of the 2-skeleton of the flip complex to prove the Orbit Conjecture."
accept: '1'
article_processing_charge: No
author:
- first_name: Anna
full_name: Lubiw, Anna
last_name: Lubiw
- first_name: Zuzana
full_name: Masárová, Zuzana
id: 45CFE238-F248-11E8-B48F-1D18A9856A87
last_name: Masárová
orcid: 0000-0002-6660-1322
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
cc_license: '''https://creativecommons.org/licenses/by/4.0/'''
citation:
ama: Lubiw A, Masárová Z, Wagner U. A Proof of the Orbit Conjecture for Flipping
Edge-Labelled Triangulations. *Discrete & Computational Geometry*. 2018:1-19.
doi:10.1007/s00454-018-0035-8
apa: Lubiw, A., Masárová, Z., & Wagner, U. (2018). A Proof of the Orbit Conjecture
for Flipping Edge-Labelled Triangulations. *Discrete & Computational Geometry*,
1–19. https://doi.org/10.1007/s00454-018-0035-8
chicago: Lubiw, Anna, Zuzana Masárová, and Uli Wagner. “A Proof of the Orbit Conjecture
for Flipping Edge-Labelled Triangulations.” *Discrete & Computational Geometry*,
2018, 1–19. https://doi.org/10.1007/s00454-018-0035-8.
ieee: A. Lubiw, Z. Masárová, and U. Wagner, “A Proof of the Orbit Conjecture for
Flipping Edge-Labelled Triangulations,” *Discrete & Computational Geometry*,
pp. 1–19, 2018.
ista: Lubiw A, Masárová Z, Wagner U. 2018. A Proof of the Orbit Conjecture for Flipping
Edge-Labelled Triangulations. Discrete & Computational Geometry., 1–19.
mla: Lubiw, Anna, et al. “A Proof of the Orbit Conjecture for Flipping Edge-Labelled
Triangulations.” *Discrete & Computational Geometry*, Springer Nature
America, 2018, pp. 1–19, doi:10.1007/s00454-018-0035-8.
short: A. Lubiw, Z. Masárová, U. Wagner, Discrete & Computational Geometry (2018)
1–19.
date_created: 2019-02-14T11:54:08Z
date_published: 2018-09-26T00:00:00Z
date_updated: 2019-06-27T13:55:25Z
day: '26'
ddc:
- '000'
department:
- _id: UlWa
doi: 10.1007/s00454-018-0035-8
file:
- access_level: open_access
content_type: application/pdf
creator: dernst
date_created: 2019-02-14T11:57:22Z
date_updated: 2019-02-14T11:57:22Z
file_id: '5988'
file_name: 2018_DiscreteGeometry_Lubiw.pdf
file_size: 556276
open_access: 1
relation: main_file
success: 1
file_date_updated: 2019-02-14T11:57:22Z
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
page: 1-19
project:
- _id: BFDF9788-01D1-11E9-AC17-EBD7A21D5664
name: IST Austria Open Access Fund
publication: Discrete & Computational Geometry
publication_identifier:
issn:
- 0179-5376
- 1432-0444
publication_status: published
publisher: Springer Nature America
quality_controlled: '1'
related_material:
record:
- id: '683'
relation: earlier_version
status: public
status: public
title: A Proof of the Orbit Conjecture for Flipping Edge-Labelled Triangulations
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
year: '2018'
...
---
_id: '683'
abstract:
- lang: eng
text: 'Given a triangulation of a point set in the plane, a flip deletes an edge
e whose removal leaves a convex quadrilateral, and replaces e by the opposite
diagonal of the quadrilateral. It is well known that any triangulation of a point
set can be reconfigured to any other triangulation by some sequence of flips.
We explore this question in the setting where each edge of a triangulation has
a label, and a flip transfers the label of the removed edge to the new edge. It
is not true that every labelled triangulation of a point set can be reconfigured
to every other labelled triangulation via a sequence of flips, but we characterize
when this is possible. There is an obvious necessary condition: for each label
l, if edge e has label l in the first triangulation and edge f has label l in
the second triangulation, then there must be some sequence of flips that moves
label l from e to f, ignoring all other labels. Bose, Lubiw, Pathak and Verdonschot
formulated the Orbit Conjecture, which states that this necessary condition is
also sufficient, i.e. that all labels can be simultaneously mapped to their destination
if and only if each label individually can be mapped to its destination. We prove
this conjecture. Furthermore, we give a polynomial-time algorithm to find a sequence
of flips to reconfigure one labelled triangulation to another, if such a sequence
exists, and we prove an upper bound of O(n7) on the length of the flip sequence.
Our proof uses the topological result that the sets of pairwise non-crossing edges
on a planar point set form a simplicial complex that is homeomorphic to a high-dimensional
ball (this follows from a result of Orden and Santos; we give a different proof
based on a shelling argument). The dual cell complex of this simplicial ball,
called the flip complex, has the usual flip graph as its 1-skeleton. We use properties
of the 2-skeleton of the flip complex to prove the Orbit Conjecture.'
accept: '1'
alternative_title:
- LIPIcs
article_number: '49'
article_processing_charge: No
author:
- first_name: Anna
full_name: Lubiw, Anna
last_name: Lubiw
- first_name: Zuzana
full_name: Masárová, Zuzana
id: 45CFE238-F248-11E8-B48F-1D18A9856A87
last_name: Masárová
orcid: 0000-0002-6660-1322
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
cc_license: '''https://creativecommons.org/licenses/by/4.0/'''
citation:
ama: 'Lubiw A, Masárová Z, Wagner U. A proof of the orbit conjecture for flipping
edge labelled triangulations. In: Vol 77. Schloss Dagstuhl - Leibniz-Zentrum für
Informatik; 2017. doi:10.4230/LIPIcs.SoCG.2017.49'
apa: 'Lubiw, A., Masárová, Z., & Wagner, U. (2017). A proof of the orbit conjecture
for flipping edge labelled triangulations (Vol. 77). Presented at the SoCG: Symposium
on Computational Geometry, Brisbane, Australia: Schloss Dagstuhl - Leibniz-Zentrum
für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2017.49'
chicago: Lubiw, Anna, Zuzana Masárová, and Uli Wagner. “A Proof of the Orbit Conjecture
for Flipping Edge Labelled Triangulations,” Vol. 77. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2017. https://doi.org/10.4230/LIPIcs.SoCG.2017.49.
ieee: 'A. Lubiw, Z. Masárová, and U. Wagner, “A proof of the orbit conjecture for
flipping edge labelled triangulations,” presented at the SoCG: Symposium on Computational
Geometry, Brisbane, Australia, 2017, vol. 77.'
ista: 'Lubiw A, Masárová Z, Wagner U. 2017. A proof of the orbit conjecture for
flipping edge labelled triangulations. SoCG: Symposium on Computational Geometry,
LIPIcs, vol. 77.'
mla: Lubiw, Anna, et al. *A Proof of the Orbit Conjecture for Flipping Edge Labelled
Triangulations*. Vol. 77, 49, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2017, doi:10.4230/LIPIcs.SoCG.2017.49.
short: A. Lubiw, Z. Masárová, U. Wagner, in:, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2017.
conference:
end_date: 2017-07-07
location: Brisbane, Australia
name: 'SoCG: Symposium on Computational Geometry'
start_date: 2017-07-04
date_created: 2018-12-11T11:47:54Z
date_published: 2017-06-01T00:00:00Z
date_updated: 2019-06-27T13:55:24Z
day: '01'
ddc:
- '514'
- '516'
department:
- _id: UlWa
doi: 10.4230/LIPIcs.SoCG.2017.49
file:
- access_level: open_access
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:17:12Z
date_updated: 2018-12-12T10:17:12Z
file_id: '5265'
file_name: IST-2017-896-v1+1_LIPIcs-SoCG-2017-49.pdf
file_size: 710007
open_access: 1
relation: main_file
file_date_updated: 2018-12-12T10:17:12Z
intvolume: ' 77'
language:
- iso: eng
month: '06'
oa_version: Published Version
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '7033'
pubrep_id: '896'
quality_controlled: '1'
related_material:
record:
- id: '5986'
relation: later_version
status: public
status: public
title: A proof of the orbit conjecture for flipping edge labelled triangulations
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 77
year: '2017'
...