Multilevel Skeletonization Using Local Separators

<!DOCTYPE html> <html lang="en"> <head> <meta charset="utf-8"> <meta http-equiv="X-UA-Compatible" content="IE=edge"> <meta name="google" content="notranslate"> <meta http-equiv="Content-Language" content="en"> <meta name="viewport" content="width=device-width, initial-scale=1"> <meta name="csrf-token" content="1ugs3IdZignqhKXuZffK74PgIxZR0cvWEfJKri1e"> <link rel="canonical" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.13"> <meta name="DC.Publisher" content="Schloss Dagstuhl – Leibniz-Zentrum für Informatik" > <meta name="DC.Title" xml:lang="en" content="Multilevel Skeletonization Using Local Separators" > <meta name="DC.Creator.PersonalName" content="Bærentzen, J. Andreas" > <meta name="DC.Creator.PersonalName" content="Christensen, Rasmus Emil" > <meta name="DC.Creator.PersonalName" content="Gæde, Emil Toftegaard" > <meta name="DC.Creator.PersonalName" content="Rotenberg, Eva" > <meta name="DC.Subject" content="Algorithm engineering" > <meta name="DC.Subject" content="experimentation and implementation" > <meta name="DC.Subject" content="shape skeletonization" > <meta name="DC.Subject" content="curve skeletons" > <meta name="DC.Subject" content="multilevel algorithm" > <meta name="DC.Date.created" scheme="ISO8601" content="2023-06-09" > <meta name="DC.Date.issued" scheme="ISO8601" content="2023-06-09" > <meta name="DC.Date.modified" scheme="ISO8601" content="2023-06-09" > <meta name="DC.Type" content="InProceedings" > <meta name="DC.Format" scheme="IMT" content="application/pdf" > <meta name="DC.Identifier" scheme="urn:nbn:de" content="urn:nbn:de:0030-drops-178637" > <meta name="DC.Identifier" scheme="DOI" content="10.4230/LIPIcs.SoCG.2023.13" > <meta name="DC.Identifier" scheme="URL" content="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.13" > <meta name="DC.Source" content="39th International Symposium on Computational Geometry (SoCG 2023)" > <meta name="DC.Source.URI" content="https://drops.dagstuhl.de/entities/volume/LIPIcs-volume-258" > <meta name="DC.Language" scheme="ISO639-1" content="en" > <meta name="DC.Description" xml:lang="en" content="In this paper we give a new, efficient algorithm for computing curve skeletons, based on local separators. Our efficiency stems from a multilevel approach, where we solve small problems across levels of detail and combine these in order to quickly obtain a skeleton. We do this in a highly modular fashion, ensuring complete flexibility in adapting the algorithm for specific types of input or for otherwise targeting specific applications. Separator based skeletonization was first proposed by Bærentzen and Rotenberg in [ACM Tran. Graphics'21], showing high quality output at the cost of running times which become prohibitive for large inputs. Our new approach retains the high quality output, and applicability to any spatially embedded graph, while being orders of magnitude faster for all practical purposes. We test our skeletonization algorithm for efficiency and quality in practice, comparing it to local separator skeletonization on the University of Groningen Skeletonization Benchmark [Telea'16]." > <meta name="DC.Rights" scheme="DCTERMS.URI" content="https://creativecommons.org/licenses/by/4.0/legalcode" > <meta name="citation_conference_title" content="39th International Symposium on Computational Geometry (SoCG 2023)" > <meta name="citation_doi" content="10.4230/LIPIcs.SoCG.2023.13" > <meta name="citation_firstpage" content="13:1" > <meta name="citation_lastpage" content="13:18" > <meta name="citation_title" content="Multilevel Skeletonization Using Local Separators" > <meta name="citation_language" content="en" > <meta name="citation_keyword" content="Algorithm engineering" > <meta name="citation_keyword" content="experimentation and implementation" > <meta name="citation_keyword" content="shape skeletonization" > <meta name="citation_keyword" content="curve skeletons" > <meta name="citation_keyword" content="multilevel algorithm" > <meta name="citation_author" content="Bærentzen, J. Andreas" > <meta name="citation_author_institution" content="Department of Applied Mathematics and Computer Science, Technical University of Denmark, Lyngby, Denmark" > <meta name="citation_author" content="Christensen, Rasmus Emil" > <meta name="citation_author_institution" content="Department of Applied Mathematics and Computer Science, Technical University of Denmark, Lyngby, Denmark" > <meta name="citation_author" content="Gæde, Emil Toftegaard" > <meta name="citation_author_institution" content="Department of Applied Mathematics and Computer Science, Technical University of Denmark, Lyngby, Denmark" > <meta name="citation_author" content="Rotenberg, Eva" > <meta name="citation_author_institution" content="Department of Applied Mathematics and Computer Science, Technical University of Denmark, Lyngby, Denmark" > <meta name="citation_date" content="2023" > <meta name="citation_keyword" xml:lang="en" content="Algorithm engineering" > <meta name="citation_keyword" xml:lang="en" content="experimentation and implementation" > <meta name="citation_keyword" xml:lang="en" content="shape skeletonization" > <meta name="citation_keyword" xml:lang="en" content="curve skeletons" > <meta name="citation_keyword" xml:lang="en" content="multilevel algorithm" > <meta name="citation_abstract_html_url" content="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.13" > <meta name="citation_pdf_url" content="https://drops.dagstuhl.de/storage/00lipics/lipics-vol258-socg2023/LIPIcs.SoCG.2023.13/LIPIcs.SoCG.2023.13.pdf" > <meta name="citation_reference" content="Amine Abou-Rjeili and George Karypis. Multilevel algorithms for partitioning power-law graphs. In 20th International Parallel and Distributed Processing Symposium (IPDPS 2006), Proceedings, 25-29 April 2006, Rhodes Island, Greece. IEEE, 2006. URL: https://doi.org/10.1109/IPDPS.2006.1639360." > <meta name="citation_reference" content="Nina Amenta, Sunghee Choi, and Ravi Krishna Kolluri. The power crust. In David C. Anderson and Kunwoo Lee, editors, Sixth ACM Symposium on Solid Modeling and Applications, Sheraton Inn, Ann Arbor, Michigan, USA, June 4-8, 2001, pages 249-266. ACM, 2001. URL: https://doi.org/10.1145/376957.376986." > <meta name="citation_reference" content="Kasra Arnavaz, Oswin Krause, Kilian Zepf, Jakob Andreas Bærentzen, Jelena M. Krivokapic, Silja Heilmann, Pia Nyeng, and Aasa Feragen. Quantifying topology in pancreatic tubular networks from live imaging 3d microscopy. Machine Learning for Biomedical Imaging, 1, 2022. URL: https://melba-journal.org/papers/2022:015.html." > <meta name="citation_reference" content="Oscar Kin-Chung Au, Chiew-Lan Tai, Hung-Kuo Chu, Daniel Cohen-Or, and Tong-Yee Lee. Skeleton extraction by mesh contraction. ACM Trans. Graph., 27(3):44, 2008. URL: https://doi.org/10.1145/1360612.1360643." > <meta name="citation_reference" content="Andreas Bærentzen and Eva Rotenberg. Skeletonization via local separators. ACM Trans. Graph., 40(5):187:1-187:18, 2021. URL: https://doi.org/10.1145/3459233." > <meta name="citation_reference" content="Silvia Biasotti, Leila De Floriani, Bianca Falcidieno, Patrizio Frosini, Daniela Giorgi, Claudia Landi, Laura Papaleo, and Michela Spagnuolo. Describing shapes by geometrical-topological properties of real functions. ACM Comput. Surv., 40(4):12:1-12:87, 2008. URL: https://doi.org/10.1145/1391729.1391731." > <meta name="citation_reference" content="Silvia Biasotti, Daniela Giorgi, Michela Spagnuolo, and Bianca Falcidieno. Reeb graphs for shape analysis and applications. Theor. Comput. Sci., 392(1-3):5-22, 2008. URL: https://doi.org/10.1016/j.tcs.2007.10.018." > <meta name="citation_reference" content="Angela Brennecke and Tobias Isenberg. 3d shape matching using skeleton graphs. In Thomas Schulze, Stefan Schlechtweg, and Volkmar Hinz, editors, Simulation und Visualisierung 2004 (SimVis 2004) 4-5 März 2004, Magdeburg, pages 299-310. SCS Publishing House e.V., 2004. URL: http://wwwisg.cs.uni-magdeburg.de/graphik/pub/files/Brennecke_2004_3SM.pdf." > <meta name="citation_reference" content="Aydin Buluç, Henning Meyerhenke, Ilya Safro, Peter Sanders, and Christian Schulz. Recent advances in graph partitioning. In Lasse Kliemann and Peter Sanders, editors, Algorithm Engineering - Selected Results and Surveys, volume 9220 of Lecture Notes in Computer Science, pages 117-158. Springer International Publishing, 2016. URL: https://doi.org/10.1007/978-3-319-49487-6_4." > <meta name="citation_reference" content="J. Andreas Bærentzen. Gel. https://github.com/janba/GEL, 2022." > <meta name="citation_reference" content="Junjie Cao, Andrea Tagliasacchi, Matt Olson, Hao Zhang, and Zhixun Su. Point cloud skeletons via laplacian based contraction. In SMI 2010, Shape Modeling International Conference, Aix en Provence, France, June 21-23 2010, pages 187-197. IEEE Computer Society, 2010. URL: https://doi.org/10.1109/SMI.2010.25." > <meta name="citation_reference" content="Nicu D. Cornea, Deborah Silver, and Patrick Min. Curve-skeleton properties, applications, and algorithms. IEEE Trans. Vis. Comput. Graph., 13(3):530-548, 2007. URL: https://doi.org/10.1109/TVCG.2007.1002." > <meta name="citation_reference" content="Tamal K. Dey and Jian Sun. Defining and computing curve-skeletons with medial geodesic function. In Alla Sheffer and Konrad Polthier, editors, Proceedings of the Fourth Eurographics Symposium on Geometry Processing, Cagliari, Sardinia, Italy, June 26-28, 2006, volume 256 of ACM International Conference Proceeding Series, pages 143-152. Eurographics Association, 2006. URL: https://doi.org/10.2312/SGP/SGP06/143-152." > <meta name="citation_reference" content="William Harvey, Yusu Wang, and Rephael Wenger. A randomized O(m log m) time algorithm for computing reeb graphs of arbitrary simplicial complexes. In David G. Kirkpatrick and Joseph S. B. Mitchell, editors, Proceedings of the 26th ACM Symposium on Computational Geometry, Snowbird, Utah, USA, June 13-16, 2010, pages 267-276. ACM, 2010. URL: https://doi.org/10.1145/1810959.1811005." > <meta name="citation_reference" content="M. Sabry Hassouna and Aly A. Farag. Variational curve skeletons using gradient vector flow. IEEE Trans. Pattern Anal. Mach. Intell., 31(12):2257-2274, 2009. URL: https://doi.org/10.1109/TPAMI.2008.271." > <meta name="citation_reference" content="Bruce Hendrickson and Robert W. Leland. A multi-level algorithm for partitioning graphs. In Sidney Karin, editor, Proceedings Supercomputing '95, San Diego, CA, USA, December 4-8, 1995, page 28. ACM, 1995. URL: https://doi.org/10.1145/224170.224228." > <meta name="citation_reference" content="Jacob Holm, Kristian de Lichtenberg, and Mikkel Thorup. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. ACM, 48(4):723-760, 2001. URL: https://doi.org/10.1145/502090.502095." > <meta name="citation_reference" content="Hui Huang, Shihao Wu, Daniel Cohen-Or, Minglun Gong, Hao Zhang, Guiqing Li, and Baoquan Chen. L_1-medial skeleton of point cloud. ACM Trans. Graph., 32(4):65:1-65:8, 2013. URL: https://doi.org/10.1145/2461912.2461913." > <meta name="citation_reference" content="Andrei C. Jalba, Jacek Kustra, and Alexandru C. Telea. Surface and curve skeletonization of large 3d models on the GPU. IEEE Trans. Pattern Anal. Mach. Intell., 35(6):1495-1508, 2013. URL: https://doi.org/10.1109/TPAMI.2012.212." > <meta name="citation_reference" content="Wei Jiang, Kai Xu, Zhi-Quan Cheng, Ralph R. Martin, and Gang Dang. Curve skeleton extraction by coupled graph contraction and surface clustering. Graph. Model., 75(3):137-148, 2013. URL: https://doi.org/10.1016/j.gmod.2012.10.005." > <meta name="citation_reference" content="George Karypis and Vipin Kumar. Analysis of multilevel graph partitioning. In Sidney Karin, editor, Proceedings Supercomputing '95, San Diego, CA, USA, December 4-8, 1995, page 29. ACM, 1995. URL: https://doi.org/10.1145/224170.224229." > <meta name="citation_reference" content="Mattia Natali, Silvia Biasotti, Giuseppe Patanè, and Bianca Falcidieno. Graph-based representations of point clouds. Graph. Model., 73(5):151-164, 2011. URL: https://doi.org/10.1016/j.gmod.2011.03.002." > <meta name="citation_reference" content="Valerio Pascucci, Giorgio Scorzelli, Peer-Timo Bremer, and Ajith Mascarenhas. Robust on-line computation of reeb graphs: simplicity and speed. ACM Trans. Graph., 26(3):58, 2007. URL: https://doi.org/10.1145/1276377.1276449." > <meta name="citation_reference" content="Diane Perchet, Catalin I. Fetita, and Françoise J. Prêteux. Advanced navigation tools for virtual bronchoscopy. In Edward R. Dougherty, Jaakko Astola, and Karen O. Egiazarian, editors, Image Processing: Algorithms and Systems III, San Jose, California, USA, January 18, 2004, volume 5298 of SPIE Proceedings, pages 147-158. SPIE, 2004. URL: https://doi.org/10.1117/12.533096." > <meta name="citation_reference" content="Dennie Reniers, Jarke J. van Wijk, and Alexandru C. Telea. Computing multiscale curve and surface skeletons of genus 0 shapes using a global importance measure. IEEE Trans. Vis. Comput. Graph., 14(2):355-368, 2008. URL: https://doi.org/10.1109/TVCG.2008.23." > <meta name="citation_reference" content="Andrea Tagliasacchi, Ibraheem Alhashim, Matt Olson, and Hao Zhang. Mean curvature skeletons. Comput. Graph. Forum, 31(5):1735-1744, 2012. URL: https://doi.org/10.1111/j.1467-8659.2012.03178.x." > <meta name="citation_reference" content="Andrea Tagliasacchi, Thomas Delamé, Michela Spagnuolo, Nina Amenta, and Alexandru C. Telea. 3d skeletons: A state-of-the-art report. Comput. Graph. Forum, 35(2):573-597, 2016. URL: https://doi.org/10.1111/cgf.12865." > <meta name="citation_reference" content="Alexandru C. Telea. 3d skeletonization benchmark. https://webspace.science.uu.nl/~telea001/Shapes/SkelBenchmark, 2016. Accessed: 2022-10-31." > <meta name="citation_reference" content="Alexandru C. Telea and Andrei C. Jalba. Computing curve skeletons from medial surfaces of 3d shapes. In Hamish A. Carr and Silvester Czanner, editors, Theory and Practice of Computer Graphics, Rutherford, United Kingdom, 2012. Proceedings, pages 99-106. Eurographics Association, 2012. URL: https://doi.org/10.2312/LocalChapterEvents/TPCG/TPCG12/099-106." > <meta name="citation_reference" content="Ming Wan, Frank Dachille, and Arie E. Kaufman. Distance-field-based skeletons for virtual navigation. In Thomas Ertl, Kenneth I. Joy, and Amitabh Varshney, editors, 12th IEEE Visualization Conference, IEEE Vis 2001, San Diego, CA, USA, October 24-26, 2001, Proceedings, pages 239-246. IEEE Computer Society, 2001. URL: https://doi.org/10.1109/VISUAL.2001.964517." > <meta name="citation_reference" content="Yu-Shuen Wang and Tong-Yee Lee. Curve-skeleton extraction using iterative least squares optimization. IEEE Trans. Vis. Comput. Graph., 14(4):926-936, 2008. URL: https://doi.org/10.1109/TVCG.2008.38." > <meta name="citation_reference" content="Yajie Yan, Kyle Sykes, Erin W. Chambers, David Letscher, and Tao Ju. Erosion thickness on medial axes of 3d shapes. ACM Trans. Graph., 35(4):38:1-38:12, 2016. URL: https://doi.org/10.1145/2897824.2925938." > <meta name="citation_publisher" content="Schloss Dagstuhl – Leibniz-Zentrum für Informatik" > <script type="application/ld+json"> { "@context": "https://schema.org/", "@type": "WebPage", "mainEntity": { "@type": "ScholarlyArticle", "url": "https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.13", "headline": "Multilevel Skeletonization Using Local Separators", "name": "Multilevel Skeletonization Using Local Separators", "abstract": "In this paper we give a new, efficient algorithm for computing curve skeletons, based on local separators. Our efficiency stems from a multilevel approach, where we solve small problems across levels of detail and combine these in order to quickly obtain a skeleton. We do this in a highly modular fashion, ensuring complete flexibility in adapting the algorithm for specific types of input or for otherwise targeting specific applications.\r\nSeparator based skeletonization was first proposed by B\u00e6rentzen and Rotenberg in [ACM Tran. Graphics'21], showing high quality output at the cost of running times which become prohibitive for large inputs. Our new approach retains the high quality output, and applicability to any spatially embedded graph, while being orders of magnitude faster for all practical purposes. \r\nWe test our skeletonization algorithm for efficiency and quality in practice, comparing it to local separator skeletonization on the University of Groningen Skeletonization Benchmark [Telea'16].", "keywords": [ "Algorithm engineering", "experimentation and implementation", "shape skeletonization", "curve skeletons", "multilevel algorithm" ], "author": [ { "@type": "Person", "name": "B\u00e6rentzen, J. Andreas", "givenName": "J. Andreas", "familyName": "B\u00e6rentzen", "email": "mailto:janba@dtu.dk", "sameAs": "https://orcid.org/0000-0003-2583-0660", "affiliation": "Department of Applied Mathematics and Computer Science, Technical University of Denmark, Lyngby, Denmark", "funding": "Partially supported by the Villum Foundation through Villum Investigator Project InnoTop." }, { "@type": "Person", "name": "Christensen, Rasmus Emil", "givenName": "Rasmus Emil", "familyName": "Christensen", "affiliation": "Department of Applied Mathematics and Computer Science, Technical University of Denmark, Lyngby, Denmark" }, { "@type": "Person", "name": "G\u00e6de, Emil Toftegaard", "givenName": "Emil Toftegaard", "familyName": "G\u00e6de", "email": "mailto:etoga@dtu.dk", "sameAs": "https://orcid.org/0009-0001-9462-6359", "affiliation": "Department of Applied Mathematics and Computer Science, Technical University of Denmark, Lyngby, Denmark" }, { "@type": "Person", "name": "Rotenberg, Eva", "givenName": "Eva", "familyName": "Rotenberg", "email": "mailto:erot@dtu.dk", "sameAs": "https://orcid.org/0000-0001-5853-7909", "affiliation": "Department of Applied Mathematics and Computer Science, Technical University of Denmark, Lyngby, Denmark" } ], "position": 13, "dateCreated": "2023-06-09", "datePublished": "2023-06-09", "isAccessibleForFree": true, "license": "https://creativecommons.org/licenses/by/4.0/legalcode", "copyrightHolder": [ { "@type": "Person", "name": "B\u00e6rentzen, J. Andreas", "givenName": "J. Andreas", "familyName": "B\u00e6rentzen", "email": "mailto:janba@dtu.dk", "sameAs": "https://orcid.org/0000-0003-2583-0660", "affiliation": "Department of Applied Mathematics and Computer Science, Technical University of Denmark, Lyngby, Denmark", "funding": "Partially supported by the Villum Foundation through Villum Investigator Project InnoTop." }, { "@type": "Person", "name": "Christensen, Rasmus Emil", "givenName": "Rasmus Emil", "familyName": "Christensen", "affiliation": "Department of Applied Mathematics and Computer Science, Technical University of Denmark, Lyngby, Denmark" }, { "@type": "Person", "name": "G\u00e6de, Emil Toftegaard", "givenName": "Emil Toftegaard", "familyName": "G\u00e6de", "email": "mailto:etoga@dtu.dk", "sameAs": "https://orcid.org/0009-0001-9462-6359", "affiliation": "Department of Applied Mathematics and Computer Science, Technical University of Denmark, Lyngby, Denmark" }, { "@type": "Person", "name": "Rotenberg, Eva", "givenName": "Eva", "familyName": "Rotenberg", "email": "mailto:erot@dtu.dk", "sameAs": "https://orcid.org/0000-0001-5853-7909", "affiliation": "Department of Applied Mathematics and Computer Science, Technical University of Denmark, Lyngby, Denmark" } ], "copyrightYear": "2023", "creativeWorkStatus": "Published", "inLanguage": "en-US", "identifier": "https://doi.org/10.4230/LIPIcs.SoCG.2023.13", "funding": "Emil Toftegaard G\u00e6de and Eva Rotenberg: supported by Eva Rotenberg\u2019s Carlsberg Foundation Young Researcher Fellowship CF21-0302 - \"Graph Algorithms with Geometric Applications\".", "publisher": { "@type": "Organization", "name": "Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik", "alternateName": [ "Schloss Dagstuhl - Leibniz Center for Informatics", "Schloss Dagstuhl - LZI GmbH" ], "identifier": "https://ror.org/00k4h2615", "sameAs": [ "https://isni.org/isni/0000000100093196", "https://www.dagstuhl.de", "https://de.wikipedia.org/wiki/Leibniz-Zentrum_f%C3%BCr_Informatik" ], "department": { "@type": "Organization", "name": "Dagstuhl Publishing", "logo": { "@type": "ImageObject", "url": "https://www.dagstuhl.de/storage/media/0005/5660/publishing-logo.jpg" }, "contactPoint": { "@type": "ContactPoint", "contactType": "customer support", "email": "mailto:publishing@dagstuhl.de", "url": "https://www.dagstuhl.de/en/publishing/team" } }, "contactPoint": { "@type": "ContactPoint", "contactType": "customer support", "email": "mailto:lzi@dagstuhl.de", "url": "https://www.dagstuhl.de/en/institute/team" } }, "citation": [ "https://doi.org/10.1109/IPDPS.2006.1639360", "https://doi.org/10.1145/376957.376986", "https://melba-journal.org/papers/2022:015.html", "https://doi.org/10.1145/1360612.1360643", "https://doi.org/10.1145/3459233", "https://doi.org/10.1145/1391729.1391731", "https://doi.org/10.1016/j.tcs.2007.10.018", "http://wwwisg.cs.uni-magdeburg.de/graphik/pub/files/Brennecke_2004_3SM.pdf", "https://doi.org/10.1007/978-3-319-49487-6_4", "https://github.com/janba/GEL", "https://doi.org/10.1109/SMI.2010.25", "https://doi.org/10.1109/TVCG.2007.1002", "https://doi.org/10.2312/SGP/SGP06/143-152", "https://doi.org/10.1145/1810959.1811005", "https://doi.org/10.1109/TPAMI.2008.271", "https://doi.org/10.1145/224170.224228", "https://doi.org/10.1145/502090.502095", "https://doi.org/10.1145/2461912.2461913", "https://doi.org/10.1109/TPAMI.2012.212", "https://doi.org/10.1016/j.gmod.2012.10.005", "https://doi.org/10.1145/224170.224229", "https://doi.org/10.1016/j.gmod.2011.03.002", "https://doi.org/10.1145/1276377.1276449", "https://doi.org/10.1117/12.533096", "https://doi.org/10.1109/TVCG.2008.23", "https://doi.org/10.1111/j.1467-8659.2012.03178.x", "https://doi.org/10.1111/cgf.12865", "https://webspace.science.uu.nl/~telea001/Shapes/SkelBenchmark", "https://doi.org/10.2312/LocalChapterEvents/TPCG/TPCG12/099-106", "https://doi.org/10.1109/VISUAL.2001.964517", "https://doi.org/10.1109/TVCG.2008.38", "https://doi.org/10.1145/2897824.2925938" ], "pageStart": "13:1", "pageEnd": "13:18", "accessMode": "textual", "accessModeSufficient": "textual", "thumbnailUrl": "https://drops.dagstuhl.de/storage/00lipics/lipics-vol258-socg2023/thumbnails/LIPIcs.SoCG.2023.13/LIPIcs.SoCG.2023.13.png", "potentialAction": { "@type": "ReadAction", "target": { "@type": "EntryPoint", "urlTemplate": "https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.13", "actionPlatform": [ "https://schema.org/DesktopWebPlatform", "https://schema.org/AndroidPlatform", "https://schema.org/IOSPlatform" ] } }, "isPartOf": { "@type": "PublicationVolume", "@id": "https://drops.dagstuhl.de/entities/volume/LIPIcs-volume-258", "url": "https://drops.dagstuhl.de/entities/volume/LIPIcs-volume-258", "volumeNumber": 258, "name": "39th International Symposium on Computational Geometry (SoCG 2023)", "dateCreated": "2023-06-09", "datePublished": "2023-06-09", "editor": [ { "@type": "Person", "name": "Chambers, Erin W.", "givenName": "Erin W.", "familyName": "Chambers", "email": "mailto:erin.chambers@slu.edu", "sameAs": "https://orcid.org/0000-0001-8333-3676", "affiliation": "Saint Louis University, USA" }, { "@type": "Person", "name": "Gudmundsson, Joachim", "givenName": "Joachim", "familyName": "Gudmundsson", "email": "mailto:joachim.gudmundsson@sydney.edu.au", "sameAs": "https://orcid.org/0000-0002-6778-7990", "affiliation": "University of Sydney, Australia" } ], "isAccessibleForFree": true, "publisher": { "@type": "Organization", "name": "Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik", "alternateName": [ "Schloss Dagstuhl - Leibniz Center for Informatics", "Schloss Dagstuhl - LZI GmbH" ], "identifier": "https://ror.org/00k4h2615", "sameAs": [ "https://isni.org/isni/0000000100093196", "https://www.dagstuhl.de", "https://de.wikipedia.org/wiki/Leibniz-Zentrum_f%C3%BCr_Informatik" ], "department": { "@type": "Organization", "name": "Dagstuhl Publishing", "logo": { "@type": "ImageObject", "url": "https://www.dagstuhl.de/storage/media/0005/5660/publishing-logo.jpg" }, "contactPoint": { "@type": "ContactPoint", "contactType": "customer support", "email": "mailto:publishing@dagstuhl.de", "url": "https://www.dagstuhl.de/en/publishing/team" } }, "contactPoint": { "@type": "ContactPoint", "contactType": "customer support", "email": "mailto:lzi@dagstuhl.de", "url": "https://www.dagstuhl.de/en/institute/team" } }, "isPartOf": { "@type": "BookSeries", "url": "https://drops.dagstuhl.de/entities/series/LIPIcs", "name": "Leibniz International Proceedings in Informatics", "issn": "1868-8969", "isAccessibleForFree": true, "publisher": { "@type": "Organization", "name": "Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik", "alternateName": [ "Schloss Dagstuhl - Leibniz Center for Informatics", "Schloss Dagstuhl - LZI GmbH" ], "identifier": "https://ror.org/00k4h2615", "sameAs": [ "https://isni.org/isni/0000000100093196", "https://www.dagstuhl.de", "https://de.wikipedia.org/wiki/Leibniz-Zentrum_f%C3%BCr_Informatik" ], "department": { "@type": "Organization", "name": "Dagstuhl Publishing", "logo": { "@type": "ImageObject", "url": "https://www.dagstuhl.de/storage/media/0005/5660/publishing-logo.jpg" }, "contactPoint": { "@type": "ContactPoint", "contactType": "customer support", "email": "mailto:publishing@dagstuhl.de", "url": "https://www.dagstuhl.de/en/publishing/team" } }, "contactPoint": { "@type": "ContactPoint", "contactType": "customer support", "email": "mailto:lzi@dagstuhl.de", "url": "https://www.dagstuhl.de/en/institute/team" } }, "hasPart": "https://drops.dagstuhl.de/entities/volume/LIPIcs-volume-258" } } } } </script> <link rel="alternate" type="application/xml" title="Multilevel Skeletonization Using Local Separators / XML" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.13/metadata/xml"> <link rel="alternate" type="application/x-bibtex" title="Multilevel Skeletonization Using Local Separators / BibTeX" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.13/metadata/bibtex/download"> <link rel="alternate" type="application/ld+json" title="Multilevel Skeletonization Using Local Separators / Schema.org" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.13/metadata/schema-org"> <link rel="alternate" type="application/xml" title="Multilevel Skeletonization Using Local Separators / OAI-DublinCore" href="/oai/?verb=GetRecord&metadataPrefix=oai_dc&identifier=17863"> <title>Multilevel Skeletonization Using Local Separators</title> <link rel="icon" href="https://drops.dagstuhl.de/favicon.ico"> <link rel="stylesheet" href="https://drops.dagstuhl.de/css/app.css?drops-core-2025-01-23.1"> </head> <body> <nav class="navbar main fixed-top navbar-expand-lg navbar-light bg-light"> <div class="container-fluid"> <a class="navbar-brand" href="https://www.dagstuhl.de"> <img class="lzi-logo" src="https://drops.dagstuhl.de/images/LZI-Logo.jpg" width="84" height="62" alt="Schloss Dagstuhl - LZI - Logo"> </a> <button class="navbar-toggler" type="button" data-bs-toggle="collapse" data-bs-target="#navbarSupportedContent" aria-controls="navbarSupportedContent" aria-expanded="false" aria-label="Toggle navigation"> <span class="navbar-toggler-icon"></span> </button> <div class="collapse navbar-collapse" id="navbarSupportedContent"> <ul class="navbar-nav me-auto mb-2 mb-lg-0"> <li class="nav-item" style="white-space: nowrap"> <a class="nav-link" href="https://drops.dagstuhl.de"> <i class="bi bi-house large-icon"></i> DROPS </a> </li> <li class="nav-item dropdown"> <a class="nav-link dropdown-toggle" href="#" id="navbarDropdownSeries" role="button" data-bs-toggle="dropdown" aria-expanded="false"> <i class="bi bi-journals large-icon"></i> Series </a> <ul class="dropdown-menu" aria-labelledby="navbarDropdown"> <li><a class="dropdown-item" href="https://drops.dagstuhl.de/entities/series/LIPIcs"> LIPIcs – Leibniz International Proceedings in Informatics </a> </li> <li><a class="dropdown-item" href="https://drops.dagstuhl.de/entities/series/OASIcs"> OASIcs – Open Access Series in Informatics </a> </li> <li><a class="dropdown-item" href="https://drops.dagstuhl.de/entities/series/DFU"> Dagstuhl Follow-Ups </a> </li> <li><a class="dropdown-item" href="https://drops.dagstuhl.de/entities/series/DagAnnRep"> Schloss Dagstuhl Jahresbericht </a> </li> <li class="dropdown-divider"></li> <li> <a class="dropdown-item" href="/#discontinued-series">Discontinued Series</a> </li> </ul> </li> <li class="nav-item dropdown"> <a class="nav-link dropdown-toggle" href="#" id="navbarDropdownJournals" role="button" data-bs-toggle="dropdown" aria-expanded="false" data-fix-width=" JournalsXXXXX "> <i class="bi bi-journal large-icon"></i> Journals </a> <ul class="dropdown-menu" aria-labelledby="navbarDropdown"> <li><a class="dropdown-item" href="https://drops.dagstuhl.de/entities/journal/DARTS"> DARTS – Dagstuhl Artifacts Series </a> </li> <li><a class="dropdown-item" href="https://drops.dagstuhl.de/entities/journal/DagRep"> Dagstuhl Reports </a> </li> <li><a class="dropdown-item" href="https://drops.dagstuhl.de/entities/journal/DagMan"> Dagstuhl Manifestos </a> </li> <li><a class="dropdown-item" href="https://drops.dagstuhl.de/entities/journal/LITES"> LITES – Leibniz Transactions on Embedded Systems </a> </li> <li><a class="dropdown-item" href="https://drops.dagstuhl.de/entities/journal/TGDK"> TGDK – Transactions on Graph Data and Knowledge </a> </li> </ul> </li> <li class="nav-item dropdown"> <a class="nav-link dropdown-toggle" href="#" id="navbarDropdownConferences" role="button" data-bs-toggle="dropdown" aria-expanded="false"> <i class="bi bi-people large-icon"></i> Conferences </a> <ul class="dropdown-menu conference-dropdown" aria-labelledby="navbarDropdown"> <div class="row"> <div class="col-sm-4 nav-conference-col"> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/AFT"> AFT </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/AIB"> AIB </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/AofA"> AofA </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/APPROX"> APPROX </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ATMOS"> ATMOS </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/CALCO"> CALCO </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/CCC"> CCC </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/CONCUR"> CONCUR </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/COSIT"> COSIT </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/CP"> CP </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/CPM"> CPM </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/CSL"> CSL </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/DISC"> DISC </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/DITAM"> DITAM </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/DNA"> DNA </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ECOOP"> ECOOP </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ECRTS"> ECRTS </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ESA"> ESA </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/FAB"> FAB </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/FMBC"> FMBC </a> </li> </div> <div class="col-sm-4 nav-conference-col"> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/FORC"> FORC </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/FSCD"> FSCD </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/FSTTCS"> FSTTCS </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/FUN"> FUN </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/GD"> GD </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/GIScience"> GIScience </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ICALP"> ICALP </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ICDT"> ICDT </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ICPEC"> ICPEC </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/IPEC"> IPEC </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/iPMVM"> iPMVM </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ISAAC"> ISAAC </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ITC"> ITC </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ITCS"> ITCS </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ITP"> ITP </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/LDK"> LDK </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/MFCS"> MFCS </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/Microservices"> Microservices </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/NG-RES"> NG-RES </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/OPODIS"> OPODIS </a> </li> </div> <div class="col-sm-4 nav-conference-col"> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/PARMA"> PARMA </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/RANDOM"> RANDOM </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/SAND"> SAND </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/SAT"> SAT </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/SEA"> SEA </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/SLATE"> SLATE </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/SNAPL"> SNAPL </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/SoCG"> SoCG </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/STACS"> STACS </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/SWAT"> SWAT </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/TIME"> TIME </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/Tokenomics"> Tokenomics </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/TQC"> TQC </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/TYPES"> TYPES </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/WABI"> WABI </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/WCET"> WCET </a> </li> </div> </div> </ul> </li> <li class="nav-item dropdown"> <a class="nav-link dropdown-toggle" href="#" id="navbarDropdownArtifacts" role="button" data-bs-toggle="dropdown" aria-expanded="false"> <i class="bi bi-braces-asterisk large-icon"></i> Artifacts </a> <ul class="dropdown-menu" aria-labelledby="navbarDropdown"> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/collection/supplementary-materials"> Supplementary Materials (Software, Datasets, ...) </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/collection/dblp"> dblp Artifacts </a> </li> <li class="dropdown-divider"></li> <li> <a class="dropdown-item" href="/entities/journal/DARTS"> DARTS (Evaluated Artifacts) </a> </li> </ul> </li> </ul> <form class="navbar-search d-flex" action="https://drops.dagstuhl.de/search" method="post"> <input type="hidden" name="_token" value="1ugs3IdZignqhKXuZffK74PgIxZR0cvWEfJKri1e" autocomplete="off"> <div class="input-group"> <input class="form-control" type="search" placeholder="Search" aria-label="Search" name="term" autocomplete="off" maxlength="600"> <button class="btn btn-outline-success" type="submit"> <i class="bi bi-search" style="color: #000"></i> </button> </div> </form> <ul class="navbar-nav nav-metadata"> <li class="nav-item dropdown"> <a class="nav-link dropdown-toggle" id="navbarDropdownMetadata" role="button" data-bs-toggle="dropdown" aria-expanded="false"> <i class="bi bi-database-down large-icon"></i><span class="nav-text-metadata">Metadata Export</span> </a> <ul class="dropdown-menu dropdown-metadata" aria-labelledby="navbarDropdownMetadata"> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/metadata">Metadata Export</a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/oai?verb=Identify" target="_blank">OAI Interface</a> </li> </ul> </li> </ul> </div> </div> </nav> <div id="app" data-release="drops-core-2025-01-23.1" class="container "> <div id="_top-of-page"></div> <div class="fixed-search-button"><i class="bi bi-search"></i></div> <div class="document-details"> <section class="mt-3 mb-5 title"> <div class="entity-type document"> <div class="row"> <div class="col-lg-3 entity-type-name"> <i class="bi bi-file-earmark"></i> Document <img src="https://drops.dagstuhl.de/images/open-access-logo.png" width="80" alt="Open Access Logo" style="transform: translate(1em, -0.2em);"> </div> <div class="col-lg-9"> <input id="doi" type="text" style="position: fixed; top: -50vh" value="https://doi.org/10.4230/LIPIcs.SoCG.2023.13"> <div class="sharing-section"> <span class="permalink"> <span> <code><span class="hide-mobile">https://doi.org/</span>10.4230/LIPIcs.SoCG.2023.13</code> <span class="btn btn-clipboard copy-to-clipboard" title="Copy to clipboard" data-selector="doi"> <i class="bi bi-clipboard" aria-hidden="true"></i> <i class="bi bi-check -hidden" aria-hidden="true"></i> </span> </span> </span> <span class="sharing-buttons"> <a class="btn sharing-btn facebook" href="https://facebook.com/sharer/sharer.php?u=https%3A%2F%2Fdoi.org%2F10.4230%2FLIPIcs.SoCG.2023.13" target="_blank" rel="noopener" aria-hidden="true"> <i class="bi bi-facebook"></i> </a> <a class="btn sharing-btn reddit" href="https://www.reddit.com/submit?url=https%3A%2F%2Fdoi.org%2F10.4230%2FLIPIcs.SoCG.2023.13&title=Multilevel+Skeletonization+Using+Local+Separators" target="_blank" rel="noopener" aria-hidden="true"> <i class="bi bi-reddit"></i> </a> <a class="btn sharing-btn twitter" href="https://twitter.com/intent/tweet/?text=Multilevel+Skeletonization+Using+Local+Separators&url=https%3A%2F%2Fdoi.org%2F10.4230%2FLIPIcs.SoCG.2023.13" target="_blank" rel="noopener" aria-hidden="true"> <svg xmlns="http://www.w3.org/2000/svg" width="16" height="16" fill="currentColor" class="bi bi-twitter-x" viewBox="0 0 16 16"> <path d="M12.6.75h2.454l-5.36 6.142L16 15.25h-4.937l-3.867-5.07-4.425 5.07H.316l5.733-6.57L0 .75h5.063l3.495 4.633L12.601.75Zm-.86 13.028h1.36L4.323 2.145H2.865l8.875 11.633Z"/> </svg> </a> <a class="btn sharing-btn email" href="mailto:?subject=Multilevel+Skeletonization+Using+Local+Separators&body=https%3A%2F%2Fdoi.org%2F10.4230%2FLIPIcs.SoCG.2023.13" target="_self" rel="noopener" aria-hidden="true"> <svg xmlns="http://www.w3.org/2000/svg" width="16" height="16" viewBox="0 0 24 24" fill="currentColor"> <path d="M22 4H2C.9 4 0 4.9 0 6v12c0 1.1.9 2 2 2h20c1.1 0 2-.9 2-2V6c0-1.1-.9-2-2-2zM7.25 14.43l-3.5 2c-.08.05-.17.07-.25.07-.17 0-.34-.1-.43-.25-.14-.24-.06-.55.18-.68l3.5-2c.24-.14.55-.06.68.18.14.24.06.55-.18.68zm4.75.07c-.1 0-.2-.03-.27-.08l-8.5-5.5c-.23-.15-.3-.46-.15-.7.15-.22.46-.3.7-.14L12 13.4l8.23-5.32c.23-.15.54-.08.7.15.14.23.07.54-.16.7l-8.5 5.5c-.08.04-.17.07-.27.07zm8.93 1.75c-.1.16-.26.25-.43.25-.08 0-.17-.02-.25-.07l-3.5-2c-.24-.13-.32-.44-.18-.68s.44-.32.68-.18l3.5 2c.24.13.32.44.18.68z"/> </svg> </a> </span> <span class="sharing-buttons"> <span class="dropdown"> <a class="btn sharing-btn metadata dropdown-toggle" href="#" role="button" data-bs-toggle="dropdown" aria-expanded="false"><i class="bi bi-download"></i></a> <ul class="dropdown-menu dropdown-menu-end"> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.13/metadata/xml"> Export XML </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.13/metadata/acm-xml"> Export ACM-XML </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.13/metadata/doaj-xml"> Export DOAJ-XML </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.13/metadata/schema-org"> Export Schema.org </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.13/metadata/bibtex"> Export BibTeX </a> </li> </ul> </span> </span> </div> </div> </div> </div> <hr> <h1>Multilevel Skeletonization Using Local Separators</h1> <h3 class="mt-2 authors"> Authors <a href="#author-details" style="font-size: 0.8em; padding-right: 1em"><i class="bi bi-info-circle"></i></a> <span class="author"> <a href="https://drops.dagstuhl.de/search/documents?author=Bærentzen, J. Andreas" class="name">J. Andreas Bærentzen</a> <a href="https://orcid.org/0000-0003-2583-0660"><img class="orcid-logo" src="https://drops.dagstuhl.de/images/orcid.png" alt="ORCID-Logo"></a>, </span> <span class="author"> <a href="https://drops.dagstuhl.de/search/documents?author=Christensen, Rasmus Emil" class="name">Rasmus Emil Christensen</a>, </span> <span class="author"> <a href="https://drops.dagstuhl.de/search/documents?author=Gæde, Emil Toftegaard" class="name">Emil Toftegaard Gæde</a> <a href="https://orcid.org/0009-0001-9462-6359"><img class="orcid-logo" src="https://drops.dagstuhl.de/images/orcid.png" alt="ORCID-Logo"></a>, </span> <span class="author"> <a href="https://drops.dagstuhl.de/search/documents?author=Rotenberg, Eva" class="name">Eva Rotenberg</a> <a href="https://orcid.org/0000-0001-5853-7909"><img class="orcid-logo" src="https://drops.dagstuhl.de/images/orcid.png" alt="ORCID-Logo"></a> </span> </h3> <hr> <ul class="mt-4"> <li> <span style="margin-right: 10px; ">Part of:</span> <span style="white-space: nowrap"> <i class="bi bi-book-half"></i> Volume: </span> <a href="https://drops.dagstuhl.de/entities/volume/LIPIcs-volume-258">39th International Symposium on Computational Geometry (SoCG 2023) </a> <br> <span style="margin-right: 10px; visibility: hidden;">Part of:</span> <span style="white-space: nowrap"> <i class="bi bi-journals"></i> Series: </span> <a href="https://drops.dagstuhl.de/entities/series/LIPIcs">Leibniz International Proceedings in Informatics (LIPIcs)</a> <br> <span style="margin-right: 10px; visibility: hidden;">Part of:</span> <span style="white-space: nowrap"> <i class="bi bi-people"></i> Conference: </span> <a href="https://drops.dagstuhl.de/entities/conference/SoCG">Symposium on Computational Geometry (SoCG)</a> </li> <li class="mt-2">License:   <a href="https://creativecommons.org/licenses/by/4.0/legalcode"> <img class="license-logo" src="https://drops.dagstuhl.de/images/cc-by.png" alt="CC-BY Logo"> Creative Commons Attribution 4.0 International license </a> </li> <li>Publication Date: 2023-06-09 </li> </ul> <hr> </section> <a class="fixed-pdf-button" href="https://drops.dagstuhl.de/storage/00lipics/lipics-vol258-socg2023/LIPIcs.SoCG.2023.13/LIPIcs.SoCG.2023.13.pdf"><i class="bi bi-file-earmark-pdf-fill" style="color:red"></i> PDF </a> <div class="row mt-2"> <div class="col-lg-4 mt-2"> <section class="thumbnail"> <a href="https://drops.dagstuhl.de/storage/00lipics/lipics-vol258-socg2023/LIPIcs.SoCG.2023.13/LIPIcs.SoCG.2023.13.pdf"><img src="https://drops.dagstuhl.de/storage/00lipics/lipics-vol258-socg2023/thumbnails/LIPIcs.SoCG.2023.13/LIPIcs.SoCG.2023.13.png" alt="Thumbnail PDF"></a> </section> <section class="files mt-5"> <h2>File</h2> <div class="content"> <div> <a href="https://drops.dagstuhl.de/storage/00lipics/lipics-vol258-socg2023/LIPIcs.SoCG.2023.13/LIPIcs.SoCG.2023.13.pdf"><i class="bi bi-file-earmark-pdf-fill" style="color:red"></i> LIPIcs.SoCG.2023.13.pdf</a> <ul> <li>Filesize: 6.51 MB</li> <li>18 pages</li> </ul> </div> </div> </section> <section class="identifiers mt-3"> <h2>Document Identifiers</h2> <div class="content"> <ul> <li><b>DOI:</b> <a href="https://doi.org/10.4230/LIPIcs.SoCG.2023.13">10.4230/LIPIcs.SoCG.2023.13</a></li> <li><b>URN:</b> <a href="https://nbn-resolving.org/process-urn-form?identifier=urn:nbn:de:0030-drops-178637&verb=FULL">urn:nbn:de:0030-drops-178637</a></li> </ul> </div> </section> <section class="authors mt-3" id="author-details"> <h2>Author Details</h2> <div class="author person-details"> <div> <i class="bi bi-person-fill"></i> <span class="name"><b>J. Andreas Bærentzen</b></span> <a href="https://orcid.org/0000-0003-2583-0660"><img class="orcid-logo" src="https://drops.dagstuhl.de/images/orcid.png" alt="ORCID-Logo"></a> <a href="mailto:janba@dtu.dk"><i class="bi bi-envelope"></i></a> <a href="https://drops.dagstuhl.de/search/documents?author=Bærentzen, J. Andreas"><small><i class="bi bi-search"></i></small></a> </div> <ul> <li class="affiliation">Department of Applied Mathematics and Computer Science, Technical University of Denmark, Lyngby, Denmark </li> </ul> </div> <div class="author person-details"> <div> <i class="bi bi-person-fill"></i> <span class="name"><b>Rasmus Emil Christensen</b></span> <a href="https://drops.dagstuhl.de/search/documents?author=Christensen, Rasmus Emil"><small><i class="bi bi-search"></i></small></a> </div> <ul> <li class="affiliation">Department of Applied Mathematics and Computer Science, Technical University of Denmark, Lyngby, Denmark </li> </ul> </div> <div class="author person-details"> <div> <i class="bi bi-person-fill"></i> <span class="name"><b>Emil Toftegaard Gæde</b></span> <a href="https://orcid.org/0009-0001-9462-6359"><img class="orcid-logo" src="https://drops.dagstuhl.de/images/orcid.png" alt="ORCID-Logo"></a> <a href="mailto:etoga@dtu.dk"><i class="bi bi-envelope"></i></a> <a href="https://drops.dagstuhl.de/search/documents?author=Gæde, Emil Toftegaard"><small><i class="bi bi-search"></i></small></a> </div> <ul> <li class="affiliation">Department of Applied Mathematics and Computer Science, Technical University of Denmark, Lyngby, Denmark </li> </ul> </div> <div class="author person-details"> <div> <i class="bi bi-person-fill"></i> <span class="name"><b>Eva Rotenberg</b></span> <a href="https://orcid.org/0000-0001-5853-7909"><img class="orcid-logo" src="https://drops.dagstuhl.de/images/orcid.png" alt="ORCID-Logo"></a> <a href="mailto:erot@dtu.dk"><i class="bi bi-envelope"></i></a> <a href="https://drops.dagstuhl.de/search/documents?author=Rotenberg, Eva"><small><i class="bi bi-search"></i></small></a> </div> <ul> <li class="affiliation">Department of Applied Mathematics and Computer Science, Technical University of Denmark, Lyngby, Denmark </li> </ul> </div> </section> <section class="related-version mt-3"> <h2>Funding</h2> <div class="content"> Emil Toftegaard Gæde and Eva Rotenberg: supported by Eva Rotenberg’s Carlsberg Foundation Young Researcher Fellowship CF21-0302 - "Graph Algorithms with Geometric Applications". <ul> <li><b>Bærentzen, J. Andreas</b>: Partially supported by the Villum Foundation through Villum Investigator Project InnoTop.</li> </ul> </div> </section> </div> <div class="col-lg-8 mt-2"> <section class="cite-as mt-3"> <h2>Cite As <span class="btn btn-primary btn-xs" style="float: right" data-bs-toggle="modal" data-bs-target="#bibtex-modal">Get BibTex</span></h2> <div class="content"> J. Andreas Bærentzen, Rasmus Emil Christensen, Emil Toftegaard Gæde, and Eva Rotenberg. Multilevel Skeletonization Using Local Separators. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 13:1-13:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) <a href="https://doi.org/10.4230/LIPIcs.SoCG.2023.13">https://doi.org/10.4230/LIPIcs.SoCG.2023.13</a> </div> <div class="modal fade" id="bibtex-modal" tabindex="-1" aria-labelledby="bibtexModalLabel" aria-hidden="true"> <div class="modal-dialog modal-dialog-centered"> <div class="modal-content"> <div class="modal-header"> <h5 class="modal-title" id="bibtexModalLabel">BibTex</h5> <button type="button" class="btn-close" data-bs-dismiss="modal" aria-label="Close"></button> </div> <div class="modal-body"> <pre class="bibtex">@InProceedings{brentzen_et_al:LIPIcs.SoCG.2023.13, author = {B{\ae}rentzen, J. Andreas and Christensen, Rasmus Emil and G{\ae}de, Emil Toftegaard and Rotenberg, Eva}, title = {{Multilevel Skeletonization Using Local Separators}}, booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)}, pages = {13:1--13:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-273-0}, ISSN = {1868-8969}, year = {2023}, volume = {258}, editor = {Chambers, Erin W. and Gudmundsson, Joachim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.13}, URN = {urn:nbn:de:0030-drops-178637}, doi = {10.4230/LIPIcs.SoCG.2023.13}, annote = {Keywords: Algorithm engineering, experimentation and implementation, shape skeletonization, curve skeletons, multilevel algorithm} }</pre> <div style="overflow: hidden"> <textarea style="position: absolute; top: -400vh" id="bibtex-input">@InProceedings{brentzen_et_al:LIPIcs.SoCG.2023.13, author = {B{\ae}rentzen, J. Andreas and Christensen, Rasmus Emil and G{\ae}de, Emil Toftegaard and Rotenberg, Eva}, title = {{Multilevel Skeletonization Using Local Separators}}, booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)}, pages = {13:1--13:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-273-0}, ISSN = {1868-8969}, year = {2023}, volume = {258}, editor = {Chambers, Erin W. and Gudmundsson, Joachim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.13}, URN = {urn:nbn:de:0030-drops-178637}, doi = {10.4230/LIPIcs.SoCG.2023.13}, annote = {Keywords: Algorithm engineering, experimentation and implementation, shape skeletonization, curve skeletons, multilevel algorithm} }</textarea> </div> </div> <div class="modal-footer"> <button type="button" class="btn btn-secondary" data-bs-dismiss="modal">Close</button> <button type="button" class="btn btn-primary copy-to-clipboard" data-selector="bibtex-input"><i class="bi bi-clipboard"></i> Copy BibTex To Clipboard<span class="bi bi-check -hidden" style="padding-left: 1em; font-weight: bold"></span></button> </div> </div> </div> </div> </section> <section class="abstract"> <h2>Abstract</h2> <pre class="content" style="white-space: -moz-pre-wrap; white-space: -o-pre-wrap; word-wrap: break-word; white-space: pre-wrap;">In this paper we give a new, efficient algorithm for computing curve skeletons, based on local separators. Our efficiency stems from a multilevel approach, where we solve small problems across levels of detail and combine these in order to quickly obtain a skeleton. We do this in a highly modular fashion, ensuring complete flexibility in adapting the algorithm for specific types of input or for otherwise targeting specific applications. Separator based skeletonization was first proposed by Bærentzen and Rotenberg in [ACM Tran. Graphics'21], showing high quality output at the cost of running times which become prohibitive for large inputs. Our new approach retains the high quality output, and applicability to any spatially embedded graph, while being orders of magnitude faster for all practical purposes. We test our skeletonization algorithm for efficiency and quality in practice, comparing it to local separator skeletonization on the University of Groningen Skeletonization Benchmark [Telea'16].</pre> </section> <section class="subject-classifications mt-3"> <h2>Subject Classification</h2> <div class="acm-subject-classifications"> <h5>ACM Subject Classification</h5> <div class="content"> <ul> <li>Computing methodologies → Computer graphics</li> <li>Theory of computation → Computational geometry</li> <li>Software and its engineering → Software design engineering</li> </ul> </div> </div> <div class="keywords "> <h5>Keywords</h5> <div class="content"> <ul class="list-style-comma"> <li>Algorithm engineering</li> <li>experimentation and implementation</li> <li>shape skeletonization</li> <li>curve skeletons</li> <li>multilevel algorithm</li> </ul> </div> </div> </section> <section class="metrics mt-3"> <h2>Metrics</h2> <div class="content"> <ul> <li> <a href="#" class="btn-statistics" data-entity="document/10.4230/LIPIcs.SoCG.2023.13" data-title="Multilevel Skeletonization Using Local Separators"> <i class="bi bi-graph-up"></i> Access Statistics </a> </li> <li> Total Accesses (updated on a weekly basis) <div class="stats-total"> <div class="stats total-downloads"> <div class="circle"> <div class="number" data-number="0">0</div> </div> <div class="label">PDF Downloads</div> </div> <div class="stats total-metadata-views"> <div class="circle"> <div class="number" data-number="0">0</div> </div> <div class="label">Metadata Views</div> </div> </div>  </li> </ul> </div> </section> <div class="offcanvas offcanvas-bottom" tabindex="-1" id="statistics-offcanvas" aria-labelledby="statistics-offcanvas"> <div class="offcanvas-header"> <h5 class="offcanvas-title"></h5> <button type="button" class="btn-close text-reset" data-bs-dismiss="offcanvas" aria-label="Close"></button> </div> <div class="offcanvas-body small" data-context=""> <div style="margin-top: 20vh" class="centered-loader"><div class="loader"></div></div> <iframe class="-hidden"></iframe> </div> </div> <section class="related-version mt-3"> <h2>Related Versions</h2> <div class="content"> <ul> <li> <b>Full Version</b> <a href="https://arxiv.org/abs/2303.07210">https://arxiv.org/abs/2303.07210</a> </li> </ul> </div> </section> <section class="related-version mt-3"> <h2>Supplementary Materials</h2> <div class="content"> <ul> <li style="margin-bottom: 0.3em"> <span style="display: block;"> <b>Software</b> <i class="bi bi-github"></i> <a href="https://github.com/janba/GEL">https://github.com/janba/GEL</a> </span> <span style="display: block;">   <i class="bi bi-arrow-return-right"></i> browse <a href="#" class="btn-software-heritage" data-swh-id="swh:1:dir:91f125aa9a06d7adf992cdb11ca2108d86acdefe;origin=https://github.com/janba/GEL;visit=swh:1:snp:cdc61da5da61908a9968b02875e132058ae8288e;anchor=swh:1:rev:d4c98b30620cb01021ece84c68e96c10ebc2d480" data-title="Software" data-url="https://github.com/janba/GEL" > <img src="/images/software-heritage-logo-title.512px.png" style="height: 30px" alt="Software Heritage Logo"> <i class="bi bi-archive"></i> archived version </a> </span> </li> <li style="margin-bottom: 0.3em"> <span style="display: block;"> <b>Software (Supplementary repo for testing and additional variations)</b> <i class="bi bi-github"></i> <a href="https://github.com/Sgelet/GEL">https://github.com/Sgelet/GEL</a> </span> <span style="display: block;">   <i class="bi bi-arrow-return-right"></i> browse <a href="#" class="btn-software-heritage" data-swh-id="swh:1:dir:09aadd7e8f82cc8dfdbbc72ea71e56e65a6e0cfc;origin=https://github.com/Sgelet/GEL;visit=swh:1:snp:0bfb48df5949c951bbd65734e9abe75be19595d2;anchor=swh:1:rev:76eb1be20acce8281f4207201d54a697bd4d5d2c" data-title="Software (Supplementary repo for testing and additional variations)" data-url="https://github.com/Sgelet/GEL" > <img src="/images/software-heritage-logo-title.512px.png" style="height: 30px" alt="Software Heritage Logo"> <i class="bi bi-archive"></i> archived version </a> </span> </li> </ul> </div> </section> <div class="offcanvas offcanvas-bottom" tabindex="-1" id="software-heritage-offcanvas" aria-labelledby="software-heritage-offcanvas"> <div class="offcanvas-header"> <h2 class="offcanvas-title" style="font-weight: bold"></h2> <button type="button" class="btn-close text-reset" data-bs-dismiss="offcanvas" aria-label="Close"></button> </div> <div class="small offcanvas-subtitle"></div> <div class="offcanvas-body small"> <div style="margin-top: 20vh" class="centered-loader"><div class="loader"></div></div> <iframe class="-hidden"></iframe> </div> </div> <section class="references mt-3"> <h2>References</h2> <div class="content"> <ol> <li> <span> Amine Abou-Rjeili and George Karypis. Multilevel algorithms for partitioning power-law graphs. In 20th International Parallel and Distributed Processing Symposium (IPDPS 2006), Proceedings, 25-29 April 2006, Rhodes Island, Greece. IEEE, 2006. URL: <a href="https://doi.org/10.1109/IPDPS.2006.1639360">https://doi.org/10.1109/IPDPS.2006.1639360</a>. </span> </li> <li> <span> Nina Amenta, Sunghee Choi, and Ravi Krishna Kolluri. The power crust. In David C. Anderson and Kunwoo Lee, editors, Sixth ACM Symposium on Solid Modeling and Applications, Sheraton Inn, Ann Arbor, Michigan, USA, June 4-8, 2001, pages 249-266. ACM, 2001. URL: <a href="https://doi.org/10.1145/376957.376986">https://doi.org/10.1145/376957.376986</a>. </span> </li> <li> <span> Kasra Arnavaz, Oswin Krause, Kilian Zepf, Jakob Andreas Bærentzen, Jelena M. Krivokapic, Silja Heilmann, Pia Nyeng, and Aasa Feragen. Quantifying topology in pancreatic tubular networks from live imaging 3d microscopy. Machine Learning for Biomedical Imaging, 1, 2022. URL: <a href="https://melba-journal.org/papers/2022:015.html">https://melba-journal.org/papers/2022:015.html</a>. </span> </li> <li> <span> Oscar Kin-Chung Au, Chiew-Lan Tai, Hung-Kuo Chu, Daniel Cohen-Or, and Tong-Yee Lee. Skeleton extraction by mesh contraction. ACM Trans. Graph., 27(3):44, 2008. URL: <a href="https://doi.org/10.1145/1360612.1360643">https://doi.org/10.1145/1360612.1360643</a>. </span> </li> <li> <span> Andreas Bærentzen and Eva Rotenberg. Skeletonization via local separators. ACM Trans. Graph., 40(5):187:1-187:18, 2021. URL: <a href="https://doi.org/10.1145/3459233">https://doi.org/10.1145/3459233</a>. </span> </li> <li> <span> Silvia Biasotti, Leila De Floriani, Bianca Falcidieno, Patrizio Frosini, Daniela Giorgi, Claudia Landi, Laura Papaleo, and Michela Spagnuolo. Describing shapes by geometrical-topological properties of real functions. ACM Comput. Surv., 40(4):12:1-12:87, 2008. URL: <a href="https://doi.org/10.1145/1391729.1391731">https://doi.org/10.1145/1391729.1391731</a>. </span> </li> <li> <span> Silvia Biasotti, Daniela Giorgi, Michela Spagnuolo, and Bianca Falcidieno. Reeb graphs for shape analysis and applications. Theor. Comput. Sci., 392(1-3):5-22, 2008. URL: <a href="https://doi.org/10.1016/j.tcs.2007.10.018">https://doi.org/10.1016/j.tcs.2007.10.018</a>. </span> </li> <li> <span> Angela Brennecke and Tobias Isenberg. 3d shape matching using skeleton graphs. In Thomas Schulze, Stefan Schlechtweg, and Volkmar Hinz, editors, Simulation und Visualisierung 2004 (SimVis 2004) 4-5 März 2004, Magdeburg, pages 299-310. SCS Publishing House e.V., 2004. URL: <a href="http://wwwisg.cs.uni-magdeburg.de/graphik/pub/files/Brennecke_2004_3SM.pdf">http://wwwisg.cs.uni-magdeburg.de/graphik/pub/files/Brennecke_2004_3SM.pdf</a>. </span> </li> <li> <span> Aydin Buluç, Henning Meyerhenke, Ilya Safro, Peter Sanders, and Christian Schulz. Recent advances in graph partitioning. In Lasse Kliemann and Peter Sanders, editors, Algorithm Engineering - Selected Results and Surveys, volume 9220 of Lecture Notes in Computer Science, pages 117-158. Springer International Publishing, 2016. URL: <a href="https://doi.org/10.1007/978-3-319-49487-6_4">https://doi.org/10.1007/978-3-319-49487-6_4</a>. </span> </li> <li> <span> J. Andreas Bærentzen. Gel. <a href="https://github.com/janba/GEL">https://github.com/janba/GEL</a>, 2022. </span> </li> <li> <span> Junjie Cao, Andrea Tagliasacchi, Matt Olson, Hao Zhang, and Zhixun Su. Point cloud skeletons via laplacian based contraction. In SMI 2010, Shape Modeling International Conference, Aix en Provence, France, June 21-23 2010, pages 187-197. IEEE Computer Society, 2010. URL: <a href="https://doi.org/10.1109/SMI.2010.25">https://doi.org/10.1109/SMI.2010.25</a>. </span> </li> <li> <span> Nicu D. Cornea, Deborah Silver, and Patrick Min. Curve-skeleton properties, applications, and algorithms. IEEE Trans. Vis. Comput. Graph., 13(3):530-548, 2007. URL: <a href="https://doi.org/10.1109/TVCG.2007.1002">https://doi.org/10.1109/TVCG.2007.1002</a>. </span> </li> <li> <span> Tamal K. Dey and Jian Sun. Defining and computing curve-skeletons with medial geodesic function. In Alla Sheffer and Konrad Polthier, editors, Proceedings of the Fourth Eurographics Symposium on Geometry Processing, Cagliari, Sardinia, Italy, June 26-28, 2006, volume 256 of ACM International Conference Proceeding Series, pages 143-152. Eurographics Association, 2006. URL: <a href="https://doi.org/10.2312/SGP/SGP06/143-152">https://doi.org/10.2312/SGP/SGP06/143-152</a>. </span> </li> <li> <span> William Harvey, Yusu Wang, and Rephael Wenger. A randomized O(m log m) time algorithm for computing reeb graphs of arbitrary simplicial complexes. In David G. Kirkpatrick and Joseph S. B. Mitchell, editors, Proceedings of the 26th ACM Symposium on Computational Geometry, Snowbird, Utah, USA, June 13-16, 2010, pages 267-276. ACM, 2010. URL: <a href="https://doi.org/10.1145/1810959.1811005">https://doi.org/10.1145/1810959.1811005</a>. </span> </li> <li> <span> M. Sabry Hassouna and Aly A. Farag. Variational curve skeletons using gradient vector flow. IEEE Trans. Pattern Anal. Mach. Intell., 31(12):2257-2274, 2009. URL: <a href="https://doi.org/10.1109/TPAMI.2008.271">https://doi.org/10.1109/TPAMI.2008.271</a>. </span> </li> <li> <span> Bruce Hendrickson and Robert W. Leland. A multi-level algorithm for partitioning graphs. In Sidney Karin, editor, Proceedings Supercomputing '95, San Diego, CA, USA, December 4-8, 1995, page 28. ACM, 1995. URL: <a href="https://doi.org/10.1145/224170.224228">https://doi.org/10.1145/224170.224228</a>. </span> </li> <li> <span> Jacob Holm, Kristian de Lichtenberg, and Mikkel Thorup. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. ACM, 48(4):723-760, 2001. URL: <a href="https://doi.org/10.1145/502090.502095">https://doi.org/10.1145/502090.502095</a>. </span> </li> <li> <span> Hui Huang, Shihao Wu, Daniel Cohen-Or, Minglun Gong, Hao Zhang, Guiqing Li, and Baoquan Chen. L_1-medial skeleton of point cloud. ACM Trans. Graph., 32(4):65:1-65:8, 2013. URL: <a href="https://doi.org/10.1145/2461912.2461913">https://doi.org/10.1145/2461912.2461913</a>. </span> </li> <li> <span> Andrei C. Jalba, Jacek Kustra, and Alexandru C. Telea. Surface and curve skeletonization of large 3d models on the GPU. IEEE Trans. Pattern Anal. Mach. Intell., 35(6):1495-1508, 2013. URL: <a href="https://doi.org/10.1109/TPAMI.2012.212">https://doi.org/10.1109/TPAMI.2012.212</a>. </span> </li> <li> <span> Wei Jiang, Kai Xu, Zhi-Quan Cheng, Ralph R. Martin, and Gang Dang. Curve skeleton extraction by coupled graph contraction and surface clustering. Graph. Model., 75(3):137-148, 2013. URL: <a href="https://doi.org/10.1016/j.gmod.2012.10.005">https://doi.org/10.1016/j.gmod.2012.10.005</a>. </span> </li> <li> <span> George Karypis and Vipin Kumar. Analysis of multilevel graph partitioning. In Sidney Karin, editor, Proceedings Supercomputing '95, San Diego, CA, USA, December 4-8, 1995, page 29. ACM, 1995. URL: <a href="https://doi.org/10.1145/224170.224229">https://doi.org/10.1145/224170.224229</a>. </span> </li> <li> <span> Mattia Natali, Silvia Biasotti, Giuseppe Patanè, and Bianca Falcidieno. Graph-based representations of point clouds. Graph. Model., 73(5):151-164, 2011. URL: <a href="https://doi.org/10.1016/j.gmod.2011.03.002">https://doi.org/10.1016/j.gmod.2011.03.002</a>. </span> </li> <li> <span> Valerio Pascucci, Giorgio Scorzelli, Peer-Timo Bremer, and Ajith Mascarenhas. Robust on-line computation of reeb graphs: simplicity and speed. ACM Trans. Graph., 26(3):58, 2007. URL: <a href="https://doi.org/10.1145/1276377.1276449">https://doi.org/10.1145/1276377.1276449</a>. </span> </li> <li> <span> Diane Perchet, Catalin I. Fetita, and Françoise J. Prêteux. Advanced navigation tools for virtual bronchoscopy. In Edward R. Dougherty, Jaakko Astola, and Karen O. Egiazarian, editors, Image Processing: Algorithms and Systems III, San Jose, California, USA, January 18, 2004, volume 5298 of SPIE Proceedings, pages 147-158. SPIE, 2004. URL: <a href="https://doi.org/10.1117/12.533096">https://doi.org/10.1117/12.533096</a>. </span> </li> <li> <span> Dennie Reniers, Jarke J. van Wijk, and Alexandru C. Telea. Computing multiscale curve and surface skeletons of genus 0 shapes using a global importance measure. IEEE Trans. Vis. Comput. Graph., 14(2):355-368, 2008. URL: <a href="https://doi.org/10.1109/TVCG.2008.23">https://doi.org/10.1109/TVCG.2008.23</a>. </span> </li> <li> <span> Andrea Tagliasacchi, Ibraheem Alhashim, Matt Olson, and Hao Zhang. Mean curvature skeletons. Comput. Graph. Forum, 31(5):1735-1744, 2012. URL: <a href="https://doi.org/10.1111/j.1467-8659.2012.03178.x">https://doi.org/10.1111/j.1467-8659.2012.03178.x</a>. </span> </li> <li> <span> Andrea Tagliasacchi, Thomas Delamé, Michela Spagnuolo, Nina Amenta, and Alexandru C. Telea. 3d skeletons: A state-of-the-art report. Comput. Graph. Forum, 35(2):573-597, 2016. URL: <a href="https://doi.org/10.1111/cgf.12865">https://doi.org/10.1111/cgf.12865</a>. </span> </li> <li> <span> Alexandru C. Telea. 3d skeletonization benchmark. <a href="https://webspace.science.uu.nl/~telea001/Shapes/SkelBenchmark">https://webspace.science.uu.nl/~telea001/Shapes/SkelBenchmark</a>, 2016. Accessed: 2022-10-31. </span> </li> <li> <span> Alexandru C. Telea and Andrei C. Jalba. Computing curve skeletons from medial surfaces of 3d shapes. In Hamish A. Carr and Silvester Czanner, editors, Theory and Practice of Computer Graphics, Rutherford, United Kingdom, 2012. Proceedings, pages 99-106. Eurographics Association, 2012. URL: <a href="https://doi.org/10.2312/LocalChapterEvents/TPCG/TPCG12/099-106">https://doi.org/10.2312/LocalChapterEvents/TPCG/TPCG12/099-106</a>. </span> </li> <li> <span> Ming Wan, Frank Dachille, and Arie E. Kaufman. Distance-field-based skeletons for virtual navigation. In Thomas Ertl, Kenneth I. Joy, and Amitabh Varshney, editors, 12th IEEE Visualization Conference, IEEE Vis 2001, San Diego, CA, USA, October 24-26, 2001, Proceedings, pages 239-246. IEEE Computer Society, 2001. URL: <a href="https://doi.org/10.1109/VISUAL.2001.964517">https://doi.org/10.1109/VISUAL.2001.964517</a>. </span> </li> <li> <span> Yu-Shuen Wang and Tong-Yee Lee. Curve-skeleton extraction using iterative least squares optimization. IEEE Trans. Vis. Comput. Graph., 14(4):926-936, 2008. URL: <a href="https://doi.org/10.1109/TVCG.2008.38">https://doi.org/10.1109/TVCG.2008.38</a>. </span> </li> <li> <span> Yajie Yan, Kyle Sykes, Erin W. Chambers, David Letscher, and Tao Ju. Erosion thickness on medial axes of 3d shapes. ACM Trans. Graph., 35(4):38:1-38:12, 2016. URL: <a href="https://doi.org/10.1145/2897824.2925938">https://doi.org/10.1145/2897824.2925938</a>. </span> </li> </ol> </div> </section> </div> </div> </div> </div> <span class="_feedback-button"> <i class="bi bi-question-circle"></i> <span class="text">Questions / Remarks / Feedback</span> </span> <div class="_feedback-form -hidden"> <span class="_feedback-close">X</span> <p>Feedback for Dagstuhl Publishing</p> <div> <textarea class="form-control" name="_feedback"></textarea> <input class="form-control" type="text" name="name" autocomplete="off" placeholder="Name (optional)" maxlength="60"> <input class="form-control" type="email" name="email" autocomplete="off" placeholder="Email (optional)" maxlength="60"> <br> <button class="btn btn-sm btn-default">Send</button> </div> </div> <div class="alert alert-success _feedback-success -hidden"> <span class="glyphicon glyphicon-ok"></span> <h3>Thanks for your feedback!</h3> <div>Feedback submitted</div> <button class="btn btn-white _feedback-done">OK</button> </div> <div class="alert alert-danger _feedback-error -hidden"> <span class="glyphicon glyphicon-remove"></span> <h3>Could not send message</h3> <div>Please try again later or send an <a href="mailto:publishing@dagstuhl.de">E-mail</a></div> <button class="btn btn-white _feedback-done">OK</button> </div> <a class="scroll-up-button -hidden" href="#_top-of-page"> <i class="bi bi-arrow-up-circle"></i> </a> <footer class="page-footer dark"> <div class="container"> <h5>About DROPS</h5> <p>Schloss Dagstuhl - Leibniz Center for Informatics has been operating the Dagstuhl Research Online Publication Server (short: DROPS) since 2004. DROPS enables publication of the latest research findings in a fast, uncomplicated manner, in addition to providing unimpeded, open access to them. All the requisite metadata on each publication is administered in accordance with general guidelines pertaining to online publications (cf. Dublin Core). This enables the online publications to be authorized for citation and made accessible to a wide readership on a permanent basis. Access is free of charge for readers following the open access idea which fosters unimpeded access to scientific publications. </p> <ul style="margin-top: -0.5em"> <li><a href="https://drops.dagstuhl.de/docs/about">More about DROPS</a></li> </ul> </div> <div class="container"> <div class="row"> <div class="col-lg-6"> <h5>Instructions for Authors</h5> <div class="row"> <div class="col-sm-6"> <b>Dagstuhl Series</b><br> <ul> <li><a href="https://submission.dagstuhl.de/series/details/lipics#author">LIPIcs</a></li> <li><a href="https://submission.dagstuhl.de/series/details/oasics#author">OASIcs</a></li> <li><a href="https://submission.dagstuhl.de/series/details/dfu#author">Dagstuhl Follow-Ups</a></li> </ul> </div> <div class="col-sm-6"> <b>Dagstuhl Journals</b><br> <ul> <li><a href="https://submission.dagstuhl.de/series/details/darts#author">DARTS – Dagstuhl Artifacts Series</a></li> <li><a href="https://submission.dagstuhl.de/series/details/dagrep#author">Dagstuhl Reports</a></li> <li><a href="https://submission.dagstuhl.de/series/details/dagman#author">Dagstuhl Manifestos</a></li> <li><a href="https://submission.dagstuhl.de/series/details/lites#author">LITES</a></li> <li><a href="https://submission.dagstuhl.de/series/details/tgdk#author">TGDK – Transactions on Graph Data and Knowledge</a></li> </ul> </div> </div> </div> <div class="col-lg-6"> <h5>Instructions for Editors</h5> <div class="row"> <div class="col-sm-6"> <b>Dagstuhl Series</b><br> <ul> <li><a href="https://submission.dagstuhl.de/series/details/lipics#editor">LIPIcs</a></li> <li><a href="https://submission.dagstuhl.de/series/details/oasics#editor">OASIcs</a></li> <li><a href="https://submission.dagstuhl.de/series/details/dfu#editor">Dagstuhl Follow-Ups</a></li> </ul> </div> <div class="col-sm-6"> <b>Dagstuhl Journals</b><br> <ul> <li><a href="https://submission.dagstuhl.de/series/details/darts#editor">DARTS – Dagstuhl Artifacts Series</a></li> <li><a href="https://submission.dagstuhl.de/series/details/dagrep#editor">Dagstuhl Reports</a></li> <li><a href="https://submission.dagstuhl.de/series/details/dagman#editor">Dagstuhl Manifestos</a></li> <li><a href="https://submission.dagstuhl.de/series/details/lites#editor">LITES</a></li> <li><a href="https://submission.dagstuhl.de/series/details/tgdk#editor">TGDK – Transactions on Graph Data and Knowledge</a></li> </ul> </div> </div> </div> </div> </div> </footer> <div class="copyright"> © 2023-2024 <a href="https://www.dagstuhl.de">Schloss Dagstuhl – LZI GmbH</a> <a href="https://drops.dagstuhl.de/docs/about">About DROPS</a> <a href="https://drops.dagstuhl.de/docs/imprint">Imprint</a> <a href="https://drops.dagstuhl.de/docs/privacy">Privacy</a> <a href="https://www.dagstuhl.de/en/publishing/team">Contact</a> </div> <script type="text/javascript" src="https://drops.dagstuhl.de/js/jquery-3.6.0.min.js"></script> <script type="text/javascript" src="https://drops.dagstuhl.de/js/app.js?drops-core-2025-01-23.1"></script> <script type="text/javascript" src="https://drops.dagstuhl.de/js/popper.min.js"></script> <script type="text/javascript" src="https://drops.dagstuhl.de/js/circle-progress.js"></script> <script type="text/javascript"> $(document).ready(function() { const view = { statsServer: 'https://drops-stats.dagstuhl.de', animationStarted: false, isScrolledIntoView: function (elem) { const rect = elem.getBoundingClientRect(); const elemTop = rect.top; //const elemBottom = rect.bottom; // const elemHeight = rect.height; return (elemTop >= 0) && (elemTop <= window.innerHeight); }, progressCircle: function ($el) { $el.find('.circle').circleProgress({ value: 1, size: 80, fill: { color: '#555' }, animation: { duration: 1200 } }); }, countUp: function($el) { $el.find('.number').each(function() { const $this = $(this); const number = parseInt($this.attr('data-number')); let suffix = ''; if (number > 90000) { $this.text(Math.ceil(number/1000)+' k'); suffix = ' k'; } else if (number > 90000000) { $this.text(Math.ceil(number/1000000)+' m'); suffix = ' m'; } else { $this.text(Math.ceil(number)) } $({ Counter: 0 }).animate({ Counter: $this.text().replace(suffix, '').replace(',', '') }, { duration: 1000, easing: 'swing', step: function() { $this.text(Math.ceil(this.Counter).toString().replace(/\B(?=(\d{3})+(?!\d))/g, ",") + suffix); } }); }); }, checkVisibility: function() { const $container = $('.stats-total'); if (view.isScrolledIntoView($container[0])) { if (!view.animationStarted) { view.animationStarted = true; view.progressCircle($container); setTimeout(function() { view.countUp($container) }, 200); } } }, initialize: function() { $.ajax({ type: 'get', url: view.statsServer + '/api/external/drops2/document/10.4230/LIPIcs.SoCG.2023.13/-/stats', success: function (result) { $('.total-downloads .number').attr('data-number', result.total.downloads); $('.total-metadata-views .number').attr('data-number', result.total.clicks); window.addEventListener('scroll', view.checkVisibility); view.checkVisibility(); }, error: function () { $('.total-downloads .number').text(0); $('.total-metadata-views .number').text(0); window.addEventListener('scroll', view.checkVisibility); view.checkVisibility(); } }); } }; view.initialize(); }); </script> <script type="text/javascript"> $(document).ready(function() { const statistics = { statsServer: 'https://drops-stats.dagstuhl.de', showStatistics: function(e) { e.preventDefault(); const $offCanvas = $('#statistics-offcanvas'); const $iframe = $offCanvas.find('iframe'); const $loader = $offCanvas.find('.centered-loader'); $iframe.addClass('-hidden'); $loader.removeClass('-hidden'); $iframe[0].onload = function () { $iframe.removeClass('-hidden'); $loader.addClass('-hidden'); }.bind(this); const modeParameter = ''; const $target = $(e.currentTarget); const entityId = $target.attr('data-entity'); const title = $target.attr('data-title'); const embedUrl = statistics.statsServer + '/embed/external/drops2/' + entityId + modeParameter; let context = $offCanvas.find('.offcanvas-body').attr('data-context'); if (context === title) { context = ''; } if (context !== '') { context += '<br>'; } $offCanvas.find('.offcanvas-title').html(context + '<h2 style="font-weight: bold">' + title + '</h2>'); $offCanvas.offcanvas('show'); $offCanvas.find('iframe').attr('src', embedUrl); return false; }, initialize: function() { $('.btn-statistics').on('click', this.showStatistics); } }; statistics.initialize(); }); </script> <script type="text/javascript"> $(document).ready(function() { $('a.btn-software-heritage').click(function(e) { const permanentId = $(this).data('permanent-id') ?? null; const contentIndex = $(this).data('content-index') ?? null; if(permanentId !== null && contentIndex !== null) { $.ajax({ url: '/entities/' + permanentId + '/_investigation/content/' + contentIndex, type: 'get', }); } }); }); </script> <script type="text/javascript"> $(document).ready(function() { const $offCanvas = $('#software-heritage-offcanvas'); const $offCanvasTitle = $offCanvas.find('.offcanvas-title'); const $offCanvasSubtitle = $offCanvas.find('.offcanvas-subtitle'); const $iframe = $offCanvas.find('iframe'); const $loader = $offCanvas.find('.centered-loader'); $iframe[0].onload = function () { $iframe.removeClass('-hidden'); $loader.addClass('-hidden'); }.bind(this); $('.btn-software-heritage').on('click', function(event) { event.preventDefault(); const $target = $(event.currentTarget); console.log($target); const swhId = $target.data('swh-id'); const title = $target.data('title'); const url = $target.data('url'); const embedUrl = 'https://archive.softwareheritage.org/browse/embed/' + swhId; $offCanvasTitle.text('Archived Version: ' + title); $offCanvasSubtitle.html('(archived from <a href="' + url +'">'+url+'</a>)'); $iframe.addClass('-hidden'); $loader.removeClass('-hidden'); $iframe.attr('src', embedUrl); $offCanvas.offcanvas('show'); }); }); </script> <script type="text/javascript"> function _enableFeedback() { var $feedbackButton = $('._feedback-button, .fixed-beta-button'); var $feedbackClose = $('._feedback-close'); var $feedbackForm = $('._feedback-form'); var $feedbackSubmit = $('._feedback-form button'); var $textarea = $feedbackForm.find('textarea'); var $feedbackSuccess = $('._feedback-success'); var $feedbackError = $('._feedback-error'); var $feedbackDoneButton = $('._feedback-done'); $feedbackButton.addClass('_show'); $feedbackButton.on('click', function () { $feedbackButton.addClass('-hidden'); $feedbackForm.removeClass('-hidden'); $textarea.focus(); }); $feedbackClose.on('click', function () { $feedbackSuccess.addClass('-hidden'); $feedbackForm.addClass('-hidden'); $feedbackButton.removeClass('-hidden'); }); $feedbackDoneButton.on('click', function () { $feedbackError.addClass('-hidden'); $feedbackSuccess.addClass('-hidden'); $feedbackForm.addClass('-hidden'); $feedbackButton.removeClass('-hidden'); }); $feedbackSubmit.on('click', function () { var message = $textarea.val(); if (message === undefined) { message = ''; } if (message.trim() !== '') { $.ajax({ url: '/api/v1/feedback', type: 'post', data: { content: message, context: window.location.href, name: $('input[name="name"]').val(), email: $('input[name="email"]').val(), }, success: function (result) { if (result === 'success') { $textarea.val(''); $feedbackSuccess.removeClass('-hidden'); } else { $feedbackError.removeClass('-hidden'); } }, error: function () { $feedbackError.removeClass('-hidden'); } }); } }); } var _defer_counter = 0; function _defer(method) { if (window.jQuery) { method(); } else { if (_defer_counter < 20) { setTimeout(function () { _defer(method); console.log(_defer_counter); _defer_counter++; }, 500); } } } setTimeout(function() { _defer(_enableFeedback); }, 1000); </script> <script type="text/javascript"> $(document).ready(function() { const app = { maxScrollPos: window.innerWidth < 500 ? 100 // mobile : 400, // desktop $el : { navbarSearch: $('nav .navbar-search'), fixedSearchButton: $('.fixed-search-button'), copyToClipboard: $('.copy-to-clipboard') }, methods: { hideMenuOnScroll: function(scrollPos) { const $menu = $('nav.navbar.main'); const $stickySearch = $('.search.sticky'); const $banner = $('#_banner'); const $fixedSearchButton = $('.fixed-search-button'); if (scrollPos > app.maxScrollPos) { $menu.addClass('-hide'); $banner.addClass('-hide'); $stickySearch.addClass('-top'); $fixedSearchButton.addClass('-show'); } else { app.methods.showMenu(null, false); } }, showMenu: function(e, focus) { const $menu = $('nav.navbar.main'); const $stickySearch = $('.search.sticky'); const $banner = $('#_banner'); const $fixedSearchButton = $('.fixed-search-button'); $menu.removeClass('-hide'); $banner.removeClass('-hide'); $stickySearch.removeClass('-top'); $fixedSearchButton.removeClass('-show'); if (focus !== false) { $('.navbar-search').find('input[name="term"]').focus(); } }, showUpLinkOnScroll: function(scrollPos) { const $upLink = $('.scroll-up-button'); if (scrollPos > app.maxScrollPos) { $upLink.removeClass('-hidden'); } else { $upLink.addClass('-hidden'); } }, scrollHandler: function() { const scrollPos = $(document).scrollTop(); app.methods.hideMenuOnScroll(scrollPos); app.methods.showUpLinkOnScroll(scrollPos); }, copyToClipboard: function(e) { e.preventDefault(); const $current = $(e.currentTarget); // console.log($current.attr('data-selector')); const element = $('#'+$current.attr('data-selector'))[0]; console.log(element); element.select(); document.execCommand("copy"); const $success = $current.find('.bi-check'); $success.removeClass('-hidden'); setTimeout(function() { $success.addClass('-hidden'); }, 1000); }, initTooltips: function() { const tooltipTriggerList = [].slice.call(document.querySelectorAll('[data-bs-toggle="tooltip"]')) const tooltipList = tooltipTriggerList.map(function (tooltipTriggerEl) { return new bootstrap.Tooltip(tooltipTriggerEl) }); }, expandSearch: function() { app.$el.navbarSearch.addClass('expanded'); }, collapseSearch: function(e) { if (!$(e.currentTarget).is('button.btn-outline-success')) { app.$el.navbarSearch.removeClass('expanded'); } }, initDeepLinksTabs: function() { app.methods.initTabLinks(); const innerAnchors =[]; $('.tab-pane').find('[id]').each(function() { innerAnchors.push(this.getAttribute('id')); }); const anchors = []; $('a[role="tab"]').each(function() { anchors.push($(this).attr('aria-controls')); }); innerAnchors.forEach(function(anchor) { if ($('#'+anchor).length > 0) { anchors.push(anchor); } }); if (anchors.length === 0) { return; } let selectedAnchor = window.location.hash.substring(1); if (anchors.indexOf(selectedAnchor) === -1) { $('#publications-tab').tab('show'); window.scrollTo(0,0); return; } if (selectedAnchor !== 'publications') { const innerAnchorIndex = innerAnchors.indexOf(selectedAnchor); // anchor sits inside tab -> open the tab first, then scroll to anchor if (innerAnchorIndex > -1) { const $tab = $('#'+selectedAnchor).closest('.tab-pane'); console.log($tab); try { $('#'+$tab.attr('id')+'-tab').tab('show'); } catch (e) { } setTimeout(function () { $('#' + selectedAnchor)[0].scrollIntoView(); }, 800); } else { try { $('#' + selectedAnchor + '-tab').tab('show'); } catch (e) { } window.scrollTo(0, 0); } } }, initTabLinks: function() { $('[data-tab-link]').on('click', function(e) { e.preventDefault(); const $target = $(e.currentTarget); document.location.href = $target.attr('href'); document.location.reload(); }); }, }, initialize: function() { $(window).on('scroll', app.methods.scrollHandler); $(window).on('scroll-to-top', function() { window.scrollTo(0,0) }); $(document).trigger('scroll'); // set correct status for scroll-related parts (navbar/back-to-top) on page reload app.$el.copyToClipboard.on('click', app.methods.copyToClipboard); app.$el.fixedSearchButton.on('click', app.methods.showMenu); app.$el.navbarSearch.find('input').on('click', app.methods.expandSearch) app.$el.navbarSearch.find('input').on('blur', app.methods.collapseSearch); app.methods.initTooltips(); app.methods.initDeepLinksTabs(); } }; app.initialize(); }); </script> </body> </html>

CINXE.COM

Multilevel Skeletonization Using Local Separators