388 Search Results for "Hoffmann, Michael"

Volume

LIPIcs, Volume 367

42nd International Symposium on Computational Geometry (SoCG 2026)

SoCG 2026, New Brunswick, NJ, USA, June 2-5, 2026

Editors: Hee-Kap Ahn, Michael Hoffmann, and Amir Nayyeri

Artifact
Dataset
DOI: 10.4230/dblp.rdf.ntriples.2026-08-01
dblp computer science bibliography – Monthly Snapshot RDF/N-Triple Release of August 2026

Authors: dblp Team

Abstract
Cite as

dblp Team. dblp computer science bibliography – Monthly Snapshot RDF/N-Triple Release of August 2026. Schloss Dagstuhl – Leibniz-Zentrum für Informatik

Copy BibTex To Clipboard

@misc{dblp.rdf.ntriples.2026-08-01,
    title     = {{dblp computer science bibliography – Monthly Snapshot RDF/N-Triple Release of August 2026}},
    author    = {dblp Team},
    doi       = {10.4230/dblp.rdf.ntriples.2026-08-01},
    url       = {https://doi.org/10.4230/dblp.rdf.ntriples.2026-08-01},
    month     = {August},
    year      = {2026},
    publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik} 
}
Artifact
Dataset
DOI: 10.4230/dblp.xml.2026-08-01
dblp computer science bibliography – Monthly Snapshot XML Release of August 2026

Authors: dblp Team

Abstract
Cite as

dblp Team. dblp computer science bibliography – Monthly Snapshot XML Release of August 2026. Schloss Dagstuhl – Leibniz-Zentrum für Informatik

Copy BibTex To Clipboard

@misc{dblp.xml.2026-08-01,
    title     = {{dblp computer science bibliography – Monthly Snapshot XML Release of August 2026}},
    author    = {dblp Team},
    doi       = {10.4230/dblp.xml.2026-08-01},
    url       = {https://doi.org/10.4230/dblp.xml.2026-08-01},
    month     = {August},
    year      = {2026},
    publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik} 
}
Artifact
Dataset
DOI: 10.4230/dblp.rdf.ntriples.2026-07-01
dblp computer science bibliography – Monthly Snapshot RDF/N-Triple Release of July 2026

Authors: dblp Team

Abstract
Cite as

dblp Team. dblp computer science bibliography – Monthly Snapshot RDF/N-Triple Release of July 2026. Schloss Dagstuhl – Leibniz-Zentrum für Informatik

Copy BibTex To Clipboard

@misc{dblp.rdf.ntriples.2026-07-01,
    title     = {{dblp computer science bibliography – Monthly Snapshot RDF/N-Triple Release of July 2026}},
    author    = {dblp Team},
    doi       = {10.4230/dblp.rdf.ntriples.2026-07-01},
    url       = {https://doi.org/10.4230/dblp.rdf.ntriples.2026-07-01},
    month     = {July},
    year      = {2026},
    publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik} 
}
Artifact
Dataset
DOI: 10.4230/dblp.xml.2026-07-01
dblp computer science bibliography – Monthly Snapshot XML Release of July 2026

Authors: dblp Team

Abstract
Cite as

dblp Team. dblp computer science bibliography – Monthly Snapshot XML Release of July 2026. Schloss Dagstuhl – Leibniz-Zentrum für Informatik

Copy BibTex To Clipboard

@misc{dblp.xml.2026-07-01,
    title     = {{dblp computer science bibliography – Monthly Snapshot XML Release of July 2026}},
    author    = {dblp Team},
    doi       = {10.4230/dblp.xml.2026-07-01},
    url       = {https://doi.org/10.4230/dblp.xml.2026-07-01},
    month     = {July},
    year      = {2026},
    publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik} 
}
Document
DOI: 10.4230/LIPIcs.SWAT.2026.24
Cutwidth Versus BFS-Width with Applications to Graph Reconstruction from Distance Queries

Authors: Chirag Kaudan and Amir Nayyeri

Published in: LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)

