14 Search Results for "Bjerkevik, Håvard Bakke"

Document
DOI: 10.4230/LIPIcs.SoCG.2026.16
Flip Distance of Non-Crossing Spanning Trees: NP-Hardness and Improved Bounds

Authors: Håvard Bakke Bjerkevik, Joseph Dorfer, Linda Kleist, Torsten Ueckerdt, and Birgit Vogtenhuber

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
We consider the problem of reconfiguring non-crossing spanning trees on point sets. For a set P of n points in general position in the plane, the flip graph ℱ(P) has a vertex for each non-crossing spanning tree on P and an edge between any two spanning trees that can be transformed into each other by the exchange of a single edge (coined a flip). This flip graph has been intensively studied, lately with an emphasis on determining its diameter diam(ℱ(P)) for sets P of n points in convex position. For this case, the current best bounds are 14/9⋅n - O(1) ≤ diam(ℱ(P)) < 15/9⋅n - 3, obtained in a recent breakthrough work [Bjerkevik, Kleist, Ueckerdt, and Vogtenhuber; SODA 2025]. The crucial tool for both the upper and lower bound are so-called conflict graphs, which the authors stated might be the key ingredient for determining the diameter (up to lower-order terms). In this paper, we pick up the concept of conflict graphs from the above-mentioned work and show that this tool is even more versatile than previously hoped. As our first main result, we use conflict graphs to show that computing the flip distance between two non-crossing spanning trees is NP-hard, even for point sets in convex position. Interestingly, the result still holds for more constrained flip operations, concretely, compatible flips (where the removed and the added edge do not cross) and rotations (where the removed and the added edge share an endpoint). Additionally, we present new insights on the diameter of the flip graph, by this directly extending the line of research from [BKUV SODA25]. Their lower bound is based on a constant-size pair of trees, one of which is of a type we refer to as stacked. We show that if one of the trees is stacked, then the lower bound is indeed optimal up to a constant term, that is, there exists a flip sequence of length at most 14/9⋅(n-1) to any other tree. Lastly, we improve the lower bound on the diameter of the flip graph ℱ(P) for n points in convex position to 11/7⋅n-o(n).
Cite as

