---
OA_place: publisher
OA_type: gold
_id: '22000'
abstract:
- lang: eng
text: 'Simplicial approximation provides a framework for constructing simplicial
complexes that are homotopy equivalent to a given manifold, provided a CW structure
is explicitly known. However, its conventional implementation quickly becomes
intractable on a computer: barycentric subdivision produces poorly shaped simplices,
and the star condition introduces many vertices. To address these limitations,
this article develops a subdivision scheme based on spherical Delaunay triangulations,
which attains better refinement properties than barycentric subdivisions. Moreover,
the star condition is reframed as two independent problems, one geometric and
the other combinatorial, respectively tackled in the language of locally equiconnected
spaces and the list homomorphism problem, allowing an exponential reduction in
the number of vertices. Via a prototype implementation, we obtain simplicial complexes
homotopy equivalent to Grassmannians and Stiefel manifolds up to dimension 5.'
article_number: 93:1-93:22
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Raphaël
full_name: Tinarrage, Raphaël
id: 40ebcc9d-905f-11ef-bf0a-dc475da8a04e
last_name: Tinarrage
orcid: 0000-0002-1404-1095
citation:
ama: 'Tinarrage R. Simplicial approximation to CW complexes with spherical Delaunay
triangulations. In: 42nd International Symposium on Computational Geometry.
Vol 367. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2026. doi:10.4230/LIPIcs.SoCG.2026.93'
apa: 'Tinarrage, R. (2026). Simplicial approximation to CW complexes with spherical
Delaunay triangulations. 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.93'
chicago: Tinarrage, Raphaël. “Simplicial Approximation to CW Complexes with Spherical
Delaunay Triangulations.” 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.93.
ieee: R. Tinarrage, “Simplicial approximation to CW complexes with spherical Delaunay
triangulations,” in 42nd International Symposium on Computational Geometry,
New Brunswick, NJ, United States, 2026, vol. 367.
ista: 'Tinarrage R. 2026. Simplicial approximation to CW complexes with spherical
Delaunay triangulations. 42nd International Symposium on Computational Geometry.
SoCG: Symposium on Computational Geometry vol. 367, 93:1-93:22.'
mla: Tinarrage, Raphaël. “Simplicial Approximation to CW Complexes with Spherical
Delaunay Triangulations.” 42nd International Symposium on Computational Geometry,
vol. 367, 93:1-93:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026,
doi:10.4230/LIPIcs.SoCG.2026.93.
short: R. Tinarrage, 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-06-14T22:01:43Z
date_published: 2026-05-27T00:00:00Z
date_updated: 2026-06-22T11:28:26Z
day: '27'
ddc:
- '500'
department:
- _id: UlWa
doi: 10.4230/LIPIcs.SoCG.2026.93
external_id:
arxiv:
- '2112.07573'
file:
- access_level: open_access
checksum: a468edad327962309688aa78678138da
content_type: application/pdf
creator: dernst
date_created: 2026-06-22T07:53:13Z
date_updated: 2026-06-22T07:53:13Z
file_id: '22111'
file_name: 2026_LIPIcSSoCG_Tinarrage.pdf
file_size: 1436035
relation: main_file
success: 1
file_date_updated: 2026-06-22T07:53:13Z
fulldoi: https://doi.org/10.4230/LIPIcs.SoCG.2026.93
has_accepted_license: '1'
intvolume: ' 367'
keyword:
- Triangulation of manifolds
- Simplicial approximation
- CW complexes
- Delaunay complexes
- List homomorphism problem
- Topological Data Analysis
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
month: '05'
oa: 1
oa_version: Published Version
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'
related_material:
link:
- relation: software
url: https://doi.org/10.5281/zenodo.19251455
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: yes
title: Simplicial approximation to CW complexes with spherical Delaunay triangulations
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'
...
---
OA_place: publisher
OA_type: gold
_id: '22002'
abstract:
- lang: eng
text: Topological simplification is the process of reducing complexity of a function
while maintaining its essential features. Its goal is to find a new filter function,
which reorders cells of the input complex in a way which eliminates some persistent
homological features, without affecting the rest. We present a new approach to
simplification based on the concept of forbidden regions and combinatorial dynamics.
It allows us to reorder and cancel critical values, whose cancellation is not
possible using existing methods because they are not consecutive in the total
order. Each such cancellation takes O(c⋅n) time in the worst case, where c is
the number of birth-death pairs and n is the size of the input complex.
acknowledgement: "Jakub Leśkiewicz wants to thank his supervisor, Prof. Marian Mrozek,
forscientific guidance, patience, and opportunity to delay the rest of his duties
while writing this work.\r\nThe author also extends thanks to his entire family,
to Zuzanna Świątek, and to Mikołaj Kardyś,\r\nBEng, MSc, for providing meals during
the most intensive periods of work. Jakub Leśkiewicz: The research was partially
funded by the Polish National Science Center under Opus Grant No. 2019/35/B/ST1/00874
and Opus Grant 2025/57/B/ST1/00550. Bartosz Furmanek: The research was partially
funded by the Polish National Science Center under Opus Grant No. 2019/35/B/ST1/00874
and Opus Grant 2025/57/B/ST1/00550. Michał Lipiński: This project has received funding
from the European Union’s Horizon 2020 research and innovation programme under the
Marie Skłodowska-Curie Grant Agreement No. 101034413. \r\nDmitriy Morozov: This
work was supported in part by the U.S. Department of Energy, Office\r\nof Science,
Office of Advanced Scientific Computing Research, under Contract No. DE-AC02-\r\n05CH11231."
alternative_title:
- LIPIcs
article_number: 72:1-72:17
article_processing_charge: No
arxiv: 1
author:
- first_name: Jakub
full_name: Leśkiewicz, Jakub
last_name: Leśkiewicz
- first_name: Bartosz
full_name: Furmanek, Bartosz
last_name: Furmanek
- 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: Dmitriy
full_name: Morozov, Dmitriy
last_name: Morozov
citation:
ama: 'Leśkiewicz J, Furmanek B, Lipiński M, Morozov D. Topological simplification
guided by forbidden regions. In: 42nd International Symposium on Computational
Geometry. Vol 367. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2026.
doi:10.4230/LIPIcs.SoCG.2026.72'
apa: 'Leśkiewicz, J., Furmanek, B., Lipiński, M., & Morozov, D. (2026). Topological
simplification guided by forbidden regions. 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.72'
chicago: Leśkiewicz, Jakub, Bartosz Furmanek, Michał Lipiński, and Dmitriy Morozov.
“Topological Simplification Guided by Forbidden Regions.” 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.72.
ieee: J. Leśkiewicz, B. Furmanek, M. Lipiński, and D. Morozov, “Topological simplification
guided by forbidden regions,” in 42nd International Symposium on Computational
Geometry, New Brunswick, NJ, United States, 2026, vol. 367.
ista: 'Leśkiewicz J, Furmanek B, Lipiński M, Morozov D. 2026. Topological simplification
guided by forbidden regions. 42nd International Symposium on Computational Geometry.
SoCG: Symposium on Computational Geometry, LIPIcs, vol. 367, 72:1-72:17.'
mla: Leśkiewicz, Jakub, et al. “Topological Simplification Guided by Forbidden Regions.”
42nd International Symposium on Computational Geometry, vol. 367, 72:1-72:17,
Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, doi:10.4230/LIPIcs.SoCG.2026.72.
short: J. Leśkiewicz, B. Furmanek, M. Lipiński, D. Morozov, 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-06-14T22:01:43Z
date_published: 2026-05-27T00:00:00Z
date_updated: 2026-06-22T07:45:36Z
day: '27'
ddc:
- '500'
department:
- _id: HeEd
doi: 10.4230/LIPIcs.SoCG.2026.72
ec_funded: 1
external_id:
arxiv:
- '2603.16416'
file:
- access_level: open_access
checksum: 3be91c06fdf716c8735b6af64a09a921
content_type: application/pdf
creator: dernst
date_created: 2026-06-22T07:39:21Z
date_updated: 2026-06-22T07:39:21Z
file_id: '22110'
file_name: 2026_LIPIcSSoCG_Leskiewicz.pdf
file_size: 2052749
relation: main_file
success: 1
file_date_updated: 2026-06-22T07:39:21Z
fulldoi: https://doi.org/10.4230/LIPIcs.SoCG.2026.72
has_accepted_license: '1'
intvolume: ' 367'
keyword:
- persistent homology
- topological simplification
- depth posets
language:
- iso: eng
month: '05'
oa: 1
oa_version: Published Version
project:
- _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'
scopus_import: '1'
status: public
title: Topological simplification guided by forbidden regions
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'
...
---
OA_place: publisher
OA_type: gold
_id: '22003'
abstract:
- lang: eng
text: 'Let G be a finite, connected metric graph and let X be a subset of G. If
X is sufficiently dense in G, we show that the Gromov-Hausdorff distance matches
the Hausdorff distance, namely d_GH(G,X) = d_H(G,X). When the metric graph is
the circle G = S¹ with circumference 2π, a recent study established the equality
d_GH(S¹,X) = d_H(S¹,X) whenever d_GH(S¹,X) < π/6. Our results relax this hypothesis
to d_GH(S¹,X) < π/3, and furthermore, we show that the constant π/3 is the best
possible. We lower bound the Gromov-Hausdorff distance d_GH(G,X) by the Hausdorff
distance d_H(G,X) via a simple topological obstruction: the existence of a possibly
discontinuous function f: G → X with too small distortion contradicts the connectedness
of G.'
acknowledgement: "Funding Henry Adams: Simons Foundation Travel Support for Mathematicians.\r\nŽiga
Virk: Slovene research agency grant P1-0292.\r\nNicolò Zava: FWF Grant, Project
number I4245-N35.\r\n"
alternative_title:
- LIPIcs
article_number: 3:1-3:16
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Henry
full_name: Adams, Henry
last_name: Adams
- first_name: Sushovan
full_name: Majhi, Sushovan
last_name: Majhi
- first_name: Fedor
full_name: Manin, Fedor
last_name: Manin
- first_name: Ziga
full_name: Virk, Ziga
id: 2E36B656-F248-11E8-B48F-1D18A9856A87
last_name: Virk
- first_name: Nicolò
full_name: Zava, Nicolò
id: c8b3499c-7a77-11eb-b046-aa368cbbf2ad
last_name: Zava
orcid: 0000-0001-8686-1888
citation:
ama: 'Adams H, Majhi S, Manin F, Virk Z, Zava N. Lower bounding the Gromov–Hausdorff
distance in metric graphs. In: 42nd International Symposium on Computational
Geometry. Vol 367. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2026.
doi:10.4230/LIPIcs.SoCG.2026.3'
apa: 'Adams, H., Majhi, S., Manin, F., Virk, Z., & Zava, N. (2026). Lower bounding
the Gromov–Hausdorff distance in metric graphs. 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.3'
chicago: Adams, Henry, Sushovan Majhi, Fedor Manin, Ziga Virk, and Nicolò Zava.
“Lower Bounding the Gromov–Hausdorff Distance in Metric Graphs.” 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.3.
ieee: H. Adams, S. Majhi, F. Manin, Z. Virk, and N. Zava, “Lower bounding the Gromov–Hausdorff
distance in metric graphs,” in 42nd International Symposium on Computational
Geometry, New Brunswick, NJ, United States, 2026, vol. 367.
ista: 'Adams H, Majhi S, Manin F, Virk Z, Zava N. 2026. Lower bounding the Gromov–Hausdorff
distance in metric graphs. 42nd International Symposium on Computational Geometry.
SoCG: Symposium on Computational Geometry, LIPIcs, vol. 367, 3:1-3:16.'
mla: Adams, Henry, et al. “Lower Bounding the Gromov–Hausdorff Distance in Metric
Graphs.” 42nd International Symposium on Computational Geometry, vol. 367,
3:1-3:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, doi:10.4230/LIPIcs.SoCG.2026.3.
short: H. Adams, S. Majhi, F. Manin, Z. Virk, N. Zava, 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-06-14T22:01:44Z
date_published: 2026-05-27T00:00:00Z
date_updated: 2026-06-22T08:49:17Z
day: '27'
ddc:
- '500'
department:
- _id: HeEd
doi: 10.4230/LIPIcs.SoCG.2026.3
external_id:
arxiv:
- '2411.09182'
file:
- access_level: open_access
checksum: 25d27c016409563196b8aecfe5bfdf41
content_type: application/pdf
creator: dernst
date_created: 2026-06-22T08:43:47Z
date_updated: 2026-06-22T08:43:47Z
file_id: '22115'
file_name: 2026_LIPIcSSoCG_Adams.pdf
file_size: 1091310
relation: main_file
success: 1
file_date_updated: 2026-06-22T08:43:47Z
fulldoi: https://doi.org/10.4230/LIPIcs.SoCG.2026.3
has_accepted_license: '1'
intvolume: ' 367'
keyword:
- Gromov–Hausdorff distance
- distortion
- connectedness
- Borsuk–Ulam theorem
language:
- iso: eng
month: '05'
oa: 1
oa_version: Published Version
project:
- _id: 26AD5D90-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: I04245
name: Algebraic Footprints of Geometric Features in Homology
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'
scopus_import: '1'
status: public
title: Lower bounding the Gromov–Hausdorff distance in metric graphs
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'
...
---
OA_place: publisher
OA_type: gold
_id: '22004'
abstract:
- lang: eng
text: "Recent research on computing the diameter of geometric intersection graphs
has made significant strides, primarily focusing on the 2D case [Duraj et al.,
2024; Hsien-Chih Chang et al., 2024; Chan et al., 2025] where truly subquadratic-time
algorithms were given for simple objects such as unit-disks and (axis-aligned)
squares. However, in three or higher dimensions, there is no known truly subquadratic-time
algorithm for any intersection graph of non-trivial objects, even basic ones such
as unit balls or (axis-aligned) unit cubes. This was partially explained by the
pioneering work of Bringmann et al. [Karl Bringmann et al., 2022] which gave several
truly subquadratic lower bounds, notably for unit balls or unit cubes in 3D when
the graph diameter Δ is at least Ω(log n), hinting at a pessimistic outlook for
the complexity of the diameter problem in higher dimensions. In this paper, we
substantially extend the landscape of diameter computation for objects in three
and higher dimensions, giving a few positive results. Our highlighted findings
include: \r\n1) A truly subquadratic-time algorithm for deciding if the diameter
of unit cubes in 3D is at most 3 (Diameter-3 hereafter), the first algorithm of
its kind for objects in 3D or higher dimensions. Our algorithm is based on a novel
connection to pseudolines, which is of independent interest. \r\n2) A truly subquadratic
time lower bound for Diameter-3 of unit balls in 3D under the Orthogonal Vector
(OV) hypothesis, giving the first separation between unit balls and unit cubes
in the small diameter regime. Previously, computing the diameter for both objects
was known to be quadratic hard when the diameter is Ω(log n) [Karl Bringmann et
al., 2022]. \r\n3) A near-linear-time algorithm for Diameter-2 of unit cubes in
3D, generalizing the previous result for unit squares in 2D [Karl Bringmann et
al., 2022]. \r\n4) A truly subquadratic-time algorithm and lower bound for Diameter-2
and Diameter-3 of rectangular boxes (of arbitrary dimension and sizes), respectively."
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. Da 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 license
to any author-accepted manuscript version arising from this submission."
alternative_title:
- LIPIcs
article_number: 29:1-29:15
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Timothy M.
full_name: Chan, Timothy M.
last_name: Chan
- first_name: Hsien Chih
full_name: Chang, Hsien Chih
last_name: Chang
- first_name: Jie
full_name: Gao, Jie
last_name: Gao
- first_name: Sándor
full_name: Kisfaludi-Bak, Sándor
last_name: Kisfaludi-Bak
- first_name: Hung
full_name: Le, Hung
last_name: Le
- first_name: Da Wei
full_name: Zheng, Da Wei
id: af77956b-e859-11ef-8dc9-d301b898e32f
last_name: Zheng
citation:
ama: 'Chan TM, Chang HC, Gao J, Kisfaludi-Bak S, Le H, Zheng DW. Charting the diameter
computation landscape of intersection graphs in 3D and above. In: 42nd International
Symposium on Computational Geometry. Vol 367. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik; 2026. doi:10.4230/LIPIcs.SoCG.2026.29'
apa: 'Chan, T. M., Chang, H. C., Gao, J., Kisfaludi-Bak, S., Le, H., & Zheng,
D. W. (2026). Charting the diameter computation landscape of intersection graphs
in 3D and above. 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.29'
chicago: Chan, Timothy M., Hsien Chih Chang, Jie Gao, Sándor Kisfaludi-Bak, Hung
Le, and Da Wei Zheng. “Charting the Diameter Computation Landscape of Intersection
Graphs in 3D and Above.” 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.29.
ieee: T. M. Chan, H. C. Chang, J. Gao, S. Kisfaludi-Bak, H. Le, and D. W. Zheng,
“Charting the diameter computation landscape of intersection graphs in 3D and
above,” in 42nd International Symposium on Computational Geometry, New
Brunswick, NJ, United States, 2026, vol. 367.
ista: 'Chan TM, Chang HC, Gao J, Kisfaludi-Bak S, Le H, Zheng DW. 2026. Charting
the diameter computation landscape of intersection graphs in 3D and above. 42nd
International Symposium on Computational Geometry. SoCG: Symposium on Computational
Geometry, LIPIcs, vol. 367, 29:1-29:15.'
mla: Chan, Timothy M., et al. “Charting the Diameter Computation Landscape of Intersection
Graphs in 3D and Above.” 42nd International Symposium on Computational Geometry,
vol. 367, 29:1-29:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026,
doi:10.4230/LIPIcs.SoCG.2026.29.
short: T.M. Chan, H.C. Chang, J. Gao, S. Kisfaludi-Bak, H. Le, D.W. Zheng, 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-06-14T22:01:44Z
date_published: 2026-05-27T00:00:00Z
date_updated: 2026-06-22T08:37:44Z
day: '27'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.SoCG.2026.29
external_id:
arxiv:
- '2603.21790'
file:
- access_level: open_access
checksum: ffff03934cc182757d6db82d88f896e6
content_type: application/pdf
creator: dernst
date_created: 2026-06-22T08:34:11Z
date_updated: 2026-06-22T08:34:11Z
file_id: '22114'
file_name: 2026_LIPIcSSoCG_Chan.pdf
file_size: 918197
relation: main_file
success: 1
file_date_updated: 2026-06-22T08:34:11Z
fulldoi: https://doi.org/10.4230/LIPIcs.SoCG.2026.29
has_accepted_license: '1'
intvolume: ' 367'
keyword:
- Graph Diameter
- Geometric Intersection Graphs
- Unit Ball Graphs
language:
- iso: eng
month: '05'
oa: 1
oa_version: Published Version
project:
- _id: bda196b2-d553-11ed-ba76-8e8ee6c21103
grant_number: I05982
name: Static and Dynamic Hierarchical Graph Decompositions
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'
scopus_import: '1'
status: public
title: Charting the diameter computation landscape of intersection graphs in 3D and
above
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'
...
---
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'
...