---
_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
article_type: original
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*. 2019;61(4):880-898.
doi:10.1007/s00454-018-0035-8
apa: Lubiw, A., Masárová, Z., & Wagner, U. (2019). A Proof of the Orbit Conjecture
for Flipping Edge-Labelled Triangulations. *Discrete & Computational Geometry*,
*61*(4), 880–898. 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*
61, no. 4 (2019): 880–98. 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*,
vol. 61, no. 4, pp. 880–898, 2019.
ista: Lubiw A, Masárová Z, Wagner U. 2019. A Proof of the Orbit Conjecture for Flipping
Edge-Labelled Triangulations. Discrete & Computational Geometry. 61(4), 880–898.
mla: Lubiw, Anna, et al. “A Proof of the Orbit Conjecture for Flipping Edge-Labelled
Triangulations.” *Discrete & Computational Geometry*, vol. 61, no. 4,
Springer Nature, 2019, pp. 880–98, doi:10.1007/s00454-018-0035-8.
short: A. Lubiw, Z. Masárová, U. Wagner, Discrete & Computational Geometry 61
(2019) 880–898.
date_created: 2019-02-14T11:54:08Z
date_published: 2019-06-01T00:00:00Z
date_updated: 2019-09-24T07:18:40Z
day: '01'
ddc:
- '000'
department:
- _id: UlWa
doi: 10.1007/s00454-018-0035-8
external_id:
arxiv:
- '1710.02741'
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
intvolume: ' 61'
issue: '4'
language:
- iso: eng
month: '06'
oa_version: Published Version
page: 880-898
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
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: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 61
year: '2019'
...
---
_id: '6989'
abstract:
- lang: eng
text: 'When can a polyomino piece of paper be folded into a unit cube? Prior work
studied tree-like polyominoes, but polyominoes with holes remain an intriguing
open problem. We present sufficient conditions for a polyomino with hole(s) to
fold into a cube, and conditions under which cube folding is impossible. In particular,
we show that all but five special simple holes guarantee foldability. '
article_processing_charge: No
author:
- first_name: Oswin
full_name: Aichholzer, Oswin
last_name: Aichholzer
- first_name: Hugo A
full_name: Akitaya, Hugo A
last_name: Akitaya
- first_name: Kenneth C
full_name: Cheung, Kenneth C
last_name: Cheung
- first_name: Erik D
full_name: Demaine, Erik D
last_name: Demaine
- first_name: Martin L
full_name: Demaine, Martin L
last_name: Demaine
- first_name: Sandor P
full_name: Fekete, Sandor P
last_name: Fekete
- first_name: Linda
full_name: Kleist, Linda
last_name: Kleist
- first_name: Irina
full_name: Kostitsyna, Irina
last_name: Kostitsyna
- first_name: Maarten
full_name: Löffler, Maarten
last_name: Löffler
- 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: Klara
full_name: Mundilova, Klara
last_name: Mundilova
- first_name: Christiane
full_name: Schmidt, Christiane
last_name: Schmidt
citation:
ama: 'Aichholzer O, Akitaya HA, Cheung KC, et al. Folding polyominoes with holes
into a cube. In: *Proceedings of the 31st Canadian Conference on Computational
Geometry*. Canadian Conference on Computational Geometry; 2019:164-170.'
apa: 'Aichholzer, O., Akitaya, H. A., Cheung, K. C., Demaine, E. D., Demaine, M.
L., Fekete, S. P., … Schmidt, C. (2019). Folding polyominoes with holes into a
cube. In *Proceedings of the 31st Canadian Conference on Computational Geometry*
(pp. 164–170). Edmonton, Canada: Canadian Conference on Computational Geometry.'
chicago: Aichholzer, Oswin, Hugo A Akitaya, Kenneth C Cheung, Erik D Demaine, Martin
L Demaine, Sandor P Fekete, Linda Kleist, et al. “Folding Polyominoes with Holes
into a Cube.” In *Proceedings of the 31st Canadian Conference on Computational
Geometry*, 164–70. Canadian Conference on Computational Geometry, 2019.
ieee: O. Aichholzer *et al.*, “Folding polyominoes with holes into a cube,”
in *Proceedings of the 31st Canadian Conference on Computational Geometry*,
Edmonton, Canada, 2019, pp. 164–170.
ista: 'Aichholzer O, Akitaya HA, Cheung KC, Demaine ED, Demaine ML, Fekete SP, Kleist
L, Kostitsyna I, Löffler M, Masárová Z, Mundilova K, Schmidt C. 2019. Folding
polyominoes with holes into a cube. Proceedings of the 31st Canadian Conference
on Computational Geometry. CCCG: Canadian Conference in Computational Geometry
164–170.'
mla: Aichholzer, Oswin, et al. “Folding Polyominoes with Holes into a Cube.” *Proceedings
of the 31st Canadian Conference on Computational Geometry*, Canadian Conference
on Computational Geometry, 2019, pp. 164–70.
short: O. Aichholzer, H.A. Akitaya, K.C. Cheung, E.D. Demaine, M.L. Demaine, S.P.
Fekete, L. Kleist, I. Kostitsyna, M. Löffler, Z. Masárová, K. Mundilova, C. Schmidt,
in:, Proceedings of the 31st Canadian Conference on Computational Geometry, Canadian
Conference on Computational Geometry, 2019, pp. 164–170.
conference:
end_date: 2019-08-10
location: Edmonton, Canada
name: 'CCCG: Canadian Conference in Computational Geometry'
start_date: 2019-08-08
date_created: 2019-11-04T16:46:11Z
date_published: 2019-08-01T00:00:00Z
date_updated: 2019-11-04T16:47:48Z
day: '01'
department:
- _id: HeEd
external_id:
arxiv:
- '1910.09917'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1910.09917
month: '08'
oa: 1
oa_version: Preprint
page: 164-170
publication: Proceedings of the 31st Canadian Conference on Computational Geometry
publication_status: published
publisher: Canadian Conference on Computational Geometry
quality_controlled: '1'
status: public
title: Folding polyominoes with holes into a cube
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2019'
...
---
_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:49. 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, p. 49). 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,” 77:49. 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, p. 49.'
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. 49.'
mla: Lubiw, Anna, et al. *A Proof of the Orbit Conjecture for Flipping Edge Labelled
Triangulations*. Vol. 77, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2017, p. 49, doi:10.4230/LIPIcs.SoCG.2017.49.
short: A. Lubiw, Z. Masárová, U. Wagner, in:, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2017, p. 49.
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-09-24T07:18:41Z
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: 1
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: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 77
year: '2017'
...