[{"intvolume":" 61","file_date_updated":"2019-02-14T11:57:22Z","date_created":"2019-02-14T11:54:08Z","title":"A Proof of the Orbit Conjecture for Flipping Edge-Labelled Triangulations","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_published":"2019-06-01T00:00:00Z","quality_controlled":"1","status":"public","file":[{"file_size":556276,"creator":"dernst","file_name":"2018_DiscreteGeometry_Lubiw.pdf","success":1,"file_id":"5988","date_updated":"2019-02-14T11:57:22Z","relation":"main_file","open_access":1,"content_type":"application/pdf","date_created":"2019-02-14T11:57:22Z","access_level":"open_access"}],"related_material":{"record":[{"id":"683","status":"public","relation":"earlier_version"}]},"year":"2019","month":"06","ddc":["000"],"issue":"4","accept":"1","author":[{"first_name":"Anna","full_name":"Lubiw, Anna","last_name":"Lubiw"},{"id":"45CFE238-F248-11E8-B48F-1D18A9856A87","last_name":"Masárová","full_name":"Masárová, Zuzana","orcid":"0000-0002-6660-1322","first_name":"Zuzana"},{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","full_name":"Wagner, Uli","last_name":"Wagner","orcid":"0000-0002-1494-0568","first_name":"Uli"}],"department":[{"_id":"UlWa"}],"page":"880-898","volume":61,"article_type":"original","oa_version":"Published Version","publication_status":"published","_id":"5986","publication":"Discrete & Computational Geometry","cc_license":"'https://creativecommons.org/licenses/by/4.0/'","external_id":{"arxiv":["1710.02741"]},"doi":"10.1007/s00454-018-0035-8","day":"01","publication_identifier":{"issn":["0179-5376","1432-0444"]},"type":"journal_article","publisher":"Springer Nature","citation":{"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.","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.","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","short":"A. Lubiw, Z. Masárová, U. Wagner, Discrete & Computational Geometry 61 (2019) 880–898.","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","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.","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."},"language":[{"iso":"eng"}],"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 𝑂(𝑛8) 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 𝑂(𝑛7) 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."}],"date_updated":"2019-11-14T08:43:40Z","project":[{"name":"IST Austria Open Access Fund","_id":"BFDF9788-01D1-11E9-AC17-EBD7A21D5664"}]},{"abstract":[{"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. ","lang":"eng"}],"language":[{"iso":"eng"}],"date_updated":"2019-11-14T08:43:44Z","publication_status":"published","oa":1,"oa_version":"Preprint","conference":{"name":"CCCG: Canadian Conference in Computational Geometry","end_date":"2019-08-10","start_date":"2019-08-08","location":"Edmonton, Canada"},"type":"conference","publisher":"Canadian Conference on Computational Geometry","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1910.09917"}],"citation":{"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.","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.","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.","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.","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.","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."},"department":[{"_id":"HeEd"}],"author":[{"last_name":"Aichholzer","full_name":"Aichholzer, Oswin","first_name":"Oswin"},{"first_name":"Hugo A","last_name":"Akitaya","full_name":"Akitaya, Hugo A"},{"first_name":"Kenneth C","full_name":"Cheung, Kenneth C","last_name":"Cheung"},{"last_name":"Demaine","full_name":"Demaine, Erik D","first_name":"Erik D"},{"first_name":"Martin L","last_name":"Demaine","full_name":"Demaine, Martin L"},{"full_name":"Fekete, Sandor P","last_name":"Fekete","first_name":"Sandor P"},{"last_name":"Kleist","full_name":"Kleist, Linda","first_name":"Linda"},{"last_name":"Kostitsyna","full_name":"Kostitsyna, Irina","first_name":"Irina"},{"full_name":"Löffler, Maarten","last_name":"Löffler","first_name":"Maarten"},{"first_name":"Zuzana","orcid":"0000-0002-6660-1322","id":"45CFE238-F248-11E8-B48F-1D18A9856A87","last_name":"Masárová","full_name":"Masárová, Zuzana"},{"full_name":"Mundilova, Klara","last_name":"Mundilova","first_name":"Klara"},{"full_name":"Schmidt, Christiane","last_name":"Schmidt","first_name":"Christiane"}],"page":"164-170","status":"public","month":"08","day":"01","year":"2019","date_created":"2019-11-04T16:46:11Z","title":"Folding polyominoes with holes into a cube","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","external_id":{"arxiv":["1910.09917"]},"_id":"6989","publication":"Proceedings of the 31st Canadian Conference on Computational Geometry","date_published":"2019-08-01T00:00:00Z","quality_controlled":"1"},{"abstract":[{"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.","lang":"eng"}],"publist_id":"7033","language":[{"iso":"eng"}],"oa":1,"date_updated":"2019-11-14T08:43:40Z","conference":{"location":"Brisbane, Australia","start_date":"2017-07-04","name":"SoCG: Symposium on Computational Geometry","end_date":"2017-07-07"},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","type":"conference","article_number":"49","citation":{"short":"A. Lubiw, Z. Masárová, U. Wagner, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, p. 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","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.","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","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.","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."},"day":"01","cc_license":"'https://creativecommons.org/licenses/by/4.0/'","_id":"683","doi":"10.4230/LIPIcs.SoCG.2017.49","alternative_title":["LIPIcs"],"oa_version":"Published Version","publication_status":"published","accept":"1","volume":77,"author":[{"last_name":"Lubiw","full_name":"Lubiw, Anna","first_name":"Anna"},{"orcid":"0000-0002-6660-1322","first_name":"Zuzana","id":"45CFE238-F248-11E8-B48F-1D18A9856A87","last_name":"Masárová","full_name":"Masárová, Zuzana"},{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","full_name":"Wagner, Uli","last_name":"Wagner","orcid":"0000-0002-1494-0568","first_name":"Uli"}],"department":[{"_id":"UlWa"}],"file":[{"file_id":"5265","date_updated":"2018-12-12T10:17:12Z","file_size":710007,"creator":"system","file_name":"IST-2017-896-v1+1_LIPIcs-SoCG-2017-49.pdf","open_access":1,"relation":"main_file","access_level":"open_access","date_created":"2018-12-12T10:17:12Z","content_type":"application/pdf"}],"pubrep_id":"896","status":"public","ddc":["514","516"],"month":"06","related_material":{"record":[{"id":"5986","status":"public","relation":"later_version"}]},"year":"2017","title":"A proof of the orbit conjecture for flipping edge labelled triangulations","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_created":"2018-12-11T11:47:54Z","file_date_updated":"2018-12-12T10:17:12Z","intvolume":" 77","quality_controlled":"1","date_published":"2017-06-01T00:00:00Z"}]