[{"year":"2026","citation":{"ieee":"T. M. Chan, H.-C. Chang, J. Gao, S. Kisfaludi-Bak, H. Le, and D. W. Zheng, “Charting the landscape of diameter computation on geometric intersection graphs in the plane,” in <i>53rd International Colloquium on Automata, Languages, and Programming</i>, Egham, United Kingdom, 2026, vol. 374.","ista":"Chan TM, Chang H-C, Gao J, Kisfaludi-Bak S, Le H, Zheng DW. 2026. Charting the landscape of diameter computation on geometric intersection graphs in the plane. 53rd International Colloquium on Automata, Languages, and Programming. ICALP: Automata, Languages and Programming vol. 374, 54:1-54:22.","apa":"Chan, T. M., Chang, H.-C., Gao, J., Kisfaludi-Bak, S., Le, H., &#38; Zheng, D. W. (2026). Charting the landscape of diameter computation on geometric intersection graphs in the plane. In <i>53rd International Colloquium on Automata, Languages, and Programming</i> (Vol. 374). Egham, United Kingdom: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPICS.ICALP.2026.54\">https://doi.org/10.4230/LIPICS.ICALP.2026.54</a>","short":"T.M. Chan, H.-C. Chang, J. Gao, S. Kisfaludi-Bak, H. Le, D.W. Zheng, in:, 53rd International Colloquium on Automata, Languages, and Programming, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026.","chicago":"Chan, Timothy M., Hsien-Chih Chang, Jie Gao, Sándor Kisfaludi-Bak, Hung Le, and Da Wei Zheng. “Charting the Landscape of Diameter Computation on Geometric Intersection Graphs in the Plane.” In <i>53rd International Colloquium on Automata, Languages, and Programming</i>, Vol. 374. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. <a href=\"https://doi.org/10.4230/LIPICS.ICALP.2026.54\">https://doi.org/10.4230/LIPICS.ICALP.2026.54</a>.","ama":"Chan TM, Chang H-C, Gao J, Kisfaludi-Bak S, Le H, Zheng DW. Charting the landscape of diameter computation on geometric intersection graphs in the plane. In: <i>53rd International Colloquium on Automata, Languages, and Programming</i>. Vol 374. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2026. doi:<a href=\"https://doi.org/10.4230/LIPICS.ICALP.2026.54\">10.4230/LIPICS.ICALP.2026.54</a>","mla":"Chan, Timothy M., et al. “Charting the Landscape of Diameter Computation on Geometric Intersection Graphs in the Plane.” <i>53rd International Colloquium on Automata, Languages, and Programming</i>, vol. 374, 54:1-54:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, doi:<a href=\"https://doi.org/10.4230/LIPICS.ICALP.2026.54\">10.4230/LIPICS.ICALP.2026.54</a>."},"researchdata_availability":"no","arxiv":1,"file":[{"creator":"dernst","relation":"main_file","content_type":"application/pdf","file_size":1440497,"file_id":"22407","file_name":"2026_LIPIcSICALP_Chan.pdf","checksum":"1e66eba4cfe4e74ab28108b1ca0bb956","access_level":"open_access","date_created":"2026-07-27T06:20:41Z","date_updated":"2026-07-27T06:20:41Z","success":1}],"intvolume":"       374","das_tickbox":"0","volume":374,"article_number":"54:1-54:22","_id":"22405","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"doi":"10.4230/LIPICS.ICALP.2026.54","date_published":"2026-07-01T00:00:00Z","type":"conference","status":"public","date_updated":"2026-08-12T09:03:26Z","abstract":[{"text":"Computing the diameter of the intersection graphs of objects is a basic problem in computational geometry. Previous works showed that the complexity of computing the diameter mainly depends on the object types: for unit disks and squares in 2D, the problem is solvable in truly subquadratic time [Chan et al., 2025], while for other objects, including unit segments and equilateral triangles in 2D or unit balls and axis-parallel unit cubes in 3D, there is no truly subquadratic time algorithm under the Orthogonal Vector (OV) hypothesis [Bringmann et al., 2022]. \r\nWe undertake a comprehensive study of computing the diameter of geometric intersection graphs for various types of objects. We discover many new irregularities, showing that the landscape is extremely nuanced: the source of hardness is a combination of the object type, the true diameter value, and how the objects intersect with each other. Our highlighted results for the 2D case include:  \r\n1) The diameter of non-degenerate, axis-aligned line segments can be computed in truly subquadratic time. Previous hardness result [Bringmann et al., 2022] for line segments applies only to degenerate instances. On the other hand, for the degenerate case, we show that a truly subquadratic time algorithm exists when the true diameter is constant. \r\n2) An almost-linear-time algorithm for unit-square graphs of constant diameter. Previous algorithms [Duraj et al., 2024; Chan et al., 2025] rely on succinct representation assuming bounded VC-dimension; for such a strategy Ω(n^{7/4}) time is an inherent barrier. \r\n3) An Õ(n^{4/3})-time algorithm to decide if the diameter of a unit-disk graph is at most 2. This improves upon the recent algorithm with running time Õ(n^{2-1/9}) [Chan et al., 2025]. \r\n4) Deciding if the diameter of intersection graphs of fat triangles or line segments is at most 2 is truly subquadratic-hard under fine-grained complexity assumptions. Previous lower bounds [Bringmann et al., 2022] only hold when deciding if diameter is at most 3.  Our findings are presented in a pair of papers. This paper focuses solely on the 2D case, while the companion paper is devoted to higher-dimensional cases.","lang":"eng"}],"external_id":{"arxiv":["2605.10692"]},"OA_type":"gold","OA_place":"publisher","title":"Charting the landscape of diameter computation on geometric intersection graphs in the plane","file_date_updated":"2026-07-27T06:20:41Z","publication_identifier":{"eissn":["1868-8969","9783959774284"]},"oa":1,"has_accepted_license":"1","author":[{"orcid":"0000-0002-8093-0675","last_name":"Chan","full_name":"Chan, Timothy M.","first_name":"Timothy M."},{"orcid":"0000-0001-6714-7988","last_name":"Chang","first_name":"Hsien-Chih","full_name":"Chang, Hsien-Chih"},{"orcid":"0000-0001-5083-6082","last_name":"Gao","full_name":"Gao, Jie","first_name":"Jie"},{"first_name":"Sándor","full_name":"Kisfaludi-Bak, Sándor","last_name":"Kisfaludi-Bak","orcid":"0000-0002-6856-2902"},{"first_name":"Hung","full_name":"Le, Hung","last_name":"Le","orcid":"0000-0001-8223-9944"},{"id":"af77956b-e859-11ef-8dc9-d301b898e32f","last_name":"Zheng","first_name":"Da Wei","full_name":"Zheng, Da Wei"}],"corr_author":"1","date_created":"2026-07-27T05:53:08Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","keyword":["String graphs","Fine-grained complexity","Theory of computation → Computational geometry"],"article_processing_charge":"No","oa_version":"Published Version","fulldoi":"https://doi.org/10.4230/LIPICS.ICALP.2026.54","quality_controlled":"1","supplementarymaterial":"no","month":"07","publication":"53rd International Colloquium on Automata, Languages, and Programming","language":[{"iso":"eng"}],"ddc":["000"],"publication_status":"published","day":"01","department":[{"_id":"MoHe"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","conference":{"end_date":"2026-07-10","start_date":"2026-07-07","location":"Egham, United Kingdom","name":"ICALP: Automata, Languages and Programming"},"acknowledgement":"Timothy M. Chan: Supported by NSF grant CCF-2224271.\r\nHsien-Chih Chang: Supported by NSF CAREER award CCF-2443017.\r\nJie Gao: Supported by NSF DMS-2220271, DMS-2311064, IIS-2229876, CCF-2118953, CNS-2515159.\r\nSándor Kisfaludi-Bak: Supported by the Research Council of Finland, Grant 363444.\r\nHung Le: Supported by an NSF grant CCF-2517033 and an NSF CAREER Award CCF-2237288.\r\nDa Wei Zheng: This project has received funding from the Austrian Science Fund (FWF) grant\r\nDOI 10.55776/I5982. For open access purposes, the author has applied a CC BY public copyright\r\nlicense to any author-accepted manuscript version arising from this submission.\r\n","project":[{"_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103","name":"Static and Dynamic Hierarchical Graph Decompositions","grant_number":"I05982"}],"scopus_import":"1"},{"year":"2026","arxiv":1,"researchdata_availability":"no","citation":{"chicago":"Edelsbrunner, Herbert, Michał Lipiński, Marian Mrozek, Manuel Soriano Trigueros, and Fedor Zimin. “The Depth Poset under Transpositions in the Filter.” In <i>42nd International Symposium on Computational Geometry</i>, Vol. 367. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. <a href=\"https://doi.org/10.4230/LIPICS.SOCG.2026.41\">https://doi.org/10.4230/LIPICS.SOCG.2026.41</a>.","ama":"Edelsbrunner H, Lipiński M, Mrozek M, Soriano Trigueros M, Zimin F. The depth poset under transpositions in the filter. In: <i>42nd International Symposium on Computational Geometry</i>. Vol 367. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2026. doi:<a href=\"https://doi.org/10.4230/LIPICS.SOCG.2026.41\">10.4230/LIPICS.SOCG.2026.41</a>","mla":"Edelsbrunner, Herbert, et al. “The Depth Poset under Transpositions in the Filter.” <i>42nd International Symposium on Computational Geometry</i>, vol. 367, 41:1-41:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, doi:<a href=\"https://doi.org/10.4230/LIPICS.SOCG.2026.41\">10.4230/LIPICS.SOCG.2026.41</a>.","ista":"Edelsbrunner H, Lipiński M, Mrozek M, Soriano Trigueros M, Zimin F. 2026. The depth poset under transpositions in the filter. 42nd International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 367, 41:1-41:18.","ieee":"H. Edelsbrunner, M. Lipiński, M. Mrozek, M. Soriano Trigueros, and F. Zimin, “The depth poset under transpositions in the filter,” in <i>42nd International Symposium on Computational Geometry</i>, New Brunswick, NJ, United States, 2026, vol. 367.","apa":"Edelsbrunner, H., Lipiński, M., Mrozek, M., Soriano Trigueros, M., &#38; Zimin, F. (2026). The depth poset under transpositions in the filter. In <i>42nd International Symposium on Computational Geometry</i> (Vol. 367). New Brunswick, NJ, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPICS.SOCG.2026.41\">https://doi.org/10.4230/LIPICS.SOCG.2026.41</a>","short":"H. Edelsbrunner, M. Lipiński, M. Mrozek, M. Soriano Trigueros, F. Zimin, in:, 42nd International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026."},"ec_funded":1,"das_tickbox":"0","intvolume":"       367","alternative_title":["LIPIcs"],"file":[{"creator":"dernst","content_type":"application/pdf","relation":"main_file","file_size":2902144,"checksum":"9dfb96ee66985c724b499b0e5888dc8e","file_name":"2026_LIPIcSSoCG_Edelsbrunner.pdf","file_id":"22329","date_updated":"2026-07-14T06:08:05Z","date_created":"2026-07-14T06:08:05Z","access_level":"open_access","success":1}],"article_number":"41:1-41:18","volume":367,"date_updated":"2026-08-12T09:02:56Z","status":"public","type":"conference","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"date_published":"2026-05-27T00:00:00Z","doi":"10.4230/LIPICS.SOCG.2026.41","_id":"22299","external_id":{"arxiv":["2511.21961"]},"abstract":[{"text":"The depth poset of a filtered Lefschetz complex reflects the dependencies between the cancellations of different shallow birth-death pairs. Using the fast algorithms for computing the depth poset in [Edelsbrunner et al., 2026] and for updating the persistence diagram under transpositions in [Cohen-Steiner et al., 2006], we give a complete case analysis of how transpositions of cells in the filter affect the depth poset. In addition, we present statistics on the depth poset for random point data and its sensitivity to the transpositions that occur in random straight-line homotopies.","lang":"eng"}],"oa":1,"file_date_updated":"2026-07-14T06:08:05Z","title":"The depth poset under transpositions in the filter","publication_identifier":{"eissn":["1868-8969"],"isbn":["9783959774185"]},"OA_type":"gold","OA_place":"publisher","author":[{"first_name":"Herbert","full_name":"Edelsbrunner, Herbert","last_name":"Edelsbrunner","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833"},{"first_name":"Michał","full_name":"Lipiński, Michał","last_name":"Lipiński","id":"dfffb474-4317-11ee-8f5c-fe3fc95a425e","orcid":"0000-0001-9789-9750"},{"first_name":"Marian","full_name":"Mrozek, Marian","orcid":"0000-0002-0619-6417","last_name":"Mrozek"},{"last_name":"Soriano Trigueros","orcid":"0000-0003-2449-1433","id":"15ebd7cf-15bf-11ee-aebd-bb4bb5121ea8","full_name":"Soriano Trigueros, Manuel","first_name":"Manuel"},{"full_name":"Zimin, Fedor","first_name":"Fedor","last_name":"Zimin","id":"afd27eda-91c1-11f0-aad8-c6edbec24c04"}],"has_accepted_license":"1","date_created":"2026-07-13T09:56:38Z","corr_author":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","month":"05","fulldoi":"https://doi.org/10.4230/LIPICS.SOCG.2026.41","supplementarymaterial":"no","quality_controlled":"1","oa_version":"Published Version","article_processing_charge":"Yes","keyword":["Algebraic topology","Lefschetz complexes","persistent homology","vines and vineyards","birth-death pairs","shallow pairs","relations","partial orders","transpositions","Theory of computation → Computational geometry"],"publication":"42nd International Symposium on Computational Geometry","publication_status":"published","ddc":["500"],"language":[{"iso":"eng"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","conference":{"name":"SoCG: Symposium on Computational Geometry","location":"New Brunswick, NJ, United States","start_date":"2026-06-02","end_date":"2026-06-05"},"day":"27","department":[{"_id":"HeEd"},{"_id":"GradSch"}],"scopus_import":"1","project":[{"name":"Persistence and stability of geometric complexes","_id":"2561EBF4-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"I02979-N35"},{"grant_number":"101034413","call_identifier":"H2020","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","name":"IST-BRIDGE: International postdoctoral program"}],"acknowledgement":"The authors thank Jakub Leśkiewicz and Bartosz Furmanek for discussions\r\nthat helped improve the paper. Herbert Edelsbrunner: DFG Collaborative Research Center TRR 109, Austrian Science\r\nFund (FWF), grant no. I 02979-N35\r\nMichał Lipiński: European Union’s Horizon 2020 research and innovation programme under the\r\nMarie Skłodowska-Curie Grant Agreement No. 101034413\r\nMarian Mrozek: Polish National Science Center under Opus Grant 2019/35/B/ST1/00874 and Opus\r\nGrant 2025/57/B/ST1/00550"},{"publication":"Transactions on Graphics","article_type":"original","publication_status":"published","language":[{"iso":"eng"}],"ddc":["516"],"publisher":"Association for Computing Machinery","department":[{"_id":"ChWo"}],"conference":{"location":"Denver, Colorado","start_date":"2024-07-28","end_date":"2024-08-01"},"day":"01","project":[{"name":"Computational Discovery of Numerical Algorithms for Animation and Simulation of Natural Phenomena","_id":"34bc2376-11ca-11ed-8bc3-9a3b3961a088","grant_number":"101045083"}],"isi":1,"acknowledgement":"We thank Gianmarco Cherchi for his help in tailoring the Mesh Booleans code for this project, Stefan Jeschke for his help with the photographs, Malina Strugaru and Aleksei Kalinov for their help with the samples, and the anonymous reviewers as well as the members of the ISTA Visual Computing Group for their feedback. This project was funded in part by the European Research Council (ERC Consolidator Grant 101045083 CoDiNA).","scopus_import":"1","author":[{"full_name":"Hafner, Christian","first_name":"Christian","last_name":"Hafner","id":"400429CC-F248-11E8-B48F-1D18A9856A87"},{"id":"6340d7f0-b48d-11eb-b10d-b7487e71d9f1","last_name":"Ly","first_name":"Mickaël","full_name":"Ly, Mickaël"},{"id":"3C61F1D2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-6646-5546","last_name":"Wojtan","full_name":"Wojtan, Christopher J","first_name":"Christopher J"}],"has_accepted_license":"1","corr_author":"1","date_created":"2024-07-05T12:08:57Z","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","oa_version":"Published Version","keyword":["Topology Optimization","Mass Moments","Computational Geometry"],"article_processing_charge":"Yes (via OA deal)","supplementarymaterial":"yes","fulldoi":"https://doi.org/10.1145/3658194","month":"07","quality_controlled":"1","volume":43,"article_number":"78","issue":"4","date_published":"2024-07-01T00:00:00Z","doi":"10.1145/3658194","_id":"17203","date_updated":"2026-10-01T09:30:01Z","type":"journal_article","status":"public","external_id":{"isi":["001289270900045"]},"abstract":[{"lang":"eng","text":"The behavior of a rigid body primarily depends on its mass moments, which consist of the mass, center of mass, and moments of inertia. It is possible to manipulate these quantities without altering the geometric appearance of an object by introducing cavities in its interior. Algorithms that find cavities of suitable shapes and sizes have enabled the computational design of spinning tops, yo-yos, wheels, buoys, and statically balanced objects. Previous work is based, for example, on topology optimization on voxel grids, which introduces a large number of optimization variables and box constraints, or offset surface computation, which cannot guarantee that solutions to a feasible problem will always be found.\r\n\r\nIn this work, we provide a mathematical analysis of constrained topology optimization problems that depend only on mass moments. This class of problems covers, among others, all applications mentioned above. Our main result is to show that no matter the outer shape of the rigid body to be optimized or the optimization objective and constraints considered, the optimal solution always features a quadric-shaped interface between material and cavities. This proves that optimal interfaces are always ellipsoids, hyperboloids, paraboloids, or one of a few degenerate cases, such as planes.\r\n\r\nThis insight lets us replace a difficult topology optimization problem with a provably equivalent non-linear equation system in a small number (<10) of variables, which represent the coefficients of the quadric. This system can be solved in a few seconds for most examples, provides insights into the geometric structure of many specific applications, and lets us describe their solution properties. Finally, our method integrates seamlessly into modern fabrication workflows because our solutions are analytical surfaces that are native to the CAD domain."}],"oa":1,"file_date_updated":"2024-07-17T09:29:13Z","publication_identifier":{"eissn":["1557-7368"],"issn":["0730-0301"]},"title":"Spin-it faster: Quadrics solve all topology optimization problems that depend only on mass moments","year":"2024","researchdata_availability":"no","citation":{"short":"C. Hafner, M. Ly, C. Wojtan, Transactions on Graphics 43 (2024).","ista":"Hafner C, Ly M, Wojtan C. 2024. Spin-it faster: Quadrics solve all topology optimization problems that depend only on mass moments. Transactions on Graphics. 43(4), 78.","ieee":"C. Hafner, M. Ly, and C. Wojtan, “Spin-it faster: Quadrics solve all topology optimization problems that depend only on mass moments,” <i>Transactions on Graphics</i>, vol. 43, no. 4. Association for Computing Machinery, 2024.","apa":"Hafner, C., Ly, M., &#38; Wojtan, C. (2024). Spin-it faster: Quadrics solve all topology optimization problems that depend only on mass moments. <i>Transactions on Graphics</i>. Denver, Colorado: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3658194\">https://doi.org/10.1145/3658194</a>","mla":"Hafner, Christian, et al. “Spin-It Faster: Quadrics Solve All Topology Optimization Problems That Depend Only on Mass Moments.” <i>Transactions on Graphics</i>, vol. 43, no. 4, 78, Association for Computing Machinery, 2024, doi:<a href=\"https://doi.org/10.1145/3658194\">10.1145/3658194</a>.","ama":"Hafner C, Ly M, Wojtan C. Spin-it faster: Quadrics solve all topology optimization problems that depend only on mass moments. <i>Transactions on Graphics</i>. 2024;43(4). doi:<a href=\"https://doi.org/10.1145/3658194\">10.1145/3658194</a>","chicago":"Hafner, Christian, Mickaël Ly, and Chris Wojtan. “Spin-It Faster: Quadrics Solve All Topology Optimization Problems That Depend Only on Mass Moments.” <i>Transactions on Graphics</i>. Association for Computing Machinery, 2024. <a href=\"https://doi.org/10.1145/3658194\">https://doi.org/10.1145/3658194</a>."},"file":[{"relation":"main_file","content_type":"application/pdf","file_size":7225150,"creator":"chafner","success":1,"file_id":"17204","file_name":"sif-final.pdf","checksum":"0dc9f5a6422b8a49a79026900f349ee5","access_level":"open_access","date_created":"2024-07-05T12:05:17Z","date_updated":"2024-07-05T12:05:17Z"},{"checksum":"cde433c6a40688d5f1187fb5721f6f94","file_name":"sif-supp-final.pdf","file_id":"17205","date_updated":"2024-07-05T12:06:03Z","access_level":"open_access","date_created":"2024-07-05T12:06:03Z","creator":"chafner","content_type":"application/pdf","relation":"supplementary_material","file_size":397262},{"file_size":170001305,"relation":"supplementary_material","content_type":"video/mp4","title":"Submission Video","creator":"chafner","access_level":"open_access","date_created":"2024-07-17T09:29:13Z","date_updated":"2024-07-17T09:29:13Z","file_id":"17276","file_name":"sif-video-final.mp4","checksum":"c0457a09c2ab9a1c2935c995dcc84907"}],"das_tickbox":"0","intvolume":"        43"},{"publisher":"Association for Computing Machinery","day":"20","department":[{"_id":"BeBi"}],"scopus_import":"1","acknowledgement":"We thank the anonymous reviewers for their generous feedback, and Julian Fischer for his help in proving Proposition 1. This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No. 715767).","isi":1,"project":[{"call_identifier":"H2020","grant_number":"715767","name":"MATERIALIZABLE: Intelligent fabrication-oriented Computational Design and Modeling","_id":"24F9549A-B435-11E9-9278-68D0E5697425"}],"publication":"ACM Transactions on Graphics","ddc":["516"],"language":[{"iso":"eng"}],"publication_status":"published","article_type":"original","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","fulldoi":"https://doi.org/10.1145/3606033","quality_controlled":"1","month":"09","keyword":["Computer Graphics","Computational Design","Computational Geometry","Shape Modeling"],"article_processing_charge":"No","oa_version":"Submitted Version","has_accepted_license":"1","author":[{"full_name":"Hafner, Christian","first_name":"Christian","id":"400429CC-F248-11E8-B48F-1D18A9856A87","last_name":"Hafner"},{"last_name":"Bickel","id":"49876194-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-6511-9385","first_name":"Bernd","full_name":"Bickel, Bernd"}],"date_created":"2023-07-04T07:41:30Z","acknowledged_ssus":[{"_id":"M-Shop"}],"corr_author":"1","abstract":[{"lang":"eng","text":"The Kirchhoff rod model describes the bending and twisting of slender elastic rods in three dimensions, and has been widely studied to enable the prediction of how a rod will deform, given its geometry and boundary conditions. In this work, we study a number of inverse problems with the goal of computing the geometry of a straight rod that will automatically deform to match a curved target shape after attaching its endpoints to a support structure. Our solution lets us finely control the static equilibrium state of a rod by varying the cross-sectional profiles along its length.\r\nWe also show that the set of physically realizable equilibrium states admits a concise geometric description in terms of linear line complexes, which leads to very efficient computational design algorithms. Implemented in an interactive software tool, they allow us to convert three-dimensional hand-drawn spline curves to elastic rods, and give feedback about the feasibility and practicality of a design in real time. We demonstrate the efficacy of our method by designing and manufacturing several physical prototypes with applications to interior design and soft robotics."}],"external_id":{"isi":["001086833300010"]},"title":"The design space of Kirchhoff rods","file_date_updated":"2023-07-04T08:11:28Z","publication_identifier":{"issn":["0730-0301"],"eissn":["1557-7368"]},"oa":1,"article_number":"171","issue":"5","volume":42,"related_material":{"record":[{"relation":"part_of_dissertation","id":"12897","status":"public"}]},"status":"public","type":"journal_article","date_updated":"2026-10-09T22:30:08Z","_id":"13188","doi":"10.1145/3606033","date_published":"2023-09-20T00:00:00Z","citation":{"chicago":"Hafner, Christian, and Bernd Bickel. “The Design Space of Kirchhoff Rods.” <i>ACM Transactions on Graphics</i>. Association for Computing Machinery, 2023. <a href=\"https://doi.org/10.1145/3606033\">https://doi.org/10.1145/3606033</a>.","ama":"Hafner C, Bickel B. The design space of Kirchhoff rods. <i>ACM Transactions on Graphics</i>. 2023;42(5). doi:<a href=\"https://doi.org/10.1145/3606033\">10.1145/3606033</a>","mla":"Hafner, Christian, and Bernd Bickel. “The Design Space of Kirchhoff Rods.” <i>ACM Transactions on Graphics</i>, vol. 42, no. 5, 171, Association for Computing Machinery, 2023, doi:<a href=\"https://doi.org/10.1145/3606033\">10.1145/3606033</a>.","apa":"Hafner, C., &#38; Bickel, B. (2023). The design space of Kirchhoff rods. <i>ACM Transactions on Graphics</i>. Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3606033\">https://doi.org/10.1145/3606033</a>","ista":"Hafner C, Bickel B. 2023. The design space of Kirchhoff rods. ACM Transactions on Graphics. 42(5), 171.","ieee":"C. Hafner and B. Bickel, “The design space of Kirchhoff rods,” <i>ACM Transactions on Graphics</i>, vol. 42, no. 5. Association for Computing Machinery, 2023.","short":"C. Hafner, B. Bickel, ACM Transactions on Graphics 42 (2023)."},"intvolume":"        42","ec_funded":1,"file":[{"file_name":"kirchhoff-rods.pdf","file_id":"13194","checksum":"4954c1cfa487725bc156dcfec872478a","access_level":"open_access","date_created":"2023-07-04T08:11:28Z","date_updated":"2023-07-04T08:11:28Z","success":1,"creator":"chafner","relation":"main_file","content_type":"application/pdf","file_size":19635168},{"file_id":"13190","file_name":"supp-main.pdf","checksum":"79c9975fbc82ff71f1767331d2204cca","access_level":"open_access","date_created":"2023-07-04T07:46:28Z","date_updated":"2023-07-04T07:46:28Z","relation":"supplementary_material","content_type":"application/pdf","file_size":420909,"creator":"chafner","title":"Supplemental Material with Proofs"},{"checksum":"4ab647e4f03c711e1e6a5fc1eb8684db","file_id":"13191","file_name":"supp-cheat.pdf","date_updated":"2023-07-04T07:46:30Z","access_level":"open_access","date_created":"2023-07-04T07:46:30Z","content_type":"application/pdf","relation":"supplementary_material","file_size":430086,"creator":"chafner","title":"Cheat Sheet for Notation"},{"file_id":"13192","file_name":"kirchhoff-video-final.mp4","checksum":"c0fd9a57d012046de90c185ffa904b76","access_level":"open_access","date_created":"2023-07-04T07:46:39Z","date_updated":"2023-07-04T07:46:39Z","creator":"chafner","title":"Supplemental Video","relation":"supplementary_material","content_type":"video/mp4","file_size":268088064},{"title":"Matlab Source Code with Example","creator":"chafner","file_size":25790,"content_type":"application/x-zip-compressed","relation":"supplementary_material","date_updated":"2023-07-04T07:47:10Z","access_level":"open_access","date_created":"2023-07-04T07:47:10Z","checksum":"71b00712b489ada2cd9815910ee180a9","file_id":"13193","file_name":"matlab-submission.zip"}],"year":"2023"},{"publication":"ACM Transactions on Graphics","language":[{"iso":"eng"}],"ddc":["516"],"publication_status":"published","article_type":"original","publisher":"Association for Computing Machinery","day":"19","department":[{"_id":"BeBi"}],"conference":{"name":"SIGGRAF: Special Interest Group on Computer Graphics and Interactive Techniques","end_date":"2021-08-13","location":"Virtual","start_date":"2021-08-09"},"acknowledgement":"We thank the anonymous reviewers for their generous feedback, and Michal Piovarči for his help in producing the supplemental video. This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 715767).\r\n","isi":1,"project":[{"grant_number":"715767","call_identifier":"H2020","_id":"24F9549A-B435-11E9-9278-68D0E5697425","name":"MATERIALIZABLE: Intelligent fabrication-oriented Computational Design and Modeling"}],"scopus_import":"1","has_accepted_license":"1","author":[{"id":"400429CC-F248-11E8-B48F-1D18A9856A87","last_name":"Hafner","first_name":"Christian","full_name":"Hafner, Christian"},{"orcid":"0000-0001-6511-9385","id":"49876194-F248-11E8-B48F-1D18A9856A87","last_name":"Bickel","first_name":"Bernd","full_name":"Bickel, Bernd"}],"date_created":"2021-08-08T22:01:26Z","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","keyword":["Computing methodologies","shape modeling","modeling and simulation","theory of computation","computational geometry","mathematics of computing","mathematical optimization"],"article_processing_charge":"No","oa_version":"Published Version","quality_controlled":"1","fulldoi":"https://doi.org/10.1145/3450626.3459800","month":"07","volume":40,"issue":"4","article_number":"126","_id":"9817","doi":"10.1145/3450626.3459800","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"date_published":"2021-07-19T00:00:00Z","type":"journal_article","status":"public","related_material":{"record":[{"id":"12897","status":"public","relation":"dissertation_contains"}],"link":[{"relation":"press_release","url":"https://ist.ac.at/en/news/designing-with-elastic-structures/","description":"News on IST Website"}]},"date_updated":"2026-10-09T22:30:08Z","abstract":[{"text":"Elastic bending of initially flat slender elements allows the realization and economic fabrication of intriguing curved shapes. In this work, we derive an intuitive but rigorous geometric characterization of the design space of plane elastic rods with variable stiffness. It enables designers to determine which shapes are physically viable with active bending by visual inspection alone. Building on these insights, we propose a method for efficiently designing the geometry of a flat elastic rod that realizes a target equilibrium curve, which only requires solving a linear program. We implement this method in an interactive computational design tool that gives feedback about the feasibility of a design, and computes the geometry of the structural elements necessary to realize it within an instant. The tool also offers an iterative optimization routine that improves the fabricability of a model while modifying it as little as possible. In addition, we use our geometric characterization to derive an algorithm for analyzing and recovering the stability of elastic curves that would otherwise snap out of their unstable equilibrium shapes by buckling. We show the efficacy of our approach by designing and manufacturing several physical models that are assembled from flat elements.","lang":"eng"}],"external_id":{"isi":["000674930900091"]},"publication_identifier":{"issn":["0730-0301"],"eissn":["1557-7368"]},"title":"The design space of plane elastic curves","file_date_updated":"2021-10-18T10:42:22Z","oa":1,"year":"2021","citation":{"short":"C. Hafner, B. Bickel, ACM Transactions on Graphics 40 (2021).","apa":"Hafner, C., &#38; Bickel, B. (2021). The design space of plane elastic curves. <i>ACM Transactions on Graphics</i>. Virtual: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3450626.3459800\">https://doi.org/10.1145/3450626.3459800</a>","ista":"Hafner C, Bickel B. 2021. The design space of plane elastic curves. ACM Transactions on Graphics. 40(4), 126.","ieee":"C. Hafner and B. Bickel, “The design space of plane elastic curves,” <i>ACM Transactions on Graphics</i>, vol. 40, no. 4. Association for Computing Machinery, 2021.","mla":"Hafner, Christian, and Bernd Bickel. “The Design Space of Plane Elastic Curves.” <i>ACM Transactions on Graphics</i>, vol. 40, no. 4, 126, Association for Computing Machinery, 2021, doi:<a href=\"https://doi.org/10.1145/3450626.3459800\">10.1145/3450626.3459800</a>.","ama":"Hafner C, Bickel B. The design space of plane elastic curves. <i>ACM Transactions on Graphics</i>. 2021;40(4). doi:<a href=\"https://doi.org/10.1145/3450626.3459800\">10.1145/3450626.3459800</a>","chicago":"Hafner, Christian, and Bernd Bickel. “The Design Space of Plane Elastic Curves.” <i>ACM Transactions on Graphics</i>. Association for Computing Machinery, 2021. <a href=\"https://doi.org/10.1145/3450626.3459800\">https://doi.org/10.1145/3450626.3459800</a>."},"file":[{"file_size":17064290,"relation":"main_file","content_type":"application/pdf","creator":"chafner","success":1,"date_created":"2021-10-18T10:42:15Z","access_level":"open_access","date_updated":"2021-10-18T10:42:15Z","file_name":"elastic-curves-paper.pdf","file_id":"10150","checksum":"7e5d08ce46b0451b3102eacd3d00f85f"},{"file_size":547156,"content_type":"application/pdf","relation":"supplementary_material","creator":"chafner","date_updated":"2021-10-18T10:42:22Z","access_level":"open_access","date_created":"2021-10-18T10:42:22Z","checksum":"0088643478be7c01a703b5b10767348f","file_name":"elastic-curves-supp.pdf","file_id":"10151"}],"intvolume":"        40","ec_funded":1},{"type":"journal_article","status":"public","date_updated":"2026-05-06T08:12:09Z","_id":"3994","date_published":"2003-10-01T00:00:00Z","doi":"10.1016/S0925-7721(02)00124-4","issue":"2","volume":26,"title":"Area, perimeter and derivatives of a skin curve","publist_id":"2135","OA_type":"closed access","abstract":[{"text":"The body defined by a finite collection of disks is a subset of the plane bounded by a tangent continuous curve, which we call the skin. We give analytic formulas for the area, the perimeter, the area derivative, and the perimeter derivative of the body. Given the filtrations of the Delaunay triangulation and the Voronoi diagram of the disks, all formulas can be evaluated in time proportional to the number of disks.","lang":"eng"}],"year":"2003","intvolume":"        26","extern":"1","citation":{"short":"H. Cheng, H. Edelsbrunner, Computational Geometry 26 (2003) 173–192.","apa":"Cheng, H., &#38; Edelsbrunner, H. (2003). Area, perimeter and derivatives of a skin curve. <i>Computational Geometry</i>. Elsevier. <a href=\"https://doi.org/10.1016/S0925-7721(02)00124-4\">https://doi.org/10.1016/S0925-7721(02)00124-4</a>","ista":"Cheng H, Edelsbrunner H. 2003. Area, perimeter and derivatives of a skin curve. Computational Geometry. 26(2), 173–192.","ieee":"H. Cheng and H. Edelsbrunner, “Area, perimeter and derivatives of a skin curve,” <i>Computational Geometry</i>, vol. 26, no. 2. Elsevier, pp. 173–192, 2003.","mla":"Cheng, Ho, and Herbert Edelsbrunner. “Area, Perimeter and Derivatives of a Skin Curve.” <i>Computational Geometry</i>, vol. 26, no. 2, Elsevier, 2003, pp. 173–92, doi:<a href=\"https://doi.org/10.1016/S0925-7721(02)00124-4\">10.1016/S0925-7721(02)00124-4</a>.","ama":"Cheng H, Edelsbrunner H. Area, perimeter and derivatives of a skin curve. <i>Computational Geometry</i>. 2003;26(2):173-192. doi:<a href=\"https://doi.org/10.1016/S0925-7721(02)00124-4\">10.1016/S0925-7721(02)00124-4</a>","chicago":"Cheng, Ho, and Herbert Edelsbrunner. “Area, Perimeter and Derivatives of a Skin Curve.” <i>Computational Geometry</i>. Elsevier, 2003. <a href=\"https://doi.org/10.1016/S0925-7721(02)00124-4\">https://doi.org/10.1016/S0925-7721(02)00124-4</a>."},"language":[{"iso":"eng"}],"publication_status":"published","article_type":"original","publication":"Computational Geometry","publisher":"Elsevier","day":"01","page":"173 - 192","date_created":"2018-12-11T12:06:20Z","author":[{"first_name":"Ho","full_name":"Cheng, Ho","last_name":"Cheng"},{"first_name":"Herbert","full_name":"Edelsbrunner, Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","last_name":"Edelsbrunner","orcid":"0000-0002-9823-6833"}],"month":"10","fulldoi":"https://doi.org/10.1016/S0925-7721(02)00124-4","quality_controlled":"1","keyword":["Computational geometry","Differential geometry","Skin curves","Voronoi diagrams","Delaunay triangulations","Filtrations","Disks","Hyperbolas","Area","Perimeter","Derivatives"],"article_processing_charge":"No","oa_version":"None","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd"},{"citation":{"chicago":"Edelsbrunner, Herbert, Leonidas Guibas, János Pach, Richard Pollack, Raimund Seidel, and Micha Sharir. “Arrangements of Curves in the Plane - Topology, Combinatorics, and Algorithms.” In <i>15th International Colloquium on Automata, Languages and Programming</i>, 317:214–29. Springer, 1988. <a href=\"https://doi.org/10.1007/3-540-19488-6_118\">https://doi.org/10.1007/3-540-19488-6_118</a>.","mla":"Edelsbrunner, Herbert, et al. “Arrangements of Curves in the Plane - Topology, Combinatorics, and Algorithms.” <i>15th International Colloquium on Automata, Languages and Programming</i>, vol. 317, Springer, 1988, pp. 214–29, doi:<a href=\"https://doi.org/10.1007/3-540-19488-6_118\">10.1007/3-540-19488-6_118</a>.","ama":"Edelsbrunner H, Guibas L, Pach J, Pollack R, Seidel R, Sharir M. Arrangements of curves in the plane - topology, combinatorics, and algorithms. In: <i>15th International Colloquium on Automata, Languages and Programming</i>. Vol 317. Springer; 1988:214-229. doi:<a href=\"https://doi.org/10.1007/3-540-19488-6_118\">10.1007/3-540-19488-6_118</a>","ieee":"H. Edelsbrunner, L. Guibas, J. Pach, R. Pollack, R. Seidel, and M. Sharir, “Arrangements of curves in the plane - topology, combinatorics, and algorithms,” in <i>15th International Colloquium on Automata, Languages and Programming</i>, Tampere, Finland, 1988, vol. 317, pp. 214–229.","ista":"Edelsbrunner H, Guibas L, Pach J, Pollack R, Seidel R, Sharir M. 1988. Arrangements of curves in the plane - topology, combinatorics, and algorithms. 15th International Colloquium on Automata, Languages and Programming. ICALP: Automata, Languages and Programming, LNCS, vol. 317, 214–229.","apa":"Edelsbrunner, H., Guibas, L., Pach, J., Pollack, R., Seidel, R., &#38; Sharir, M. (1988). Arrangements of curves in the plane - topology, combinatorics, and algorithms. In <i>15th International Colloquium on Automata, Languages and Programming</i> (Vol. 317, pp. 214–229). Tampere, Finland: Springer. <a href=\"https://doi.org/10.1007/3-540-19488-6_118\">https://doi.org/10.1007/3-540-19488-6_118</a>","short":"H. Edelsbrunner, L. Guibas, J. Pach, R. Pollack, R. Seidel, M. Sharir, in:, 15th International Colloquium on Automata, Languages and Programming, Springer, 1988, pp. 214–229."},"main_file_link":[{"url":"https://link.springer.com/chapter/10.1007/3-540-19488-6_118"}],"extern":"1","alternative_title":["LNCS"],"intvolume":"       317","year":"1988","abstract":[{"lang":"eng","text":"Arrangements of curves in the plane are of fundamental significance in many problems of computational and combinatorial geometry (e.g. motion planning, algebraic cell decomposition, etc.). In this paper we study various topological and combinatorial properties of such arrangements under some mild assumptions on the shape of the curves, and develop basic tools for the construction, manipulation, and analysis of these arrangements. Our main results include a generalization of the zone theorem of [EOS], [CGL] to arrangements of curves (in which we show that the combinatorial complexity of the zone of a curve is nearly linear in the number of curves), and an application of (some weaker variant of) that theorem to obtain a nearly quadratic incremental algorithm for the construction of such arrangements."}],"publist_id":"2028","publication_identifier":{"isbn":["978-3-540-19488-0"]},"title":"Arrangements of curves in the plane - topology, combinatorics, and algorithms","volume":317,"_id":"4097","doi":"10.1007/3-540-19488-6_118","date_published":"1988-01-01T00:00:00Z","type":"conference","status":"public","date_updated":"2022-02-08T10:15:09Z","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","article_processing_charge":"No","keyword":["line segment","computational geometry","Jordan curve","cell decomposition","vertical tangency"],"oa_version":"None","fulldoi":"https://doi.org/10.1007/3-540-19488-6_118","quality_controlled":"1","month":"01","author":[{"full_name":"Edelsbrunner, Herbert","first_name":"Herbert","last_name":"Edelsbrunner","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833"},{"last_name":"Guibas","full_name":"Guibas, Leonidas","first_name":"Leonidas"},{"last_name":"Pach","first_name":"János","full_name":"Pach, János"},{"last_name":"Pollack","first_name":"Richard","full_name":"Pollack, Richard"},{"last_name":"Seidel","full_name":"Seidel, Raimund","first_name":"Raimund"},{"full_name":"Sharir, Micha","first_name":"Micha","last_name":"Sharir"}],"date_created":"2018-12-11T12:06:55Z","page":"214 - 229","conference":{"start_date":"1988-07-11","location":"Tampere, Finland","end_date":"1988-07-15","name":"ICALP: Automata, Languages and Programming"},"day":"01","publisher":"Springer","acknowledgement":"Work on this paper by the first author has been supported by Amoco Fnd. Fac. Dev. Comput. Sci. 1-6-44862 and by the National Science Foundation under grant CCR-8714566. Work on this paper by the third and sixth authors has been supported by Office of Naval Research Grant N00014-82-K-0381, by National Science Foundation Grant No. NSF-DCR-83-20085, by grants from the Digital Equipment Corporation, and the IBM Corporation. Work by the sixth author has also been supported by a research grant from the NCRD — the Israeli National Council for Research and Development. Work by the fourth author has been supported by National Science Foundation Grant DMS-8501947.","scopus_import":"1","publication":"15th International Colloquium on Automata, Languages and Programming","language":[{"iso":"eng"}],"publication_status":"published"}]