Abstract
Eppstein, Goodrich, and Liu [ESA 2025] introduced a new graph parameter, called BFS-width, and gave polylogarithmic bounds on it for bounded bandwidth graphs. Their bounds naturally imply several applications, e.g. in graph reconstruction via shortest path distance queries, graph drawing, and matrix reordering. We study this parameter for a broader class of graphs, namely bounded cutwidth graphs. We prove a sublinear upper bound on the BFS-width of bounded cutwidth graphs and show that our bounds are asymptotically tight. Our upper bound implies the first deterministic algorithm for reconstructing a bounded cutwidth graph with a subquadratic number of shortest path distance queries.
Cite as

Chirag Kaudan and Amir Nayyeri. Cutwidth Versus BFS-Width with Applications to Graph Reconstruction from Distance Queries. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 24:1-24:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{kaudan_et_al:LIPIcs.SWAT.2026.24,
  author =	{Kaudan, Chirag and Nayyeri, Amir},
  title =	{{Cutwidth Versus BFS-Width with Applications to Graph Reconstruction from Distance Queries}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{24:1--24:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-421-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{370},
  editor =	{Fraigniaud, Pierre},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.24},
  URN =		{urn:nbn:de:0030-drops-260600},
  doi =		{10.4230/LIPIcs.SWAT.2026.24},
  annote =	{Keywords: Graph algorithms, graph theory, cutwidth, pathwidth, BFS-width}
}
Artifact
Dataset
DOI: 10.4230/dblp.rdf.ntriples.2026-06-01
dblp computer science bibliography – Monthly Snapshot RDF/N-Triple Release of June 2026

Authors: dblp Team

Abstract
Cite as

dblp Team. dblp computer science bibliography – Monthly Snapshot RDF/N-Triple Release of June 2026. Schloss Dagstuhl – Leibniz-Zentrum für Informatik

Copy BibTex To Clipboard

@misc{dblp.rdf.ntriples.2026-06-01,
    title     = {{dblp computer science bibliography – Monthly Snapshot RDF/N-Triple Release of June 2026}},
    author    = {dblp Team},
    doi       = {10.4230/dblp.rdf.ntriples.2026-06-01},
    url       = {https://doi.org/10.4230/dblp.rdf.ntriples.2026-06-01},
    month     = {June},
    year      = {2026},
    publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik} 
}
Artifact
Dataset
DOI: 10.4230/dblp.xml.2026-06-01
dblp computer science bibliography – Monthly Snapshot XML Release of June 2026

Authors: dblp Team

Abstract
Cite as

dblp Team. dblp computer science bibliography – Monthly Snapshot XML Release of June 2026. Schloss Dagstuhl – Leibniz-Zentrum für Informatik

Copy BibTex To Clipboard

@misc{dblp.xml.2026-06-01,
    title     = {{dblp computer science bibliography – Monthly Snapshot XML Release of June 2026}},
    author    = {dblp Team},
    doi       = {10.4230/dblp.xml.2026-06-01},
    url       = {https://doi.org/10.4230/dblp.xml.2026-06-01},
    month     = {June},
    year      = {2026},
    publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik} 
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.1
Covering and Partitioning Complex Objects with Small Pieces

Authors: Anders Aamand, Mikkel Abrahamsen, Reilly Browne, Mayank Goswami, Prahlad Narasimhan Kasthurirangan, Linda Kleist, Joseph S. B. Mitchell, Valentin Polishchuk, and Jack Stade

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

Abstract
We study the problems of covering or partitioning a polygon P (possibly with holes) using a minimum number of small pieces, where a small piece is a connected sub-polygon contained in an axis-aligned unit square. For covering, we seek to write P as a union of small pieces, and in partitioning, we furthermore require the pieces to be pairwise interior-disjoint. We show that these problems are in fact equivalent: Optimum covers and partitions have the same number of pieces. For covering, a natural local search algorithm repeatedly attempts to replace k pieces from a candidate cover with k-1 pieces. In two dimensions and for sufficiently large k, we show that when no such swap is possible, the cover is a 1+ O(1/√k) approximation, hence obtaining the first PTAS for the problem. Prior to our work, the only known algorithm was a 13-approximation that only works for polygons without holes [Abrahamsen and Rasmussen, SODA 2025]. In contrast, in the three dimensional version of the problem, for a polyhedron P of complexity n, we show that it is NP-hard to approximate an optimal cover or partition to within a factor that is logarithmic in n, even if P is simple, i.e., has genus 0 and no holes.
Cite as

Anders Aamand, Mikkel Abrahamsen, Reilly Browne, Mayank Goswami, Prahlad Narasimhan Kasthurirangan, Linda Kleist, Joseph S. B. Mitchell, Valentin Polishchuk, and Jack Stade. Covering and Partitioning Complex Objects with Small Pieces. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 1:1-1:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{aamand_et_al:LIPIcs.SoCG.2026.1,
  author =	{Aamand, Anders and Abrahamsen, Mikkel and Browne, Reilly and Goswami, Mayank and Kasthurirangan, Prahlad Narasimhan and Kleist, Linda and Mitchell, Joseph S. B. and Polishchuk, Valentin and Stade, Jack},
  title =	{{Covering and Partitioning Complex Objects with Small Pieces}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{1:1--1: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.1},
  URN =		{urn:nbn:de:0030-drops-258077},
  doi =		{10.4230/LIPIcs.SoCG.2026.1},
  annote =	{Keywords: Covering, partitioning, polygon, small piece, PTAS}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.4
Dynamic Nearest-Neighbor Searching Under General Metrics in ℝ³ and Its Applications

Authors: Pankaj K. Agarwal, Matthew J. Katz, and Micha Sharir

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

Abstract
Let K be a compact, centrally-symmetric, strictly-convex region in ℝ³, which is a semi-algebraic set of constant complexity, i.e. the unit ball of a corresponding metric, denoted as ‖⋅‖_K. Let 𝒦 be a set of n homothetic copies of K. This paper contains two main sets of results: (i) For a storage parameter s ∈ [n,n³], 𝒦 can be preprocessed in O^*(s) expected time into a data structure of size O^*(s), so that for a query homothet K₀ of K, an intersection-detection query (determine whether K₀ intersects any member of 𝒦, and if so, report such a member) or a nearest-neighbor query (return the member of 𝒦 whose ‖⋅‖_K-distance from K₀ is smallest) can be answered in O^*(n/s^{1/3}) time; all k homothets of 𝒦 intersecting K₀ can be reported in additional O(k) time. In addition, the data structure supports insertions/deletions in O^*(s/n) amortized expected time per operation. Here the O^*(⋅) notation hides factors of the form n^ε, where ε > 0 is an arbitrarily small constant, and the constant of proportionality depends on ε. (ii) Let 𝒢(𝒦) denote the intersection graph of 𝒦. Using the above data structure, breadth-first or depth-first search on 𝒢(𝒦) can be performed in O^*(n^{3/2}) expected time. Combining this result with the so-called shrink-and-bifurcate technique, the reverse-shortest-path problem in a suitably defined proximity graph of 𝒦 can be solved in O^*(n^{62/39}) expected time. Dijkstra’s shortest-path algorithm, as well as Prim’s MST algorithm, on a ‖⋅‖_K-proximity graph on n points in ℝ³, with edges weighted by ‖⋅‖_K, can also be performed in O^*(n^{3/2}) time.
Cite as

Pankaj K. Agarwal, Matthew J. Katz, and Micha Sharir. Dynamic Nearest-Neighbor Searching Under General Metrics in ℝ³ and Its Applications. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{agarwal_et_al:LIPIcs.SoCG.2026.4,
  author =	{Agarwal, Pankaj K. and Katz, Matthew J. and Sharir, Micha},
  title =	{{Dynamic Nearest-Neighbor Searching Under General Metrics in \mathbb{R}³ and Its Applications}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{4:1--4: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.4},
  URN =		{urn:nbn:de:0030-drops-258102},
  doi =		{10.4230/LIPIcs.SoCG.2026.4},
  annote =	{Keywords: Homothets, Minkowski metric, Shallow cuttings, Nearest-neighbor searching, Intersection and proximity graphs, Reverse-shortest-path problem}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.7
Computing L_∞ Hausdorff Distances Under Translations: The Interplay of Dimensionality, Symmetry and Discreteness

Authors: Sebastian Angrick, Kevin Buchin, Geri Gokaj, and Marvin Künnemann

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

Abstract
To measure the similarity of the shape of point sets, rather than their mere closeness in space, various notions of a Hausdorff distance under translation have been investigated. Specifically, let P and Q denote point sets of n and m points, respectively, in ℝ^d. We consider the task of computing the minimum distance d(P,Q+τ) over an admissible set of translations τ ∈ T, where d(⋅, ⋅) denotes the Hausdorff distance under the L_∞-norm. As variants, we distinguish between continuous (T = ℝ^d) or discrete (T is a given finite set of t translations) as well as directed or undirected (choosing the directed or undirected Hausdorff distance for d(⋅, ⋅)). We seek to apply the paradigm of fine-grained complexity to understand the complexity of these variants, and in particular: How is the running time influenced by the dimension d, the relationship between n and m, and the specific choice of variant? As our main results, we obtain: - The asymmetric definition of the most studied variant, the continuous directed Hausdorff distance, results in an intrinsically asymmetric time complexity: While (Chan, SoCG'23) established a symmetric Õ((nm)^{d/2}) upper bound for all d ≥ 3 and proved it to be conditionally optimal for combinatorial algorithms whenever m ≤ n, we show that this lower bound does not hold for the case n ≪ m, by providing a combinatorial, almost-linear-time algorithm for d = 3 and n = m^{o(1)}. We further prove general, i.e., non-combinatorial, conditional lower bounds for d ≥ 3, in particular: (1) m^{⌊d/2⌋ - o(1)} for small n and (2) n^{d/2 - o(1)} for d = 3 and small m. - We observe that the directed and undirected case is closely related, in particular, all our lower bounds for d ≥ 3 hold for both the directed and undirected variant. A remarkable exception is the case of d = 1 for which we provide a conditional separation. Specifically, in contrast to the undirected variants being solvable in near-linear time (Rote, IPL'91), we show that the directed variants are at least as hard as the additive problem MaxConv LowerBound introduced in (Cygan, Mucha, Wegrzycki and Wlodarczyk, TALG'19). - We show that the discrete variants reduce to a variant of 3SUM for d ≤ 3. This gives a barrier in proving a tight lower bound of these variants under the Orthogonal Vectors Hypothesis (OVH); in contrast, the continuous variants admit a tight conditional lower bound under OVH in d = 2 (Bringmann, Nusser, JoCG'21). These results reveal an intricate interplay of dimensionality, symmetry and discreteness in determining the fine-grained complexity of computing Hausdorff distances under translation.
Cite as

Sebastian Angrick, Kevin Buchin, Geri Gokaj, and Marvin Künnemann. Computing L_∞ Hausdorff Distances Under Translations: The Interplay of Dimensionality, Symmetry and Discreteness. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 7:1-7:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{angrick_et_al:LIPIcs.SoCG.2026.7,
  author =	{Angrick, Sebastian and Buchin, Kevin and Gokaj, Geri and K\"{u}nnemann, Marvin},
  title =	{{Computing L\underline∞ Hausdorff Distances Under Translations: The Interplay of Dimensionality, Symmetry and Discreteness}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{7:1--7: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.7},
  URN =		{urn:nbn:de:0030-drops-258131},
  doi =		{10.4230/LIPIcs.SoCG.2026.7},
  annote =	{Keywords: Hausdorff Distance, Fine-Grained Complexity, Computational Geometry, Translation-Invariant Similarity Measures}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.2
On the Maximum Number of Tangencies Among 1-Intersecting Curves

Authors: Eyal Ackerman and Balázs Keszegh

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

Abstract
According to a conjecture of Pach, there are O(n) tangent pairs among any family of n Jordan arcs in which every pair of arcs has precisely one common point and no three arcs share a common point. This conjecture was proved for two special cases, however, for the general case the currently best upper bound is only O(n^{7/4}). This is also the best known bound on the number of tangencies in the relaxed case where every pair of arcs has at most one common point. We improve the bounds for the latter and former cases to O(n^{5/3}) and O(n^{3/2}), respectively. We also consider a few other variants of these questions, for example, we show that if the arcs are x-monotone, each pair intersects at most once and their left endpoints lie on a common vertical line, then the maximum number of tangencies is Θ(n^{4/3}). Without this last condition the number of tangencies is O(n^{4/3}(log n)^{1/3}), improving a previous bound of Pach and Sharir. Along the way we prove a graph-theoretic theorem which extends a result of Erdős and Simonovits and may be of independent interest.
Cite as

Eyal Ackerman and Balázs Keszegh. On the Maximum Number of Tangencies Among 1-Intersecting Curves. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 2:1-2:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ackerman_et_al:LIPIcs.SoCG.2026.2,
  author =	{Ackerman, Eyal and Keszegh, Bal\'{a}zs},
  title =	{{On the Maximum Number of Tangencies Among 1-Intersecting Curves}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{2:1--2: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.2},
  URN =		{urn:nbn:de:0030-drops-258085},
  doi =		{10.4230/LIPIcs.SoCG.2026.2},
  annote =	{Keywords: tangency graph, forbidden subgraph, extremal graph}
}
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.3
Lower Bounding the Gromov-Hausdorff Distance in Metric Graphs

Authors: Henry Adams, Sushovan Majhi, Fedor Manin, Žiga Virk, and Nicolò Zava

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

Abstract
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.
Cite as

Henry Adams, Sushovan Majhi, Fedor Manin, Žiga Virk, and Nicolò Zava. Lower Bounding the Gromov-Hausdorff Distance in Metric Graphs. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 3:1-3:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{adams_et_al:LIPIcs.SoCG.2026.3,
  author =	{Adams, Henry and Majhi, Sushovan and Manin, Fedor and Virk, \v{Z}iga and Zava, Nicol\`{o}},
  title =	{{Lower Bounding the Gromov-Hausdorff Distance in Metric Graphs}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{3:1--3: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.3},
  URN =		{urn:nbn:de:0030-drops-258099},
  doi =		{10.4230/LIPIcs.SoCG.2026.3},
  annote =	{Keywords: Gromov-Hausdorff distance, distortion, connectedness, Borsuk-Ulam theorem}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.22
Disproving Two Conjectures on the Hamiltonicity of Venn Diagrams

Authors: Sofia Brenner, Linda Kleist, Torsten Mütze, Christian Rieck, and Francesco Verciani

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

Abstract
In 1984, Winkler conjectured that every simple Venn diagram with n curves can be extended to a simple Venn diagram with n+1 curves. This conjecture is equivalent to the statement that the dual graph of any simple Venn diagram has a Hamilton cycle. In this work, we construct counterexamples to Winkler’s conjecture for all n ≥ 6. As part of this proof, we computed all 3.430.404 simple Venn diagrams with n = 6 curves (even their number was not previously known), among which we found 72 counterexamples. We also disprove another conjecture about the Hamiltonicity of the arrangement graph of a Venn diagram. Specifically, while working on Winkler’s conjecture, Pruesse and Ruskey proved that this graph has a Hamilton cycle for every simple Venn diagram with n curves, and conjectured that this also holds for non-simple diagrams. We construct counterexamples to this conjecture for all n ≥ 4.
Cite as

Sofia Brenner, Linda Kleist, Torsten Mütze, Christian Rieck, and Francesco Verciani. Disproving Two Conjectures on the Hamiltonicity of Venn Diagrams. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 22:1-22:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{brenner_et_al:LIPIcs.SoCG.2026.22,
  author =	{Brenner, Sofia and Kleist, Linda and M\"{u}tze, Torsten and Rieck, Christian and Verciani, Francesco},
  title =	{{Disproving Two Conjectures on the Hamiltonicity of Venn Diagrams}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{22:1--22: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.22},
  URN =		{urn:nbn:de:0030-drops-258285},
  doi =		{10.4230/LIPIcs.SoCG.2026.22},
  annote =	{Keywords: Venn diagram, Winkler’s conjecture, Hamilton cycle, perfect matching, hypercube}
}
  • Refine by Type
  • 206 Artifact
  • 181 Document/PDF
  • 160 Document/HTML
  • 1 Volume

  • Refine by Publication Year
  • 133 2026
  • 70 2025
  • 26 2024
  • 29 2023
  • 27 2022
  • Show More...

  • Refine by Author
  • 206 dblp Team
  • 18 Hoffmann, Michael
  • 6 Fekete, Sándor P.
  • 5 Kleist, Linda
  • 5 Rieck, Christian
  • Show More...

  • Refine by Series/Journal
  • 173 LIPIcs
  • 6 OASIcs
  • 1 TGDK
  • 1 DagSemProc

  • Refine by Classification
  • 89 Theory of computation → Computational geometry
  • 17 Theory of computation → Design and analysis of algorithms
  • 12 Mathematics of computing → Algebraic topology
  • 12 Mathematics of computing → Graph theory
  • 11 Mathematics of computing → Graph algorithms
  • Show More...

  • Refine by Keyword
  • 206 bibliography
  • 206 computer science
  • 206 dblp
  • 206 knowledge graph
  • 206 open data
  • 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