---
OA_place: publisher
OA_type: gold
_id: '22405'
abstract:
- lang: eng
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."
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"
article_number: 54:1-54:22
article_processing_charge: No
arxiv: 1
author:
- first_name: Timothy M.
full_name: Chan, Timothy M.
last_name: Chan
orcid: 0000-0002-8093-0675
- first_name: Hsien-Chih
full_name: Chang, Hsien-Chih
last_name: Chang
orcid: 0000-0001-6714-7988
- first_name: Jie
full_name: Gao, Jie
last_name: Gao
orcid: 0000-0001-5083-6082
- 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
- first_name: Da Wei
full_name: Zheng, Da Wei
id: af77956b-e859-11ef-8dc9-d301b898e32f
last_name: Zheng
citation:
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: 53rd
International Colloquium on Automata, Languages, and Programming. Vol 374.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2026. doi:10.4230/LIPICS.ICALP.2026.54'
apa: 'Chan, T. M., Chang, H.-C., Gao, J., Kisfaludi-Bak, S., Le, H., & Zheng,
D. W. (2026). Charting the landscape of diameter computation on geometric intersection
graphs in the plane. In 53rd International Colloquium on Automata, Languages,
and Programming (Vol. 374). Egham, United Kingdom: Schloss Dagstuhl - Leibniz-Zentrum
für Informatik. https://doi.org/10.4230/LIPICS.ICALP.2026.54'
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 53rd International Colloquium on Automata,
Languages, and Programming, Vol. 374. Schloss Dagstuhl - Leibniz-Zentrum für
Informatik, 2026. https://doi.org/10.4230/LIPICS.ICALP.2026.54.
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 53rd International Colloquium on Automata, Languages, and
Programming, 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.'
mla: Chan, Timothy M., et al. “Charting the Landscape of Diameter Computation on
Geometric Intersection Graphs in the Plane.” 53rd International Colloquium
on Automata, Languages, and Programming, vol. 374, 54:1-54:22, Schloss Dagstuhl
- Leibniz-Zentrum für Informatik, 2026, doi:10.4230/LIPICS.ICALP.2026.54.
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.
conference:
end_date: 2026-07-10
location: Egham, United Kingdom
name: 'ICALP: Automata, Languages and Programming'
start_date: 2026-07-07
corr_author: '1'
das_tickbox: '0'
date_created: 2026-07-27T05:53:08Z
date_published: 2026-07-01T00:00:00Z
date_updated: 2026-08-12T09:03:26Z
day: '01'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPICS.ICALP.2026.54
external_id:
arxiv:
- '2605.10692'
file:
- access_level: open_access
checksum: 1e66eba4cfe4e74ab28108b1ca0bb956
content_type: application/pdf
creator: dernst
date_created: 2026-07-27T06:20:41Z
date_updated: 2026-07-27T06:20:41Z
file_id: '22407'
file_name: 2026_LIPIcSICALP_Chan.pdf
file_size: 1440497
relation: main_file
success: 1
file_date_updated: 2026-07-27T06:20:41Z
fulldoi: https://doi.org/10.4230/LIPICS.ICALP.2026.54
has_accepted_license: '1'
intvolume: ' 374'
keyword:
- String graphs
- Fine-grained complexity
- Theory of computation → Computational geometry
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
month: '07'
oa: 1
oa_version: Published Version
project:
- _id: bda196b2-d553-11ed-ba76-8e8ee6c21103
grant_number: I05982
name: Static and Dynamic Hierarchical Graph Decompositions
publication: 53rd International Colloquium on Automata, Languages, and Programming
publication_identifier:
eissn:
- 1868-8969
- '9783959774284'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: no
title: Charting the landscape of diameter computation on geometric intersection graphs
in the plane
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 374
year: '2026'
...
---
OA_place: publisher
OA_type: gold
_id: '22299'
abstract:
- lang: eng
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.
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"
alternative_title:
- LIPIcs
article_number: 41:1-41:18
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Michał
full_name: Lipiński, Michał
id: dfffb474-4317-11ee-8f5c-fe3fc95a425e
last_name: Lipiński
orcid: 0000-0001-9789-9750
- first_name: Marian
full_name: Mrozek, Marian
last_name: Mrozek
orcid: 0000-0002-0619-6417
- first_name: Manuel
full_name: Soriano Trigueros, Manuel
id: 15ebd7cf-15bf-11ee-aebd-bb4bb5121ea8
last_name: Soriano Trigueros
orcid: 0000-0003-2449-1433
- first_name: Fedor
full_name: Zimin, Fedor
id: afd27eda-91c1-11f0-aad8-c6edbec24c04
last_name: Zimin
citation:
ama: 'Edelsbrunner H, Lipiński M, Mrozek M, Soriano Trigueros M, Zimin F. The depth
poset under transpositions in the filter. In: 42nd International Symposium
on Computational Geometry. Vol 367. Schloss Dagstuhl - Leibniz-Zentrum für
Informatik; 2026. doi:10.4230/LIPICS.SOCG.2026.41'
apa: 'Edelsbrunner, H., Lipiński, M., Mrozek, M., Soriano Trigueros, M., & Zimin,
F. (2026). The depth poset under transpositions in the filter. In 42nd International
Symposium on Computational Geometry (Vol. 367). New Brunswick, NJ, United
States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.SOCG.2026.41'
chicago: Edelsbrunner, Herbert, Michał Lipiński, Marian Mrozek, Manuel Soriano Trigueros,
and Fedor Zimin. “The Depth Poset under Transpositions in the Filter.” In 42nd
International Symposium on Computational Geometry, Vol. 367. Schloss Dagstuhl
- Leibniz-Zentrum für Informatik, 2026. https://doi.org/10.4230/LIPICS.SOCG.2026.41.
ieee: H. Edelsbrunner, M. Lipiński, M. Mrozek, M. Soriano Trigueros, and F. Zimin,
“The depth poset under transpositions in the filter,” in 42nd International
Symposium on Computational Geometry, New Brunswick, NJ, United States, 2026,
vol. 367.
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.'
mla: Edelsbrunner, Herbert, et al. “The Depth Poset under Transpositions in the
Filter.” 42nd International Symposium on Computational Geometry, vol. 367,
41:1-41:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, doi:10.4230/LIPICS.SOCG.2026.41.
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.
conference:
end_date: 2026-06-05
location: New Brunswick, NJ, United States
name: 'SoCG: Symposium on Computational Geometry'
start_date: 2026-06-02
corr_author: '1'
das_tickbox: '0'
date_created: 2026-07-13T09:56:38Z
date_published: 2026-05-27T00:00:00Z
date_updated: 2026-08-12T09:02:56Z
day: '27'
ddc:
- '500'
department:
- _id: HeEd
- _id: GradSch
doi: 10.4230/LIPICS.SOCG.2026.41
ec_funded: 1
external_id:
arxiv:
- '2511.21961'
file:
- access_level: open_access
checksum: 9dfb96ee66985c724b499b0e5888dc8e
content_type: application/pdf
creator: dernst
date_created: 2026-07-14T06:08:05Z
date_updated: 2026-07-14T06:08:05Z
file_id: '22329'
file_name: 2026_LIPIcSSoCG_Edelsbrunner.pdf
file_size: 2902144
relation: main_file
success: 1
file_date_updated: 2026-07-14T06:08:05Z
fulldoi: https://doi.org/10.4230/LIPICS.SOCG.2026.41
has_accepted_license: '1'
intvolume: ' 367'
keyword:
- Algebraic topology
- Lefschetz complexes
- persistent homology
- vines and vineyards
- birth-death pairs
- shallow pairs
- relations
- partial orders
- transpositions
- Theory of computation → Computational geometry
language:
- iso: eng
month: '05'
oa: 1
oa_version: Published Version
project:
- _id: 2561EBF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: I02979-N35
name: Persistence and stability of geometric complexes
- _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c
call_identifier: H2020
grant_number: '101034413'
name: 'IST-BRIDGE: International postdoctoral program'
publication: 42nd International Symposium on Computational Geometry
publication_identifier:
eissn:
- 1868-8969
isbn:
- '9783959774185'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: no
title: The depth poset under transpositions in the filter
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 367
year: '2026'
...
---
_id: '17203'
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."
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).
article_number: '78'
article_processing_charge: Yes (via OA deal)
article_type: original
author:
- first_name: Christian
full_name: Hafner, Christian
id: 400429CC-F248-11E8-B48F-1D18A9856A87
last_name: Hafner
- first_name: Mickaël
full_name: Ly, Mickaël
id: 6340d7f0-b48d-11eb-b10d-b7487e71d9f1
last_name: Ly
- first_name: Christopher J
full_name: Wojtan, Christopher J
id: 3C61F1D2-F248-11E8-B48F-1D18A9856A87
last_name: Wojtan
orcid: 0000-0001-6646-5546
citation:
ama: 'Hafner C, Ly M, Wojtan C. Spin-it faster: Quadrics solve all topology optimization
problems that depend only on mass moments. Transactions on Graphics. 2024;43(4).
doi:10.1145/3658194'
apa: '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. Denver, Colorado: Association for Computing Machinery. https://doi.org/10.1145/3658194'
chicago: 'Hafner, Christian, Mickaël Ly, and Chris Wojtan. “Spin-It Faster: Quadrics
Solve All Topology Optimization Problems That Depend Only on Mass Moments.” Transactions
on Graphics. Association for Computing Machinery, 2024. https://doi.org/10.1145/3658194.'
ieee: 'C. Hafner, M. Ly, and C. Wojtan, “Spin-it faster: Quadrics solve all topology
optimization problems that depend only on mass moments,” Transactions on Graphics,
vol. 43, no. 4. Association for Computing Machinery, 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.'
mla: 'Hafner, Christian, et al. “Spin-It Faster: Quadrics Solve All Topology Optimization
Problems That Depend Only on Mass Moments.” Transactions on Graphics, vol.
43, no. 4, 78, Association for Computing Machinery, 2024, doi:10.1145/3658194.'
short: C. Hafner, M. Ly, C. Wojtan, Transactions on Graphics 43 (2024).
conference:
end_date: 2024-08-01
location: Denver, Colorado
start_date: 2024-07-28
corr_author: '1'
das_tickbox: '0'
date_created: 2024-07-05T12:08:57Z
date_published: 2024-07-01T00:00:00Z
date_updated: 2026-10-01T09:30:01Z
day: '01'
ddc:
- '516'
department:
- _id: ChWo
doi: 10.1145/3658194
external_id:
isi:
- '001289270900045'
file:
- access_level: open_access
checksum: 0dc9f5a6422b8a49a79026900f349ee5
content_type: application/pdf
creator: chafner
date_created: 2024-07-05T12:05:17Z
date_updated: 2024-07-05T12:05:17Z
file_id: '17204'
file_name: sif-final.pdf
file_size: 7225150
relation: main_file
success: 1
- access_level: open_access
checksum: cde433c6a40688d5f1187fb5721f6f94
content_type: application/pdf
creator: chafner
date_created: 2024-07-05T12:06:03Z
date_updated: 2024-07-05T12:06:03Z
file_id: '17205'
file_name: sif-supp-final.pdf
file_size: 397262
relation: supplementary_material
- access_level: open_access
checksum: c0457a09c2ab9a1c2935c995dcc84907
content_type: video/mp4
creator: chafner
date_created: 2024-07-17T09:29:13Z
date_updated: 2024-07-17T09:29:13Z
file_id: '17276'
file_name: sif-video-final.mp4
file_size: 170001305
relation: supplementary_material
title: Submission Video
file_date_updated: 2024-07-17T09:29:13Z
fulldoi: https://doi.org/10.1145/3658194
has_accepted_license: '1'
intvolume: ' 43'
isi: 1
issue: '4'
keyword:
- Topology Optimization
- Mass Moments
- Computational Geometry
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
project:
- _id: 34bc2376-11ca-11ed-8bc3-9a3b3961a088
grant_number: '101045083'
name: Computational Discovery of Numerical Algorithms for Animation and Simulation
of Natural Phenomena
publication: Transactions on Graphics
publication_identifier:
eissn:
- 1557-7368
issn:
- 0730-0301
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: yes
title: 'Spin-it faster: Quadrics solve all topology optimization problems that depend
only on mass moments'
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 43
year: '2024'
...
---
_id: '13188'
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."
acknowledged_ssus:
- _id: M-Shop
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).
article_number: '171'
article_processing_charge: No
article_type: original
author:
- first_name: Christian
full_name: Hafner, Christian
id: 400429CC-F248-11E8-B48F-1D18A9856A87
last_name: Hafner
- first_name: Bernd
full_name: Bickel, Bernd
id: 49876194-F248-11E8-B48F-1D18A9856A87
last_name: Bickel
orcid: 0000-0001-6511-9385
citation:
ama: Hafner C, Bickel B. The design space of Kirchhoff rods. ACM Transactions
on Graphics. 2023;42(5). doi:10.1145/3606033
apa: Hafner, C., & Bickel, B. (2023). The design space of Kirchhoff rods. ACM
Transactions on Graphics. Association for Computing Machinery. https://doi.org/10.1145/3606033
chicago: Hafner, Christian, and Bernd Bickel. “The Design Space of Kirchhoff Rods.”
ACM Transactions on Graphics. Association for Computing Machinery, 2023.
https://doi.org/10.1145/3606033.
ieee: C. Hafner and B. Bickel, “The design space of Kirchhoff rods,” ACM Transactions
on Graphics, vol. 42, no. 5. Association for Computing Machinery, 2023.
ista: Hafner C, Bickel B. 2023. The design space of Kirchhoff rods. ACM Transactions
on Graphics. 42(5), 171.
mla: Hafner, Christian, and Bernd Bickel. “The Design Space of Kirchhoff Rods.”
ACM Transactions on Graphics, vol. 42, no. 5, 171, Association for Computing
Machinery, 2023, doi:10.1145/3606033.
short: C. Hafner, B. Bickel, ACM Transactions on Graphics 42 (2023).
corr_author: '1'
date_created: 2023-07-04T07:41:30Z
date_published: 2023-09-20T00:00:00Z
date_updated: 2026-10-11T22:30:08Z
day: '20'
ddc:
- '516'
department:
- _id: BeBi
doi: 10.1145/3606033
ec_funded: 1
external_id:
isi:
- '001086833300010'
file:
- access_level: open_access
checksum: 4954c1cfa487725bc156dcfec872478a
content_type: application/pdf
creator: chafner
date_created: 2023-07-04T08:11:28Z
date_updated: 2023-07-04T08:11:28Z
file_id: '13194'
file_name: kirchhoff-rods.pdf
file_size: 19635168
relation: main_file
success: 1
- access_level: open_access
checksum: 79c9975fbc82ff71f1767331d2204cca
content_type: application/pdf
creator: chafner
date_created: 2023-07-04T07:46:28Z
date_updated: 2023-07-04T07:46:28Z
file_id: '13190'
file_name: supp-main.pdf
file_size: 420909
relation: supplementary_material
title: Supplemental Material with Proofs
- access_level: open_access
checksum: 4ab647e4f03c711e1e6a5fc1eb8684db
content_type: application/pdf
creator: chafner
date_created: 2023-07-04T07:46:30Z
date_updated: 2023-07-04T07:46:30Z
file_id: '13191'
file_name: supp-cheat.pdf
file_size: 430086
relation: supplementary_material
title: Cheat Sheet for Notation
- access_level: open_access
checksum: c0fd9a57d012046de90c185ffa904b76
content_type: video/mp4
creator: chafner
date_created: 2023-07-04T07:46:39Z
date_updated: 2023-07-04T07:46:39Z
file_id: '13192'
file_name: kirchhoff-video-final.mp4
file_size: 268088064
relation: supplementary_material
title: Supplemental Video
- access_level: open_access
checksum: 71b00712b489ada2cd9815910ee180a9
content_type: application/x-zip-compressed
creator: chafner
date_created: 2023-07-04T07:47:10Z
date_updated: 2023-07-04T07:47:10Z
file_id: '13193'
file_name: matlab-submission.zip
file_size: 25790
relation: supplementary_material
title: Matlab Source Code with Example
file_date_updated: 2023-07-04T08:11:28Z
fulldoi: https://doi.org/10.1145/3606033
has_accepted_license: '1'
intvolume: ' 42'
isi: 1
issue: '5'
keyword:
- Computer Graphics
- Computational Design
- Computational Geometry
- Shape Modeling
language:
- iso: eng
month: '09'
oa: 1
oa_version: Submitted Version
project:
- _id: 24F9549A-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '715767'
name: 'MATERIALIZABLE: Intelligent fabrication-oriented Computational Design and
Modeling'
publication: ACM Transactions on Graphics
publication_identifier:
eissn:
- 1557-7368
issn:
- 0730-0301
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
related_material:
record:
- id: '12897'
relation: part_of_dissertation
status: public
scopus_import: '1'
status: public
title: The design space of Kirchhoff rods
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 42
year: '2023'
...
---
_id: '9817'
abstract:
- lang: eng
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.
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"
article_number: '126'
article_processing_charge: No
article_type: original
author:
- first_name: Christian
full_name: Hafner, Christian
id: 400429CC-F248-11E8-B48F-1D18A9856A87
last_name: Hafner
- first_name: Bernd
full_name: Bickel, Bernd
id: 49876194-F248-11E8-B48F-1D18A9856A87
last_name: Bickel
orcid: 0000-0001-6511-9385
citation:
ama: Hafner C, Bickel B. The design space of plane elastic curves. ACM Transactions
on Graphics. 2021;40(4). doi:10.1145/3450626.3459800
apa: 'Hafner, C., & Bickel, B. (2021). The design space of plane elastic curves.
ACM Transactions on Graphics. Virtual: Association for Computing Machinery.
https://doi.org/10.1145/3450626.3459800'
chicago: Hafner, Christian, and Bernd Bickel. “The Design Space of Plane Elastic
Curves.” ACM Transactions on Graphics. Association for Computing Machinery,
2021. https://doi.org/10.1145/3450626.3459800.
ieee: C. Hafner and B. Bickel, “The design space of plane elastic curves,” ACM
Transactions on Graphics, vol. 40, no. 4. Association for Computing Machinery,
2021.
ista: Hafner C, Bickel B. 2021. The design space of plane elastic curves. ACM Transactions
on Graphics. 40(4), 126.
mla: Hafner, Christian, and Bernd Bickel. “The Design Space of Plane Elastic Curves.”
ACM Transactions on Graphics, vol. 40, no. 4, 126, Association for Computing
Machinery, 2021, doi:10.1145/3450626.3459800.
short: C. Hafner, B. Bickel, ACM Transactions on Graphics 40 (2021).
conference:
end_date: 2021-08-13
location: Virtual
name: 'SIGGRAF: Special Interest Group on Computer Graphics and Interactive Techniques'
start_date: 2021-08-09
date_created: 2021-08-08T22:01:26Z
date_published: 2021-07-19T00:00:00Z
date_updated: 2026-10-11T22:30:08Z
day: '19'
ddc:
- '516'
department:
- _id: BeBi
doi: 10.1145/3450626.3459800
ec_funded: 1
external_id:
isi:
- '000674930900091'
file:
- access_level: open_access
checksum: 7e5d08ce46b0451b3102eacd3d00f85f
content_type: application/pdf
creator: chafner
date_created: 2021-10-18T10:42:15Z
date_updated: 2021-10-18T10:42:15Z
file_id: '10150'
file_name: elastic-curves-paper.pdf
file_size: 17064290
relation: main_file
success: 1
- access_level: open_access
checksum: 0088643478be7c01a703b5b10767348f
content_type: application/pdf
creator: chafner
date_created: 2021-10-18T10:42:22Z
date_updated: 2021-10-18T10:42:22Z
file_id: '10151'
file_name: elastic-curves-supp.pdf
file_size: 547156
relation: supplementary_material
file_date_updated: 2021-10-18T10:42:22Z
fulldoi: https://doi.org/10.1145/3450626.3459800
has_accepted_license: '1'
intvolume: ' 40'
isi: 1
issue: '4'
keyword:
- Computing methodologies
- shape modeling
- modeling and simulation
- theory of computation
- computational geometry
- mathematics of computing
- mathematical optimization
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
project:
- _id: 24F9549A-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '715767'
name: 'MATERIALIZABLE: Intelligent fabrication-oriented Computational Design and
Modeling'
publication: ACM Transactions on Graphics
publication_identifier:
eissn:
- 1557-7368
issn:
- 0730-0301
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
related_material:
link:
- description: News on IST Website
relation: press_release
url: https://ist.ac.at/en/news/designing-with-elastic-structures/
record:
- id: '12897'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: The design space of plane elastic curves
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 40
year: '2021'
...
---
OA_type: closed access
_id: '3994'
abstract:
- lang: eng
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.
article_processing_charge: No
article_type: original
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
citation:
ama: Cheng H, Edelsbrunner H. Area, perimeter and derivatives of a skin curve. Computational
Geometry. 2003;26(2):173-192. doi:10.1016/S0925-7721(02)00124-4
apa: Cheng, H., & Edelsbrunner, H. (2003). Area, perimeter and derivatives of
a skin curve. Computational Geometry. Elsevier. https://doi.org/10.1016/S0925-7721(02)00124-4
chicago: Cheng, Ho, and Herbert Edelsbrunner. “Area, Perimeter and Derivatives of
a Skin Curve.” Computational Geometry. Elsevier, 2003. https://doi.org/10.1016/S0925-7721(02)00124-4.
ieee: H. Cheng and H. Edelsbrunner, “Area, perimeter and derivatives of a skin curve,”
Computational Geometry, vol. 26, no. 2. Elsevier, pp. 173–192, 2003.
ista: Cheng H, Edelsbrunner H. 2003. Area, perimeter and derivatives of a skin curve.
Computational Geometry. 26(2), 173–192.
mla: Cheng, Ho, and Herbert Edelsbrunner. “Area, Perimeter and Derivatives of a
Skin Curve.” Computational Geometry, vol. 26, no. 2, Elsevier, 2003, pp.
173–92, doi:10.1016/S0925-7721(02)00124-4.
short: H. Cheng, H. Edelsbrunner, Computational Geometry 26 (2003) 173–192.
date_created: 2018-12-11T12:06:20Z
date_published: 2003-10-01T00:00:00Z
date_updated: 2026-05-06T08:12:09Z
day: '01'
doi: 10.1016/S0925-7721(02)00124-4
extern: '1'
fulldoi: https://doi.org/10.1016/S0925-7721(02)00124-4
intvolume: ' 26'
issue: '2'
keyword:
- Computational geometry
- Differential geometry
- Skin curves
- Voronoi diagrams
- Delaunay triangulations
- Filtrations
- Disks
- Hyperbolas
- Area
- Perimeter
- Derivatives
language:
- iso: eng
month: '10'
oa_version: None
page: 173 - 192
publication: Computational Geometry
publication_status: published
publisher: Elsevier
publist_id: '2135'
quality_controlled: '1'
status: public
title: Area, perimeter and derivatives of a skin curve
type: journal_article
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
volume: 26
year: '2003'
...
---
_id: '4097'
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.
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.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Leonidas
full_name: Guibas, Leonidas
last_name: Guibas
- first_name: János
full_name: Pach, János
last_name: Pach
- first_name: Richard
full_name: Pollack, Richard
last_name: Pollack
- first_name: Raimund
full_name: Seidel, Raimund
last_name: Seidel
- first_name: Micha
full_name: Sharir, Micha
last_name: Sharir
citation:
ama: 'Edelsbrunner H, Guibas L, Pach J, Pollack R, Seidel R, Sharir M. Arrangements
of curves in the plane - topology, combinatorics, and algorithms. In: 15th
International Colloquium on Automata, Languages and Programming. Vol 317.
Springer; 1988:214-229. doi:10.1007/3-540-19488-6_118'
apa: 'Edelsbrunner, H., Guibas, L., Pach, J., Pollack, R., Seidel, R., & Sharir,
M. (1988). Arrangements of curves in the plane - topology, combinatorics, and
algorithms. In 15th International Colloquium on Automata, Languages and Programming
(Vol. 317, pp. 214–229). Tampere, Finland: Springer. https://doi.org/10.1007/3-540-19488-6_118'
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 15th International Colloquium on Automata, Languages and
Programming, 317:214–29. Springer, 1988. https://doi.org/10.1007/3-540-19488-6_118.
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 15th International Colloquium on Automata, Languages and Programming,
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.'
mla: Edelsbrunner, Herbert, et al. “Arrangements of Curves in the Plane - Topology,
Combinatorics, and Algorithms.” 15th International Colloquium on Automata,
Languages and Programming, vol. 317, Springer, 1988, pp. 214–29, doi:10.1007/3-540-19488-6_118.
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.
conference:
end_date: 1988-07-15
location: Tampere, Finland
name: 'ICALP: Automata, Languages and Programming'
start_date: 1988-07-11
date_created: 2018-12-11T12:06:55Z
date_published: 1988-01-01T00:00:00Z
date_updated: 2022-02-08T10:15:09Z
day: '01'
doi: 10.1007/3-540-19488-6_118
extern: '1'
fulldoi: https://doi.org/10.1007/3-540-19488-6_118
intvolume: ' 317'
keyword:
- line segment
- computational geometry
- Jordan curve
- cell decomposition
- vertical tangency
language:
- iso: eng
main_file_link:
- url: https://link.springer.com/chapter/10.1007/3-540-19488-6_118
month: '01'
oa_version: None
page: 214 - 229
publication: 15th International Colloquium on Automata, Languages and Programming
publication_identifier:
isbn:
- 978-3-540-19488-0
publication_status: published
publisher: Springer
publist_id: '2028'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Arrangements of curves in the plane - topology, combinatorics, and algorithms
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 317
year: '1988'
...