[{"abstract":[{"text":"We solve a problem of Dujmović and Wood (2007) by showing that a complete convex geometric graph on n vertices cannot be decomposed into fewer than n - 1 star-forests, each consisting of noncrossing edges. This bound is clearly tight. We also discuss similar questions for abstract graphs.","lang":"eng"}],"intvolume":"       129","publisher":"Elsevier","date_published":"2025-12-01T00:00:00Z","OA_place":"repository","publication":"Computational Geometry","quality_controlled":"1","corr_author":"1","article_processing_charge":"No","acknowledgement":"A preliminary version of this note has been published in the proceedings of the 31st International Symposium on Graph Drawing and Network Visualization, Palermo, 2023. The authors would like to thank the anonymous referees for their valuable comments.","arxiv":1,"type":"journal_article","department":[{"_id":"HeEd"}],"related_material":{"record":[{"id":"15012","status":"public","relation":"earlier_version"}]},"volume":129,"main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2306.13201"}],"year":"2025","date_updated":"2026-10-02T11:50:58Z","author":[{"last_name":"Pach","full_name":"Pach, János","first_name":"János"},{"last_name":"Saghafian","id":"f86f7148-b140-11ec-9577-95435b8df824","full_name":"Saghafian, Morteza","first_name":"Morteza"},{"last_name":"Schnider","full_name":"Schnider, Patrick","first_name":"Patrick"}],"external_id":{"arxiv":["2306.13201"]},"oa":1,"article_type":"original","doi":"10.1016/j.comgeo.2025.102186","language":[{"iso":"eng"}],"date_created":"2026-02-16T15:48:42Z","publication_identifier":{"issn":["0925-7721"]},"status":"public","month":"12","day":"01","citation":{"mla":"Pach, János, et al. “Decomposition of Geometric Graphs into Star-Forests.” <i>Computational Geometry</i>, vol. 129, 102186, Elsevier, 2025, doi:<a href=\"https://doi.org/10.1016/j.comgeo.2025.102186\">10.1016/j.comgeo.2025.102186</a>.","short":"J. Pach, M. Saghafian, P. Schnider, Computational Geometry 129 (2025).","ieee":"J. Pach, M. Saghafian, and P. Schnider, “Decomposition of geometric graphs into star-forests,” <i>Computational Geometry</i>, vol. 129. Elsevier, 2025.","apa":"Pach, J., Saghafian, M., &#38; Schnider, P. (2025). Decomposition of geometric graphs into star-forests. <i>Computational Geometry</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.comgeo.2025.102186\">https://doi.org/10.1016/j.comgeo.2025.102186</a>","ista":"Pach J, Saghafian M, Schnider P. 2025. Decomposition of geometric graphs into star-forests. Computational Geometry. 129, 102186.","ama":"Pach J, Saghafian M, Schnider P. Decomposition of geometric graphs into star-forests. <i>Computational Geometry</i>. 2025;129. doi:<a href=\"https://doi.org/10.1016/j.comgeo.2025.102186\">10.1016/j.comgeo.2025.102186</a>","chicago":"Pach, János, Morteza Saghafian, and Patrick Schnider. “Decomposition of Geometric Graphs into Star-Forests.” <i>Computational Geometry</i>. Elsevier, 2025. <a href=\"https://doi.org/10.1016/j.comgeo.2025.102186\">https://doi.org/10.1016/j.comgeo.2025.102186</a>."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_number":"102186","fulldoi":"https://doi.org/10.1016/j.comgeo.2025.102186","title":"Decomposition of geometric graphs into star-forests","_id":"21253","OA_type":"green","publication_status":"published","oa_version":"Preprint"},{"month":"02","status":"public","date_created":"2020-08-30T22:01:09Z","publication_identifier":{"eissn":["1879-081X"],"issn":["0925-7721"]},"article_type":"original","language":[{"iso":"eng"}],"doi":"10.1016/j.comgeo.2020.101700","project":[{"grant_number":"Z00342","call_identifier":"FWF","_id":"268116B8-B435-11E9-9278-68D0E5697425","name":"Mathematics, Computer Science"}],"oa":1,"external_id":{"arxiv":["1910.09917"],"isi":["000579185100004"]},"oa_version":"Preprint","publication_status":"published","_id":"8317","fulldoi":"https://doi.org/10.1016/j.comgeo.2020.101700","article_number":"101700","title":"Folding polyominoes with holes into a cube","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","citation":{"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, Computational Geometry: Theory and Applications 93 (2021).","mla":"Aichholzer, Oswin, et al. “Folding Polyominoes with Holes into a Cube.” <i>Computational Geometry: Theory and Applications</i>, vol. 93, 101700, Elsevier, 2021, doi:<a href=\"https://doi.org/10.1016/j.comgeo.2020.101700\">10.1016/j.comgeo.2020.101700</a>.","apa":"Aichholzer, O., Akitaya, H. A., Cheung, K. C., Demaine, E. D., Demaine, M. L., Fekete, S. P., … Schmidt, C. (2021). Folding polyominoes with holes into a cube. <i>Computational Geometry: Theory and Applications</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.comgeo.2020.101700\">https://doi.org/10.1016/j.comgeo.2020.101700</a>","ieee":"O. Aichholzer <i>et al.</i>, “Folding polyominoes with holes into a cube,” <i>Computational Geometry: Theory and Applications</i>, vol. 93. Elsevier, 2021.","chicago":"Aichholzer, Oswin, Hugo A. Akitaya, Kenneth C. Cheung, Erik D. Demaine, Martin L. Demaine, Sándor P. Fekete, Linda Kleist, et al. “Folding Polyominoes with Holes into a Cube.” <i>Computational Geometry: Theory and Applications</i>. Elsevier, 2021. <a href=\"https://doi.org/10.1016/j.comgeo.2020.101700\">https://doi.org/10.1016/j.comgeo.2020.101700</a>.","ama":"Aichholzer O, Akitaya HA, Cheung KC, et al. Folding polyominoes with holes into a cube. <i>Computational Geometry: Theory and Applications</i>. 2021;93. doi:<a href=\"https://doi.org/10.1016/j.comgeo.2020.101700\">10.1016/j.comgeo.2020.101700</a>","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. 2021. Folding polyominoes with holes into a cube. Computational Geometry: Theory and Applications. 93, 101700."},"day":"01","corr_author":"1","quality_controlled":"1","publication":"Computational Geometry: Theory and Applications","date_published":"2021-02-01T00:00:00Z","publisher":"Elsevier","intvolume":"        93","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 one or several holes to fold into a cube, and conditions under which cube folding is impossible. In particular, we show that all but five special “basic” holes guarantee foldability."}],"author":[{"first_name":"Oswin","full_name":"Aichholzer, Oswin","last_name":"Aichholzer"},{"first_name":"Hugo A.","full_name":"Akitaya, Hugo A.","last_name":"Akitaya"},{"last_name":"Cheung","first_name":"Kenneth C.","full_name":"Cheung, Kenneth C."},{"full_name":"Demaine, Erik D.","first_name":"Erik D.","last_name":"Demaine"},{"first_name":"Martin L.","full_name":"Demaine, Martin L.","last_name":"Demaine"},{"last_name":"Fekete","full_name":"Fekete, Sándor P.","first_name":"Sándor P."},{"first_name":"Linda","full_name":"Kleist, Linda","last_name":"Kleist"},{"full_name":"Kostitsyna, Irina","first_name":"Irina","last_name":"Kostitsyna"},{"full_name":"Löffler, Maarten","first_name":"Maarten","last_name":"Löffler"},{"full_name":"Masárová, Zuzana","first_name":"Zuzana","orcid":"0000-0002-6660-1322","last_name":"Masárová","id":"45CFE238-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Mundilova","full_name":"Mundilova, Klara","first_name":"Klara"},{"first_name":"Christiane","full_name":"Schmidt, Christiane","last_name":"Schmidt"}],"date_updated":"2026-07-28T13:08:48Z","year":"2021","isi":1,"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1910.09917v3"}],"related_material":{"record":[{"relation":"shorter_version","status":"public","id":"6989"}]},"department":[{"_id":"HeEd"}],"volume":93,"type":"journal_article","scopus_import":"1","arxiv":1,"acknowledgement":"This research was performed in part at the 33rd Bellairs Winter Workshop on Computational Geometry. We thank all other participants for a fruitful atmosphere. H. Akitaya was supported by NSF CCF-1422311 & 1423615. Z. Masárová was partially funded by Wittgenstein Prize, Austrian Science Fund (FWF), grant no. Z 342-N31.","article_processing_charge":"No"},{"article_processing_charge":"No","arxiv":1,"department":[{"_id":"UlWa"}],"volume":66,"type":"journal_article","year":"2017","date_updated":"2026-04-16T09:57:17Z","author":[{"id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","last_name":"Fulek","orcid":"0000-0001-8485-1774","full_name":"Fulek, Radoslav","first_name":"Radoslav"},{"last_name":"Mojarrad","first_name":"Hossein","full_name":"Mojarrad, Hossein"},{"last_name":"Naszódi","full_name":"Naszódi, Márton","first_name":"Márton"},{"full_name":"Solymosi, József","first_name":"József","last_name":"Solymosi"},{"full_name":"Stich, Sebastian","first_name":"Sebastian","last_name":"Stich"},{"full_name":"Szedlák, May","first_name":"May","last_name":"Szedlák"}],"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1701.08183"}],"isi":1,"abstract":[{"lang":"eng","text":"Let P be a finite point set in the plane. A cordinary triangle in P is a subset of P consisting of three non-collinear points such that each of the three lines determined by the three points contains at most c points of P . Motivated by a question of Erdös, and answering a question of de Zeeuw, we prove that there exists a constant c &gt; 0such that P contains a c-ordinary triangle, provided that P is not contained in the union of two lines. Furthermore, the number of c-ordinary triangles in P is Ω(| P |). "}],"publisher":"Elsevier","intvolume":"        66","date_published":"2017-01-01T00:00:00Z","publication":"Computational Geometry: Theory and Applications","quality_controlled":"1","day":"01","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","ec_funded":1,"citation":{"short":"R. Fulek, H. Mojarrad, M. Naszódi, J. Solymosi, S. Stich, M. Szedlák, Computational Geometry: Theory and Applications 66 (2017) 28–31.","mla":"Fulek, Radoslav, et al. “On the Existence of Ordinary Triangles.” <i>Computational Geometry: Theory and Applications</i>, vol. 66, Elsevier, 2017, pp. 28–31, doi:<a href=\"https://doi.org/10.1016/j.comgeo.2017.07.002\">10.1016/j.comgeo.2017.07.002</a>.","ieee":"R. Fulek, H. Mojarrad, M. Naszódi, J. Solymosi, S. Stich, and M. Szedlák, “On the existence of ordinary triangles,” <i>Computational Geometry: Theory and Applications</i>, vol. 66. Elsevier, pp. 28–31, 2017.","apa":"Fulek, R., Mojarrad, H., Naszódi, M., Solymosi, J., Stich, S., &#38; Szedlák, M. (2017). On the existence of ordinary triangles. <i>Computational Geometry: Theory and Applications</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.comgeo.2017.07.002\">https://doi.org/10.1016/j.comgeo.2017.07.002</a>","ista":"Fulek R, Mojarrad H, Naszódi M, Solymosi J, Stich S, Szedlák M. 2017. On the existence of ordinary triangles. Computational Geometry: Theory and Applications. 66, 28–31.","chicago":"Fulek, Radoslav, Hossein Mojarrad, Márton Naszódi, József Solymosi, Sebastian Stich, and May Szedlák. “On the Existence of Ordinary Triangles.” <i>Computational Geometry: Theory and Applications</i>. Elsevier, 2017. <a href=\"https://doi.org/10.1016/j.comgeo.2017.07.002\">https://doi.org/10.1016/j.comgeo.2017.07.002</a>.","ama":"Fulek R, Mojarrad H, Naszódi M, Solymosi J, Stich S, Szedlák M. On the existence of ordinary triangles. <i>Computational Geometry: Theory and Applications</i>. 2017;66:28-31. doi:<a href=\"https://doi.org/10.1016/j.comgeo.2017.07.002\">10.1016/j.comgeo.2017.07.002</a>"},"title":"On the existence of ordinary triangles","fulldoi":"https://doi.org/10.1016/j.comgeo.2017.07.002","_id":"793","oa_version":"Submitted Version","publication_status":"published","project":[{"_id":"25681D80-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"291734","name":"International IST Postdoc Fellowship Programme"}],"page":"28 - 31","external_id":{"arxiv":["1701.08183"],"isi":["000412039700003"]},"oa":1,"doi":"10.1016/j.comgeo.2017.07.002","language":[{"iso":"eng"}],"publist_id":"6861","publication_identifier":{"issn":["0925-7721"]},"date_created":"2018-12-11T11:48:32Z","status":"public","month":"01"},{"type":"journal_article","volume":41,"year":"2008","date_updated":"2026-05-29T09:15:13Z","author":[{"last_name":"Edelsbrunner","orcid":"0000-0002-9823-6833","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","first_name":"Herbert","full_name":"Edelsbrunner, Herbert"},{"last_name":"Harer","first_name":"John","full_name":"Harer, John"},{"last_name":"Mascarenhas","full_name":"Mascarenhas, Ajith","first_name":"Ajith"},{"full_name":"Pascucci, Valerio","first_name":"Valerio","last_name":"Pascucci"},{"last_name":"Snoeyink","first_name":"Jack","full_name":"Snoeyink, Jack"}],"article_processing_charge":"No","extern":"1","date_published":"2008-11-01T00:00:00Z","publication":"Computational Geometry: Theory and Applications","abstract":[{"text":"The Reeb graph is a useful tool in visualizing real-valued data obtained from computational simulations of physical processes. We characterize the evolution of the Reeb graph of a time-varying continuous function defined in three-dimensional space. We show how to maintain the Reeb graph over time and compress the entire sequence of Reeb graphs into a single, partially persistent data structure, and augment this data structure with Betti numbers to describe the topology of level sets and with path seeds to assist in the fast extraction of level sets for visualization.","lang":"eng"}],"intvolume":"        41","publisher":"Elsevier","fulldoi":"https://doi.org/10.1016/j.comgeo.2007.11.001","title":"Time-varying Reeb graphs for continuous space-time data","_id":"3971","publication_status":"published","OA_type":"free access","oa_version":"None","day":"01","citation":{"apa":"Edelsbrunner, H., Harer, J., Mascarenhas, A., Pascucci, V., &#38; Snoeyink, J. (2008). Time-varying Reeb graphs for continuous space-time data. <i>Computational Geometry: Theory and Applications</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.comgeo.2007.11.001\">https://doi.org/10.1016/j.comgeo.2007.11.001</a>","ieee":"H. Edelsbrunner, J. Harer, A. Mascarenhas, V. Pascucci, and J. Snoeyink, “Time-varying Reeb graphs for continuous space-time data,” <i>Computational Geometry: Theory and Applications</i>, vol. 41, no. 3. Elsevier, pp. 149–166, 2008.","short":"H. Edelsbrunner, J. Harer, A. Mascarenhas, V. Pascucci, J. Snoeyink, Computational Geometry: Theory and Applications 41 (2008) 149–166.","mla":"Edelsbrunner, Herbert, et al. “Time-Varying Reeb Graphs for Continuous Space-Time Data.” <i>Computational Geometry: Theory and Applications</i>, vol. 41, no. 3, Elsevier, 2008, pp. 149–66, doi:<a href=\"https://doi.org/10.1016/j.comgeo.2007.11.001\">10.1016/j.comgeo.2007.11.001</a>.","ama":"Edelsbrunner H, Harer J, Mascarenhas A, Pascucci V, Snoeyink J. Time-varying Reeb graphs for continuous space-time data. <i>Computational Geometry: Theory and Applications</i>. 2008;41(3):149-166. doi:<a href=\"https://doi.org/10.1016/j.comgeo.2007.11.001\">10.1016/j.comgeo.2007.11.001</a>","chicago":"Edelsbrunner, Herbert, John Harer, Ajith Mascarenhas, Valerio Pascucci, and Jack Snoeyink. “Time-Varying Reeb Graphs for Continuous Space-Time Data.” <i>Computational Geometry: Theory and Applications</i>. Elsevier, 2008. <a href=\"https://doi.org/10.1016/j.comgeo.2007.11.001\">https://doi.org/10.1016/j.comgeo.2007.11.001</a>.","ista":"Edelsbrunner H, Harer J, Mascarenhas A, Pascucci V, Snoeyink J. 2008. Time-varying Reeb graphs for continuous space-time data. Computational Geometry: Theory and Applications. 41(3), 149–166."},"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","publist_id":"2158","publication_identifier":{"eissn":["1879-081X"],"issn":["0925-7721"]},"date_created":"2018-12-11T12:06:12Z","status":"public","issue":"3","month":"11","page":"149 - 166","article_type":"original","language":[{"iso":"eng"}],"doi":"10.1016/j.comgeo.2007.11.001"},{"quality_controlled":"1","publication":"Computational Geometry: Theory and Applications","date_published":"2001-07-01T00:00:00Z","intvolume":"        19","publisher":"Elsevier","abstract":[{"text":"The construction of shape spaces is studied from a mathematical and a computational viewpoint. A program is outlined reducing the problem to four tasks: the representation of geometry, the canonical deformation of geometry, the measuring of distance in shape space, and the selection of base shapes. The technical part of this paper focuses on the second task: the specification of a deformation mixing two or more shapes in continuously changing proportions. (C) 2001 Elsevier Science B.V All rights reserved.","lang":"eng"}],"author":[{"last_name":"Cheng","first_name":"Ho","full_name":"Cheng, Ho"},{"first_name":"Herbert","full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Ping","full_name":"Fu, Ping","last_name":"Fu"}],"date_updated":"2023-05-10T12:57:14Z","year":"2001","type":"journal_article","scopus_import":"1","volume":19,"acknowledgement":"National Science Foundation under grants CCR-96-19542 and CCR-97-12088, and by the Army Research Office under grant DAAG55-98-1-0177.","extern":"1","article_processing_charge":"No","issue":"2-3","month":"07","status":"public","publist_id":"2123","date_created":"2018-12-11T12:06:22Z","publication_identifier":{"issn":["0925-7721"]},"doi":"10.1016/S0925-7721(01)00021-9","language":[{"iso":"eng"}],"article_type":"original","page":"191 - 204","publication_status":"published","oa_version":"None","_id":"4001","fulldoi":"https://doi.org/10.1016/S0925-7721(01)00021-9","title":"Shape space from deformation","citation":{"apa":"Cheng, H., Edelsbrunner, H., &#38; Fu, P. (2001). Shape space from deformation. <i>Computational Geometry: Theory and Applications</i>. Elsevier. <a href=\"https://doi.org/10.1016/S0925-7721(01)00021-9\">https://doi.org/10.1016/S0925-7721(01)00021-9</a>","ieee":"H. Cheng, H. Edelsbrunner, and P. Fu, “Shape space from deformation,” <i>Computational Geometry: Theory and Applications</i>, vol. 19, no. 2–3. Elsevier, pp. 191–204, 2001.","mla":"Cheng, Ho, et al. “Shape Space from Deformation.” <i>Computational Geometry: Theory and Applications</i>, vol. 19, no. 2–3, Elsevier, 2001, pp. 191–204, doi:<a href=\"https://doi.org/10.1016/S0925-7721(01)00021-9\">10.1016/S0925-7721(01)00021-9</a>.","short":"H. Cheng, H. Edelsbrunner, P. Fu, Computational Geometry: Theory and Applications 19 (2001) 191–204.","chicago":"Cheng, Ho, Herbert Edelsbrunner, and Ping Fu. “Shape Space from Deformation.” <i>Computational Geometry: Theory and Applications</i>. Elsevier, 2001. <a href=\"https://doi.org/10.1016/S0925-7721(01)00021-9\">https://doi.org/10.1016/S0925-7721(01)00021-9</a>.","ama":"Cheng H, Edelsbrunner H, Fu P. Shape space from deformation. <i>Computational Geometry: Theory and Applications</i>. 2001;19(2-3):191-204. doi:<a href=\"https://doi.org/10.1016/S0925-7721(01)00021-9\">10.1016/S0925-7721(01)00021-9</a>","ista":"Cheng H, Edelsbrunner H, Fu P. 2001. Shape space from deformation. Computational Geometry: Theory and Applications. 19(2–3), 191–204."},"user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","day":"01"},{"user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","citation":{"ista":"Cheng S, Edelsbrunner H, Fu P, Lam K. 2001. Design and analysis of planar shape deformation. Computational Geometry: Theory and Applications. 19(2–3), 205–218.","chicago":"Cheng, Siu, Herbert Edelsbrunner, Ping Fu, and Ka Lam. “Design and Analysis of Planar Shape Deformation.” <i>Computational Geometry: Theory and Applications</i>. Elsevier, 2001. <a href=\"https://doi.org/10.1016/S0925-7721(01)00020-7\">https://doi.org/10.1016/S0925-7721(01)00020-7</a>.","ama":"Cheng S, Edelsbrunner H, Fu P, Lam K. Design and analysis of planar shape deformation. <i>Computational Geometry: Theory and Applications</i>. 2001;19(2-3):205-218. doi:<a href=\"https://doi.org/10.1016/S0925-7721(01)00020-7\">10.1016/S0925-7721(01)00020-7</a>","short":"S. Cheng, H. Edelsbrunner, P. Fu, K. Lam, Computational Geometry: Theory and Applications 19 (2001) 205–218.","mla":"Cheng, Siu, et al. “Design and Analysis of Planar Shape Deformation.” <i>Computational Geometry: Theory and Applications</i>, vol. 19, no. 2–3, Elsevier, 2001, pp. 205–18, doi:<a href=\"https://doi.org/10.1016/S0925-7721(01)00020-7\">10.1016/S0925-7721(01)00020-7</a>.","ieee":"S. Cheng, H. Edelsbrunner, P. Fu, and K. Lam, “Design and analysis of planar shape deformation,” <i>Computational Geometry: Theory and Applications</i>, vol. 19, no. 2–3. Elsevier, pp. 205–218, 2001.","apa":"Cheng, S., Edelsbrunner, H., Fu, P., &#38; Lam, K. (2001). Design and analysis of planar shape deformation. <i>Computational Geometry: Theory and Applications</i>. Elsevier. <a href=\"https://doi.org/10.1016/S0925-7721(01)00020-7\">https://doi.org/10.1016/S0925-7721(01)00020-7</a>"},"day":"01","oa_version":"None","publication_status":"published","fulldoi":"https://doi.org/10.1016/S0925-7721(01)00020-7","title":"Design and analysis of planar shape deformation","_id":"4002","doi":"10.1016/S0925-7721(01)00020-7","language":[{"iso":"eng"}],"article_type":"original","page":"205 - 218","month":"07","issue":"2-3","publist_id":"2124","publication_identifier":{"issn":["0925-7721"]},"date_created":"2018-12-11T12:06:22Z","status":"public","extern":"1","acknowledgement":"NSF under grants CCR-96-19542 and CCR-97-12088.","article_processing_charge":"No","year":"2001","date_updated":"2023-05-10T14:21:31Z","author":[{"last_name":"Cheng","full_name":"Cheng, Siu","first_name":"Siu"},{"full_name":"Edelsbrunner, Herbert","first_name":"Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner"},{"last_name":"Fu","first_name":"Ping","full_name":"Fu, Ping"},{"last_name":"Lam","first_name":"Ka","full_name":"Lam, Ka"}],"volume":19,"scopus_import":"1","type":"journal_article","publisher":"Elsevier","intvolume":"        19","abstract":[{"lang":"eng","text":"Shape deformation refers to the continuous change of one geometric object to another. We develop a software tool for planning, analyzing and visualizing deformations between two shapes in R-2. The deformation is generated automatically without any user intervention or specification of feature correspondences. A unique property of the tool is the explicit availability of a two-dimensional shape space, which can be used for designing the deformation either automatically by following constraints and objectives or manually by drawing deformation paths."}],"quality_controlled":"1","date_published":"2001-07-01T00:00:00Z","publication":"Computational Geometry: Theory and Applications"},{"article_processing_charge":"No","extern":"1","acknowledgement":"Partially supported by the National Science Foundation, under grant ASC-200301 and the Alan T. Waterman award, grant CCR-9118874.","volume":7,"type":"journal_article","scopus_import":"1","date_updated":"2022-08-19T08:32:23Z","author":[{"orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","full_name":"Edelsbrunner, Herbert","first_name":"Herbert"},{"first_name":"Nimish","full_name":"Shah, Nimish","last_name":"Shah"}],"year":"1997","abstract":[{"lang":"eng","text":"Given a subspace X subset of or equal to R-d and a finite set S subset of or equal to R-d, we introduce the Delaunay complex, D-X, restricted by X. Its simplices are spanned by subsets T subset of or equal to S for which the common intersection of Voronoi cells meets X in a non-empty set. By the nerve theorem, boolean OR D-X and X are homotopy equivalent if all such sets are contractible. This paper proves a sufficient condition for boolean OR D-X and X be homeomorphic."}],"publisher":"World Scientific Publishing","intvolume":"         7","publication":"International Journal of Computational Geometry & Applications","date_published":"1997-01-01T00:00:00Z","quality_controlled":"1","day":"01","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","citation":{"apa":"Edelsbrunner, H., &#38; Shah, N. (1997). Triangulating topological spaces. <i>International Journal of Computational Geometry &#38; Applications</i>. World Scientific Publishing. <a href=\"https://doi.org/10.1142/S0218195997000223\">https://doi.org/10.1142/S0218195997000223</a>","ieee":"H. Edelsbrunner and N. Shah, “Triangulating topological spaces,” <i>International Journal of Computational Geometry &#38; Applications</i>, vol. 7, no. 4. World Scientific Publishing, pp. 365–378, 1997.","mla":"Edelsbrunner, Herbert, and Nimish Shah. “Triangulating Topological Spaces.” <i>International Journal of Computational Geometry &#38; Applications</i>, vol. 7, no. 4, World Scientific Publishing, 1997, pp. 365–78, doi:<a href=\"https://doi.org/10.1142/S0218195997000223\">10.1142/S0218195997000223</a>.","short":"H. Edelsbrunner, N. Shah, International Journal of Computational Geometry &#38; Applications 7 (1997) 365–378.","chicago":"Edelsbrunner, Herbert, and Nimish Shah. “Triangulating Topological Spaces.” <i>International Journal of Computational Geometry &#38; Applications</i>. World Scientific Publishing, 1997. <a href=\"https://doi.org/10.1142/S0218195997000223\">https://doi.org/10.1142/S0218195997000223</a>.","ama":"Edelsbrunner H, Shah N. Triangulating topological spaces. <i>International Journal of Computational Geometry &#38; Applications</i>. 1997;7(4):365-378. doi:<a href=\"https://doi.org/10.1142/S0218195997000223\">10.1142/S0218195997000223</a>","ista":"Edelsbrunner H, Shah N. 1997. Triangulating topological spaces. International Journal of Computational Geometry &#38; Applications. 7(4), 365–378."},"_id":"4018","fulldoi":"https://doi.org/10.1142/S0218195997000223","title":"Triangulating topological spaces","oa_version":"None","publication_status":"published","page":"365 - 378","language":[{"iso":"eng"}],"doi":"10.1142/S0218195997000223","article_type":"original","status":"public","date_created":"2018-12-11T12:06:28Z","publication_identifier":{"issn":["0925-7721"]},"publist_id":"2106","month":"01","issue":"4"},{"user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","citation":{"mla":"Edelsbrunner, Herbert, and Roman Waupotitsch. “A Combinatorial Approach to Cartograms.” <i>Computational Geometry: Theory and Applications</i>, vol. 7, no. 5–6, Elsevier, 1997, pp. 343–60, doi:<a href=\"https://doi.org/10.1016/S0925-7721(96)00006-5\">10.1016/S0925-7721(96)00006-5</a>.","short":"H. Edelsbrunner, R. Waupotitsch, Computational Geometry: Theory and Applications 7 (1997) 343–360.","apa":"Edelsbrunner, H., &#38; Waupotitsch, R. (1997). A combinatorial approach to cartograms. <i>Computational Geometry: Theory and Applications</i>. Elsevier. <a href=\"https://doi.org/10.1016/S0925-7721(96)00006-5\">https://doi.org/10.1016/S0925-7721(96)00006-5</a>","ieee":"H. Edelsbrunner and R. Waupotitsch, “A combinatorial approach to cartograms,” <i>Computational Geometry: Theory and Applications</i>, vol. 7, no. 5–6. Elsevier, pp. 343–360, 1997.","ama":"Edelsbrunner H, Waupotitsch R. A combinatorial approach to cartograms. <i>Computational Geometry: Theory and Applications</i>. 1997;7(5-6):343-360. doi:<a href=\"https://doi.org/10.1016/S0925-7721(96)00006-5\">10.1016/S0925-7721(96)00006-5</a>","chicago":"Edelsbrunner, Herbert, and Roman Waupotitsch. “A Combinatorial Approach to Cartograms.” <i>Computational Geometry: Theory and Applications</i>. Elsevier, 1997. <a href=\"https://doi.org/10.1016/S0925-7721(96)00006-5\">https://doi.org/10.1016/S0925-7721(96)00006-5</a>.","ista":"Edelsbrunner H, Waupotitsch R. 1997. A combinatorial approach to cartograms. Computational Geometry: Theory and Applications. 7(5–6), 343–360."},"day":"01","oa_version":"Published Version","publication_status":"published","_id":"4021","title":"A combinatorial approach to cartograms","fulldoi":"https://doi.org/10.1016/S0925-7721(96)00006-5","language":[{"iso":"eng"}],"doi":"10.1016/S0925-7721(96)00006-5","article_type":"original","oa":1,"page":"343 - 360","month":"04","popular_science":"1","issue":"5-6","status":"public","date_created":"2018-12-11T12:06:29Z","publist_id":"2105","publication_identifier":{"issn":["0925-7721"]},"acknowledgement":"The authors thank Jack Snoeyink for bringing the cartogram problem to their attention, and Michael McAllister for providing pointers to the literature on cartograms. ","article_processing_charge":"No","extern":"1","date_updated":"2022-08-19T08:12:03Z","author":[{"first_name":"Herbert","full_name":"Edelsbrunner, Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","last_name":"Edelsbrunner","orcid":"0000-0002-9823-6833"},{"last_name":"Waupotitsch","first_name":"Roman","full_name":"Waupotitsch, Roman"}],"year":"1997","main_file_link":[{"url":"https://www.sciencedirect.com/science/article/pii/S0925772196000065","open_access":"1"}],"volume":7,"type":"journal_article","publisher":"Elsevier","intvolume":"         7","abstract":[{"text":"A homeomorphism from R-2 to itself distorts metric quantities, such as distance and area. We describe an algorithm that constructs homeomorphisms with prescribed area distortion. Such homeomorphisms can be used to generate cartograms, which are geographic maps purposely distorted so their area distributions reflects a variable different from area, as for example population density. The algorithm generates the homeomorphism through a sequence of local piecewise linear homeomorphic changes. Sample results produced by the preliminary implementation of the method are included.","lang":"eng"}],"publication":"Computational Geometry: Theory and Applications","date_published":"1997-04-01T00:00:00Z"},{"page":"305 - 323","oa":1,"language":[{"iso":"eng"}],"article_type":"original","doi":"10.1016/0925-7721(92)90009-H","publist_id":"2804","date_created":"2018-12-11T12:04:04Z","publication_identifier":{"issn":["0925-7721"]},"status":"public","month":"06","issue":"6","day":"01","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","citation":{"ista":"Chazelle B, Edelsbrunner H, Guibas L, Pollack R, Seidel R, Sharir M, Snoeyink J. 1992. Counting and cutting cycles of lines and rods in space. Computational Geometry: Theory and Applications. 1(6), 305–323.","ama":"Chazelle B, Edelsbrunner H, Guibas L, et al. Counting and cutting cycles of lines and rods in space. <i>Computational Geometry: Theory and Applications</i>. 1992;1(6):305-323. doi:<a href=\"https://doi.org/10.1016/0925-7721(92)90009-H\">10.1016/0925-7721(92)90009-H</a>","chicago":"Chazelle, Bernard, Herbert Edelsbrunner, Leonidas Guibas, Richard Pollack, Raimund Seidel, Micha Sharir, and Jack Snoeyink. “Counting and Cutting Cycles of Lines and Rods in Space.” <i>Computational Geometry: Theory and Applications</i>. Elsevier, 1992. <a href=\"https://doi.org/10.1016/0925-7721(92)90009-H\">https://doi.org/10.1016/0925-7721(92)90009-H</a>.","mla":"Chazelle, Bernard, et al. “Counting and Cutting Cycles of Lines and Rods in Space.” <i>Computational Geometry: Theory and Applications</i>, vol. 1, no. 6, Elsevier, 1992, pp. 305–23, doi:<a href=\"https://doi.org/10.1016/0925-7721(92)90009-H\">10.1016/0925-7721(92)90009-H</a>.","short":"B. Chazelle, H. Edelsbrunner, L. Guibas, R. Pollack, R. Seidel, M. Sharir, J. Snoeyink, Computational Geometry: Theory and Applications 1 (1992) 305–323.","ieee":"B. Chazelle <i>et al.</i>, “Counting and cutting cycles of lines and rods in space,” <i>Computational Geometry: Theory and Applications</i>, vol. 1, no. 6. Elsevier, pp. 305–323, 1992.","apa":"Chazelle, B., Edelsbrunner, H., Guibas, L., Pollack, R., Seidel, R., Sharir, M., &#38; Snoeyink, J. (1992). Counting and cutting cycles of lines and rods in space. <i>Computational Geometry: Theory and Applications</i>. Elsevier. <a href=\"https://doi.org/10.1016/0925-7721(92)90009-H\">https://doi.org/10.1016/0925-7721(92)90009-H</a>"},"fulldoi":"https://doi.org/10.1016/0925-7721(92)90009-H","title":"Counting and cutting cycles of lines and rods in space","_id":"3581","oa_version":"Published Version","publication_status":"published","abstract":[{"text":"A number of rendering algorithms in computer graphics sort three-dimensional objects by depth and assume that there is no cycle that makes the sorting impossible. One way to resolve the problem caused by cycles is to cut the objects into smaller pieces. In this paper we address the problem of estimating how many such cuts arc always sufficient. We also consider a few related algorithmic and combinatorial geometry problems. For example, we demonstrate that n lines in space can be sorted in randomized expected time O(n4’st’), provided that they define no cycle. We also prove an 0(n7’4) upper bound on the number of points in space so that there are n lines with the property that for each point there are at least three noncoplanar lines that contain it. ","lang":"eng"}],"publisher":"Elsevier","intvolume":"         1","date_published":"1992-06-01T00:00:00Z","publication":"Computational Geometry: Theory and Applications","quality_controlled":"1","acknowledgement":"* Bernard Chazelle wishes to acknowledge the National Science Foundation for supporting this research in part under Grant CCR-9002352. Herbert Edelsbrunner acknowledges the support of the National Science Foundation under grants CCR-8714565 and CCR-8921421. Richard Pollack was supported in part by NSF grant CCR-8901484, NSA grant MDA904-89-H-2030, and DIMACS, a Science and Technology Center under NSF grant STC88-09648. Raimund Seidel acknowledges support by NSF grant CCR-8809040. Mich Sharir was partially supported by the Office of Naval\r\nResearch under Grant N00014-87-K-0129, by the National Science Foundation under Grant CCR-89-01484, and by grants from the U.S.-Israeli Binational Science Foundation and the Fund for Basic Research administered by the Israeli Academy of Sciences.","article_processing_charge":"No","extern":"1","volume":1,"scopus_import":"1","type":"journal_article","year":"1992","date_updated":"2022-03-16T10:41:58Z","author":[{"first_name":"Bernard","full_name":"Chazelle, Bernard","last_name":"Chazelle"},{"first_name":"Herbert","full_name":"Edelsbrunner, Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","last_name":"Edelsbrunner","orcid":"0000-0002-9823-6833"},{"last_name":"Guibas","first_name":"Leonidas","full_name":"Guibas, Leonidas"},{"first_name":"Richard","full_name":"Pollack, Richard","last_name":"Pollack"},{"last_name":"Seidel","first_name":"Raimund","full_name":"Seidel, Raimund"},{"first_name":"Micha","full_name":"Sharir, Micha","last_name":"Sharir"},{"last_name":"Snoeyink","first_name":"Jack","full_name":"Snoeyink, Jack"}],"main_file_link":[{"open_access":"1","url":"https://www.sciencedirect.com/science/article/pii/092577219290009H?via%3Dihub"}]}]