Håvard Bakke Bjerkevik, Joseph Dorfer, Linda Kleist, Torsten Ueckerdt, and Birgit Vogtenhuber. Flip Distance of Non-Crossing Spanning Trees: NP-Hardness and Improved Bounds. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 16:1-16:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bjerkevik_et_al:LIPIcs.SoCG.2026.16,
  author =	{Bjerkevik, H\r{a}vard Bakke and Dorfer, Joseph and Kleist, Linda and Ueckerdt, Torsten and Vogtenhuber, Birgit},
  title =	{{Flip Distance of Non-Crossing Spanning Trees: NP-Hardness and Improved Bounds}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{16:1--16:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.16},
  URN =		{urn:nbn:de:0030-drops-258225},
  doi =		{10.4230/LIPIcs.SoCG.2026.16},
  annote =	{Keywords: Non-crossing, spanning tree, plane graph, flip graph, reconfiguration, diameter, complexity, NP-hard, edge exchange, compatible flip, rotation, happy edge property}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.6
Estimating the Persistent Homology of ℝⁿ-Valued Functions Using Function-Geometric Multifiltrations

Authors: Ethan André, Jingyi Li, David Loiseaux, and Steve Oudot

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
Given an unknown ℝⁿ-valued function f on a metric space X, can we approximate the persistent homology of f from a finite sampling of X with known pairwise distances and function values? This question has been answered in the case n = 1, assuming f is Lipschitz continuous and X is a sufficiently regular geodesic metric space, and using filtered geometric complexes with fixed scale parameter for the approximation. In this paper we answer the question for arbitrary n, under similar assumptions and using function-geometric multifiltrations. Our analysis offers a different view on these multifiltrations by focusing on their approximation properties rather than on their stability properties. We also leverage the multiparameter setting to provide insight into the influence of the scale parameter, whose choice is central to this type of approach. From a practical standpoint, we show that our approximation results are robust to input noise, and that function-geometric multifiltrations have good statistical convergence properties. We also provide an algorithm to compute our estimators, and we use its implementation to conduct extensive experiments, on both synthetic and real biological data, in order to validate our theoretical results.
Cite as

Ethan André, Jingyi Li, David Loiseaux, and Steve Oudot. Estimating the Persistent Homology of ℝⁿ-Valued Functions Using Function-Geometric Multifiltrations. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 6:1-6:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{andre_et_al:LIPIcs.SoCG.2026.6,
  author =	{Andr\'{e}, Ethan and Li, Jingyi and Loiseaux, David and Oudot, Steve},
  title =	{{Estimating the Persistent Homology of \mathbb{R}ⁿ-Valued Functions Using Function-Geometric Multifiltrations}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{6:1--6:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.6},
  URN =		{urn:nbn:de:0030-drops-258120},
  doi =		{10.4230/LIPIcs.SoCG.2026.6},
  annote =	{Keywords: Topological data analysis, multi-parameter persistent homology, function-Rips multifiltration}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.47
Computing the Skyscraper Invariant

Authors: Marc Fersztand and Jan Jendrysiak

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
We develop the first algorithms for computing the Skyscraper Invariant [FJNT24]. This is a filtration of the classical rank invariant for multiparameter persistence modules defined by the Harder-Narasimhan filtrations along every central charge supported at a single parameter value. Cheng’s algorithm [Cheng24] can be used to compute HN filtrations of arbitrary acyclic quiver representations in polynomial time in the total dimension, but in practice, the large dimension of persistence modules makes this direct approach infeasible. We show that by exploiting the additivity of the HN filtration and the special central charges, one can get away with a brute-force approach. For d-parameter modules, this produces an FPT ε-approximate algorithm with runtime dominated by 𝒪(1/ε^d ⋅ T_dec), where T_dec is the time for decomposition, which we compute with aida [DJK25]. We show that the wall-and-chamber structure of the module can be computed via lower envelopes of degree d - 1 polynomials. This allows for an exact computation of the Skyscraper Invariant roughly in 𝒪(n^d ⋅ T_dec) time for n the size of the presentation and enables a fast hybrid algorithm. For 2-parameter modules, we have implemented not only our algorithms but also, for the first time, Cheng’s algorithm. We compare all algorithms and, as a proof of concept for data analysis, compute a filtered version of the Multiparameter Landscape for biomedical data.
Cite as

Marc Fersztand and Jan Jendrysiak. Computing the Skyscraper Invariant. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 47:1-47:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{fersztand_et_al:LIPIcs.SoCG.2026.47,
  author =	{Fersztand, Marc and Jendrysiak, Jan},
  title =	{{Computing the Skyscraper Invariant}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{47:1--47:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.47},
  URN =		{urn:nbn:de:0030-drops-258535},
  doi =		{10.4230/LIPIcs.SoCG.2026.47},
  annote =	{Keywords: Topological Data Analysis, Multiparameter Persistence, Persistence, Harder-Narasimhan Filtration, Skyscraper Invariant}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.62
Computing the Bottleneck Distance Between Persistent Homology Transforms

Authors: Michael Kerber and Elena Xinyi Wang

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
The Persistent Homology Transform (PHT) summarizes a shape in ℝ^m by collecting persistence diagrams obtained from linear height filtrations in all directions on 𝕊^{m-1}. It enjoys strong theoretical guarantees, including continuity, stability, and injectivity. A natural way to compare two PHTs is to use the bottleneck distance between their diagrams as the direction varies. Prior work has either compared PHTs by sampling directions or, in 2D, computed the exact integral of bottleneck distance over all angles via a kinetic data structure. We improve the integral objective to Õ(n⁵) in place of the earlier Õ(n⁶) bound, where n denotes the number of simplices. For the max objective, we give an Õ(n³) expected-time algorithm in ℝ² and an Õ(n⁵) expected-time algorithm in ℝ³.
Cite as

Michael Kerber and Elena Xinyi Wang. Computing the Bottleneck Distance Between Persistent Homology Transforms. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 62:1-62:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{kerber_et_al:LIPIcs.SoCG.2026.62,
  author =	{Kerber, Michael and Wang, Elena Xinyi},
  title =	{{Computing the Bottleneck Distance Between Persistent Homology Transforms}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{62:1--62:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.62},
  URN =		{urn:nbn:de:0030-drops-258693},
  doi =		{10.4230/LIPIcs.SoCG.2026.62},
  annote =	{Keywords: Kinetic data structure, bottleneck distance, persistent homology transform, vineyards}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.90
Better Sampling Bounds for Restricted Delaunay Triangulations and a Star-Shaped Property for Restricted Voronoi Cells

Authors: Jonathan Richard Shewchuk

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
The restricted Delaunay triangulation of a closed surface Σ and a finite point set V ⊂ Σ is a subcomplex of the Delaunay tetrahedralization of V whose triangles approximate Σ. It is well known that if V is a sufficiently dense sample of a smooth Σ, then the union of the restricted Delaunay triangles is homeomorphic to Σ. We show that an ε-sample with ε ≤ 0.3245 suffices. By comparison, Dey proves it for a 0.18-sample; our improved sampling bound reduces the number of sample points required by a factor of 3.25. More importantly, we improve a related sampling bound of Cheng et al. for Delaunay surface meshing, reducing the number of sample points required by a factor of 21. The first step of our homeomorphism proof is particularly interesting: we show that for a 0.44-sample, the restricted Voronoi cell of each site v ∈ V is homeomorphic to a disk, and the orthogonal projection of the cell onto T_vΣ (the plane tangent to Σ at v) is star-shaped.
Cite as

Jonathan Richard Shewchuk. Better Sampling Bounds for Restricted Delaunay Triangulations and a Star-Shaped Property for Restricted Voronoi Cells. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 90:1-90:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{shewchuk:LIPIcs.SoCG.2026.90,
  author =	{Shewchuk, Jonathan Richard},
  title =	{{Better Sampling Bounds for Restricted Delaunay Triangulations and a Star-Shaped Property for Restricted Voronoi Cells}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{90:1--90:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.90},
  URN =		{urn:nbn:de:0030-drops-258961},
  doi =		{10.4230/LIPIcs.SoCG.2026.90},
  annote =	{Keywords: Restricted Delaunay triangulation, restricted Voronoi diagram, surface sampling, surface mesh generation, surface reconstruction, \epsilon-sample, homeomorphism}
}
Document
DOI: 10.4230/LIPIcs.GD.2025.5
Constrained Flips in Plane Spanning Trees

Authors: Oswin Aichholzer, Joseph Dorfer, and Birgit Vogtenhuber

Published in: LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)

Abstract
A flip in a plane spanning tree T is the operation of removing one edge from T and adding another edge such that the resulting structure is again a plane spanning tree. For trees on a set of points in convex position we study two classic types of constrained flips: (1) Compatible flips are flips in which the removed and inserted edge do not cross each other. We relevantly improve the previous upper bound of 2n-O(√n) on the diameter of the compatible flip graph to (5n/3)-O(1), by this matching the upper bound for unrestricted flips by Bjerkevik, Kleist, Ueckerdt, and Vogtenhuber [SODA 2025] up to an additive constant of 1. We further show that no shortest compatible flip sequence removes an edge that is already in its target position. Using this so-called happy edge property, we derive a fixed-parameter tractable algorithm to compute the shortest compatible flip sequence between two given trees. (2) Rotations are flips in which the removed and inserted edge share a common vertex. Besides showing that the happy edge property does not hold for rotations, we improve the previous upper bound of 2n-O(1) for the diameter of the rotation graph to (7n/4)-O(1).
Cite as

Oswin Aichholzer, Joseph Dorfer, and Birgit Vogtenhuber. Constrained Flips in Plane Spanning Trees. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 5:1-5:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{aichholzer_et_al:LIPIcs.GD.2025.5,
  author =	{Aichholzer, Oswin and Dorfer, Joseph and Vogtenhuber, Birgit},
  title =	{{Constrained Flips in Plane Spanning Trees}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{5:1--5:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-403-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{357},
  editor =	{Dujmovi\'{c}, Vida and Montecchiani, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.5},
  URN =		{urn:nbn:de:0030-drops-249913},
  doi =		{10.4230/LIPIcs.GD.2025.5},
  annote =	{Keywords: Non-crossing spanning trees, Flip Graphs, Diameter, Complexity, Happy edges}
}
Document
Poster Abstract
DOI: 10.4230/LIPIcs.GD.2025.47
Reconfigurations of Plane Caterpillars and Paths (Poster Abstract)

Authors: Todor Antić, Guillermo Gamboa Quintero, and Jelena Glišić

Published in: LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)

Abstract
Let S be a point set in the plane, and let 𝒫(S) and 𝒞(S) be the sets of all plane spanning paths and caterpillars on S. We study reconfiguration operations on 𝒫(S) and 𝒞(S). In particular, we prove that all of the commonly studied reconfigurations on plane spanning trees still yield connected reconfiguration graphs for caterpillars when S is in convex position. If S is in general position, we show that the rotation, compatible flip and flip graphs of 𝒞(S) are connected while the slide graph is sometimes disconnected, but always has a component of size 1/4(3ⁿ-1). We then study sizes of connected components in reconfiguration graphs of plane spanning paths. In this direction, we show that no component of size at most 7 can exist in the flip graph on 𝒫(S).
Cite as

Todor Antić, Guillermo Gamboa Quintero, and Jelena Glišić. Reconfigurations of Plane Caterpillars and Paths (Poster Abstract). In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 47:1-47:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{antic_et_al:LIPIcs.GD.2025.47,
  author =	{Anti\'{c}, Todor and Gamboa Quintero, Guillermo and Gli\v{s}i\'{c}, Jelena},
  title =	{{Reconfigurations of Plane Caterpillars and Paths}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{47:1--47:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-403-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{357},
  editor =	{Dujmovi\'{c}, Vida and Montecchiani, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.47},
  URN =		{urn:nbn:de:0030-drops-250337},
  doi =		{10.4230/LIPIcs.GD.2025.47},
  annote =	{Keywords: reconfiguration graph, caterpillar, path, geometric graph}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.8
Rapid Mixing of the Flip Chain over Non-Crossing Spanning Trees

Authors: Konrad Anand, Weiming Feng, Graham Freifeld, Heng Guo, Mark Jerrum, and Jiaheng Wang

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
We show that the flip chain for non-crossing spanning trees of n+1 points in convex position mixes in time O(n⁸log n). We use connections between Fuss-Catalan structures to construct a comparison argument with a chain similar to Wilson’s lattice path chain (Wilson 2004).
Cite as

Konrad Anand, Weiming Feng, Graham Freifeld, Heng Guo, Mark Jerrum, and Jiaheng Wang. Rapid Mixing of the Flip Chain over Non-Crossing Spanning Trees. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 8:1-8:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{anand_et_al:LIPIcs.SoCG.2025.8,
  author =	{Anand, Konrad and Feng, Weiming and Freifeld, Graham and Guo, Heng and Jerrum, Mark and Wang, Jiaheng},
  title =	{{Rapid Mixing of the Flip Chain over Non-Crossing Spanning Trees}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{8:1--8:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.8},
  URN =		{urn:nbn:de:0030-drops-231607},
  doi =		{10.4230/LIPIcs.SoCG.2025.8},
  annote =	{Keywords: non-crossing spanning trees, Markov chain, mixing time}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.11
When Alpha-Complexes Collapse onto Codimension-1 Submanifolds

Authors: Dominique Attali, Mattéo Clémot, Bianca B. Dornelas, and André Lieutier

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
Given a finite set of points P sampling an unknown smooth surface ℳ ⊆ ℝ³, our goal is to triangulate ℳ based solely on P. Assuming ℳ is a smooth orientable submanifold of codimension 1 in ℝ^d, we introduce a simple algorithm, Naive Squash, which simplifies the α-complex of P by repeatedly applying a new type of collapse called vertical relative to ℳ. Naive Squash also has a practical version that does not require knowledge of ℳ. We establish conditions under which both the naive and practical Squash algorithms output a triangulation of ℳ. We provide a bound on the angle formed by triangles in the α-complex with ℳ, yielding sampling conditions on P that are competitive with existing literature for smooth surfaces embedded in ℝ³, while offering a more compartmentalized proof. As a by-product, we obtain that the restricted Delaunay complex of P triangulates ℳ when ℳ is a smooth surface in ℝ³ under weaker conditions than existing ones.
Cite as

Dominique Attali, Mattéo Clémot, Bianca B. Dornelas, and André Lieutier. When Alpha-Complexes Collapse onto Codimension-1 Submanifolds. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 11:1-11:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{attali_et_al:LIPIcs.SoCG.2025.11,
  author =	{Attali, Dominique and Cl\'{e}mot, Matt\'{e}o and Dornelas, Bianca B. and Lieutier, Andr\'{e}},
  title =	{{When Alpha-Complexes Collapse onto Codimension-1 Submanifolds}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{11:1--11:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.11},
  URN =		{urn:nbn:de:0030-drops-231630},
  doi =		{10.4230/LIPIcs.SoCG.2025.11},
  annote =	{Keywords: Submanifold reconstruction, triangulation, abstract simplicial complexes, collapses, convexity}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.41
Decomposing Multiparameter Persistence Modules

Authors: Tamal K. Dey, Jan Jendrysiak, and Michael Kerber

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
Dey and Xin (J.Appl.Comput.Top., 2022) describe an algorithm to decompose finitely presented multiparameter persistence modules using a matrix reduction algorithm. Their algorithm only works for modules whose generators and relations are distinctly graded. We extend their approach to work on all finitely presented modules and introduce several improvements that lead to significant speed-ups in practice. Our algorithm is fixed-parameter tractable with respect to the maximal number of relations of the same degree and with further optimisation we obtain an O(n³) time algorithm for interval-decomposable modules. In particular, we can decide interval-decomposability in this time. As a by-product to the proofs of correctness we develop a theory of parameter restriction for persistence modules. Our algorithm is implemented as a software library aida, the first to enable the decomposition of large inputs. We show its capabilities via extensive experimental evaluation.
Cite as

Tamal K. Dey, Jan Jendrysiak, and Michael Kerber. Decomposing Multiparameter Persistence Modules. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 41:1-41:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dey_et_al:LIPIcs.SoCG.2025.41,
  author =	{Dey, Tamal K. and Jendrysiak, Jan and Kerber, Michael},
  title =	{{Decomposing Multiparameter Persistence Modules}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{41:1--41:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.41},
  URN =		{urn:nbn:de:0030-drops-231939},
  doi =		{10.4230/LIPIcs.SoCG.2025.41},
  annote =	{Keywords: Topological Data Analysis, Multiparameter Persistence Modules, Persistence, Decomposition}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.58
Tracking the Persistence of Harmonic Chains: Barcode and Stability

Authors: Tao Hou, Salman Parsa, and Bei Wang

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
The persistence barcode is a topological descriptor of data that plays a fundamental role in topological data analysis. Given a filtration of data, the persistence barcode tracks the evolution of its homology groups. In this paper, we introduce a new type of barcode, called the harmonic chain barcode, which tracks the evolution of harmonic chains. In addition, we show that the harmonic chain barcode is stable. Given a filtration of a simplicial complex of size m, we present an algorithm to compute its harmonic chain barcode in O(m³) time. Consequently, the harmonic chain barcode can enrich the family of topological descriptors in applications where a persistence barcode is applicable, such as feature vectorization and machine learning.
Cite as

Tao Hou, Salman Parsa, and Bei Wang. Tracking the Persistence of Harmonic Chains: Barcode and Stability. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 58:1-58:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hou_et_al:LIPIcs.SoCG.2025.58,
  author =	{Hou, Tao and Parsa, Salman and Wang, Bei},
  title =	{{Tracking the Persistence of Harmonic Chains: Barcode and Stability}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{58:1--58:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.58},
  URN =		{urn:nbn:de:0030-drops-232100},
  doi =		{10.4230/LIPIcs.SoCG.2025.58},
  annote =	{Keywords: Persistent homology, harmonic chains, topological data analysis}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2022.9
Tighter Bounds for Reconstruction from ε-Samples

Authors: Håvard Bakke Bjerkevik

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

Abstract
We show that reconstructing a curve in ℝ^d for d ≥ 2 from a 0.66-sample is always possible using an algorithm similar to the classical NN-Crust algorithm. Previously, this was only known to be possible for 0.47-samples in ℝ² and 1/3-samples in ℝ^d for d ≥ 3. In addition, we show that there is not always a unique way to reconstruct a curve from a 0.72-sample; this was previously only known for 1-samples. We also extend this non-uniqueness result to hypersurfaces in all higher dimensions.
Cite as

Håvard Bakke Bjerkevik. Tighter Bounds for Reconstruction from ε-Samples. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bakkebjerkevik:LIPIcs.SoCG.2022.9,
  author =	{Bakke Bjerkevik, H\r{a}vard},
  title =	{{Tighter Bounds for Reconstruction from \epsilon-Samples}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{9:1--9:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.9},
  URN =		{urn:nbn:de:0030-drops-160170},
  doi =		{10.4230/LIPIcs.SoCG.2022.9},
  annote =	{Keywords: Curve reconstruction, surface reconstruction, \epsilon-sampling}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2022.14
Quasi-Universality of Reeb Graph Distances

Authors: Ulrich Bauer, Håvard Bakke Bjerkevik, and Benedikt Fluhr

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

Abstract
We establish bi-Lipschitz bounds certifying quasi-universality (universality up to a constant factor) for various distances between Reeb graphs: the interleaving distance, the functional distortion distance, and the functional contortion distance. The definition of the latter distance is a novel contribution, and for the special case of contour trees we also prove strict universality of this distance. Furthermore, we prove that for the special case of merge trees the functional contortion distance coincides with the interleaving distance, yielding universality of all four distances in this case.
Cite as

Ulrich Bauer, Håvard Bakke Bjerkevik, and Benedikt Fluhr. Quasi-Universality of Reeb Graph Distances. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 14:1-14:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bauer_et_al:LIPIcs.SoCG.2022.14,
  author =	{Bauer, Ulrich and Bjerkevik, H\r{a}vard Bakke and Fluhr, Benedikt},
  title =	{{Quasi-Universality of Reeb Graph Distances}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{14:1--14:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.14},
  URN =		{urn:nbn:de:0030-drops-160221},
  doi =		{10.4230/LIPIcs.SoCG.2022.14},
  annote =	{Keywords: Reeb graphs, contour trees, merge trees, distances, universality, interleaving distance, functional distortion distance, functional contortion distance}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2018.13
Computational Complexity of the Interleaving Distance

Authors: Håvard Bakke Bjerkevik and Magnus Bakke Botnan

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

Abstract
The interleaving distance is arguably the most prominent distance measure in topological data analysis. In this paper, we provide bounds on the computational complexity of determining the interleaving distance in several settings. We show that the interleaving distance is NP-hard to compute for persistence modules valued in the category of vector spaces. In the specific setting of multidimensional persistent homology we show that the problem is at least as hard as a matrix invertibility problem. Furthermore, this allows us to conclude that the interleaving distance of interval decomposable modules depends on the characteristic of the field. Persistence modules valued in the category of sets are also studied. As a corollary, we obtain that the isomorphism problem for Reeb graphs is graph isomorphism complete.
Cite as

Håvard Bakke Bjerkevik and Magnus Bakke Botnan. Computational Complexity of the Interleaving Distance. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 13:1-13:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bjerkevik_et_al:LIPIcs.SoCG.2018.13,
  author =	{Bjerkevik, H\r{a}vard Bakke and Botnan, Magnus Bakke},
  title =	{{Computational Complexity of the Interleaving Distance}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{13:1--13:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.13},
  URN =		{urn:nbn:de:0030-drops-87268},
  doi =		{10.4230/LIPIcs.SoCG.2018.13},
  annote =	{Keywords: Persistent Homology, Interleavings, NP-hard}
}
  • Refine by Type
  • 14 Document/PDF
  • 11 Document/HTML

  • Refine by Publication Year
  • 5 2026
  • 6 2025
  • 2 2022
  • 1 2018

  • Refine by Author
  • 3 Bjerkevik, Håvard Bakke
  • 2 Dorfer, Joseph
  • 2 Jendrysiak, Jan
  • 2 Kerber, Michael
  • 2 Vogtenhuber, Birgit
  • Show More...

  • Refine by Series/Journal
  • 14 LIPIcs

  • Refine by Classification
  • 6 Theory of computation → Computational geometry
  • 4 Mathematics of computing → Algebraic topology
  • 3 Mathematics of computing → Combinatorics
  • 2 Mathematics of computing → Combinatoric problems
  • 2 Mathematics of computing → Discrete mathematics
  • Show More...

  • Refine by Keyword
  • 2 NP-hard
  • 2 Persistence
  • 2 Topological Data Analysis
  • 2 surface reconstruction
  • 1 Complexity
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact