112 Search Results for "Goaoc, Xavier"

Volume

LIPIcs, Volume 224

38th International Symposium on Computational Geometry (SoCG 2022)

SoCG 2022, June 7-10, 2022, Berlin, Germany

Editors: Xavier Goaoc and Michael Kerber

Document
DOI: 10.4230/LIPIcs.SoCG.2026.29
Charting the Diameter Computation Landscape of Intersection Graphs in 3D and Above

Authors: Timothy M. Chan, Hsien-Chih Chang, Jie Gao, Sándor Kisfaludi-Bak, Hung Le, and Da Wei Zheng

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

Abstract
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: 1) 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. 2) 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]. 3) 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]. 4) A truly subquadratic-time algorithm and lower bound for Diameter-2 and Diameter-3 of rectangular boxes (of arbitrary dimension and sizes), respectively.
Cite as

Timothy M. Chan, 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 (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 29:1-29:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chan_et_al:LIPIcs.SoCG.2026.29,
  author =	{Chan, Timothy M. and Chang, Hsien-Chih and Gao, Jie and Kisfaludi-Bak, S\'{a}ndor and Le, Hung and Zheng, Da Wei},
  title =	{{Charting the Diameter Computation Landscape of Intersection Graphs in 3D and Above}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{29:1--29: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.29},
  URN =		{urn:nbn:de:0030-drops-258357},
  doi =		{10.4230/LIPIcs.SoCG.2026.29},
  annote =	{Keywords: Graph Diameter, Geometric Intersection Graphs, Unit Ball Graphs}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.32
Tensor Computation of Euler Characteristic Functions and Transforms

Authors: Jessi Cisewski-Kehe, Brittany Terese Fasy, Alexander McCleary, and Eli Quist

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

Abstract
The weighted Euler characteristic transform (WECT) and Euler characteristic function (ECF) have proven to be useful tools in a variety of applications. However, current methods for computing these functions are either not optimized for GPU computation or do not scale to higher-dimensional settings. In this work, we present a tensor-based framework for computing such topological descriptors which is highly optimized for GPU architectures and works in full generality across simplicial and cubical complexes of arbitrary dimension. Experimentally, the framework demonstrates significant speedups over existing methods when computing the WECT and ECF across a variety of two- and three-dimensional datasets. Computation of these transforms is implemented in a publicly available Python package called pyECT.
Cite as

Jessi Cisewski-Kehe, Brittany Terese Fasy, Alexander McCleary, and Eli Quist. Tensor Computation of Euler Characteristic Functions and Transforms. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 32:1-32:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{cisewskikehe_et_al:LIPIcs.SoCG.2026.32,
  author =	{Cisewski-Kehe, Jessi and Fasy, Brittany Terese and McCleary, Alexander and Quist, Eli},
  title =	{{Tensor Computation of Euler Characteristic Functions and Transforms}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{32:1--32:17},
  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.32},
  URN =		{urn:nbn:de:0030-drops-258380},
  doi =		{10.4230/LIPIcs.SoCG.2026.32},
  annote =	{Keywords: Topological data analysis, weighted Euler characteristic transform, Euler characteristic function, tensor computation, GPU computation}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.33
Near-Optimal Bounds for Parameterized Euclidean k-Means

Authors: Vincent Cohen-Addad, Karthik C. S., David Saulpic, and Chris Schwiegelshohn

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

Abstract
The k-means problem is a classic objective for modeling clustering in a metric space. Given a set of points in a metric space, the goal is to find k representative points so as to minimize the sum of the squared distances from each point to its closest representative. In this work, we study the approximability of k-means in Euclidean spaces parameterized by the number of clusters, k. In seminal works, de la Vega, Karpinski, Kenyon, and Rabani [STOC'03] and Kumar, Sabharwal, and Sen [JACM'10] showed how to obtain a (1+ε)-approximation for high-dimensional Euclidean k-means in time 2^{(k/ε)^O(1)} ⋅ dn^O(1). In this work, we introduce a new fine-grained hypothesis called Exponential Time for Expanders Hypothesis (XXH) which roughly asserts that there are no non-trivial exponential time approximation algorithms for the vertex cover problem on near perfect vertex expanders. Assuming XXH, we close the above long line of work on approximating Euclidean k-means by showing that there is no 2^{(k/ε)^{1-o(1)}} ⋅ n^O(1) time algorithm achieving a (1+ε)-approximation for k-means in Euclidean space. This lower bound is tight as it matches the algorithm given by Feldman, Monemizadeh, and Sohler [SoCG'07] whose runtime is 2^O(k/ε) + O(ndk). Furthermore, assuming XXH, we show that the seminal O(n^{kd+1}) runtime exact algorithm of Inaba, Katoh, and Imai [SoCG'94] for k-means is optimal for small values of k.
Cite as

Vincent Cohen-Addad, Karthik C. S., David Saulpic, and Chris Schwiegelshohn. Near-Optimal Bounds for Parameterized Euclidean k-Means. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 33:1-33:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{cohenaddad_et_al:LIPIcs.SoCG.2026.33,
  author =	{Cohen-Addad, Vincent and C. S., Karthik and Saulpic, David and Schwiegelshohn, Chris},
  title =	{{Near-Optimal Bounds for Parameterized Euclidean k-Means}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{33:1--33:17},
  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.33},
  URN =		{urn:nbn:de:0030-drops-258391},
  doi =		{10.4230/LIPIcs.SoCG.2026.33},
  annote =	{Keywords: k-means clustering, Euclidean space, Fine-Grained Complexity}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.35
On Computing the (Exact) Fréchet Distance with a Frog

Authors: Jacobus Conradi, Ivor van der Hoog, and Eva Rotenberg

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

Abstract
The continuous Fréchet distance 𝒟_F(π,σ) between two polygonal curves π and σ is classically computed by exploring the free space diagram over the two curves. [SoCG'25] recently proposed a radically different approach: they approximate 𝒟_F(π,σ) by computing paths in a discrete graph that models a joint traversal of π and σ, recursively bisecting edges until the discrete distance converges to the continuous one. They implement their "frog-based" technique, and claim that it yields substantial practical speedups compared to the state-of-the-art implementations. In this paper, we revisit this technique. We observe that, in its current form, it has three limitations: (i) it does not use exact arithmetic, (ii) its recursive bisection introduces the required monotonicity events to realise the Fréchet distance only in the limit, and (iii) it applies a heuristic simplification technique which is overly conservative. Motivated by theoretical interest, we develop new techniques that guarantee exactness, polynomial-time convergence and near-optimal lossless simplifications. We provide an open-source C++ implementation of our variant. Our primary contribution is an extensive empirical evaluation on a broad, publically available, suite of real-world and synthetic data sets. Among the frog-based variants, exact computation indeed introduces overhead and increases median runtime. Yet, our new approach is often faster in the worst case, worst ten percent, or even the average runtime due to its worst-case convergence guarantees. More surprisingly, the implementation of [SoCG'19] dominates all frog-based implementations in performance - this finding contrasts previously published claims. These results provide a much-needed nuanced perspective on the capabilities and limitations of frog-based techniques: we showcase its theoretical appeal, but highlight its limited practical feasibility.
Cite as

Jacobus Conradi, Ivor van der Hoog, and Eva Rotenberg. On Computing the (Exact) Fréchet Distance with a Frog. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 35:1-35:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{conradi_et_al:LIPIcs.SoCG.2026.35,
  author =	{Conradi, Jacobus and van der Hoog, Ivor and Rotenberg, Eva},
  title =	{{On Computing the (Exact) Fr\'{e}chet Distance with a Frog}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{35:1--35:20},
  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.35},
  URN =		{urn:nbn:de:0030-drops-258414},
  doi =		{10.4230/LIPIcs.SoCG.2026.35},
  annote =	{Keywords: Algorithms engineering, Fr\'{e}chet distance}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.36
Upward Book Embeddings of Partitioned Digraphs

Authors: Giordano Da Lozzo, Fabrizio Frati, and Ignaz Rutter

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

Abstract
In 1999, Heath, Pemmaraju, and Trenk [SIAM J. Comput. 28(4), 1999] extended the classic notion of book embeddings to digraphs, introducing the concept of upward book embeddings, in which the vertices must appear along the spine in a topological order and the edges are partitioned into pages, so that no two edges in the same page cross. For a partitioned digraph G = (V, ⋃^k_{i=1} E_i), that is, a digraph whose edge set is partitioned into k subsets, an upward book embedding is required to assign edges to pages as prescribed by the given partition. In a companion paper, Heath and Pemmaraju [SIAM J. Comput. 28(5), 1999] proved that the problem of testing the existence of an upward book embedding of a partitioned digraph is linear-time solvable for k = 1 and recently Akitaya, Demaine, Hesterberg, and Liu [GD, 2017] have shown the problem NP-complete for k ≥ 3. In this paper, we study upward book embeddings of partitioned digraphs and focus on the unsolved case k = 2. Our first main result is a novel characterization of the upward embeddings that support an upward book embedding in two pages. We exploit this characterization in several ways, and obtain a rich picture of the complexity landscape of the problem. First, we show that the problem remains NP-complete when k = 2, thus closing the complexity gap for the problem. Second, we show that, for an n-vertex partitioned digraph with a prescribed planar embedding, the existence of an upward book embedding that respects the given planar embedding can be tested in O(n log³ n) time. Finally, leveraging the SPQ(R)-tree decomposition of biconnected graphs into triconnected components, we present a cubic-time testing algorithm for biconnected directed partial 2-trees.
Cite as

Giordano Da Lozzo, Fabrizio Frati, and Ignaz Rutter. Upward Book Embeddings of Partitioned Digraphs. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 36:1-36:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{dalozzo_et_al:LIPIcs.SoCG.2026.36,
  author =	{Da Lozzo, Giordano and Frati, Fabrizio and Rutter, Ignaz},
  title =	{{Upward Book Embeddings of Partitioned Digraphs}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{36:1--36: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.36},
  URN =		{urn:nbn:de:0030-drops-258424},
  doi =		{10.4230/LIPIcs.SoCG.2026.36},
  annote =	{Keywords: upward book embeddings, partitioned digraphs, SPQ-trees, 2-trees}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.43
Unlabeled Multi-Robot Motion Planning with Improved Separation Trade-Offs

Authors: Tsuri Farhana, Omrit Filtser, and Shalev Goldshtein

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

Abstract
We study unlabeled multi-robot motion planning for unit-disk robots in a polygonal environment. Although the problem is hard in general, polynomial-time solutions exist under appropriate separation assumptions on start and target positions. Solovey et al. (RSS'15) provide a near-optimal solution assuming that start/target positions must have pairwise distance at least 4, and at least √5≈2.236 from obstacles. This raises the question of whether polynomial-time algorithms can be obtained in even more densely packed environments. In this paper we present a generalized algorithm that achieve different trade-offs on the robots-separation and obstacles-separation bounds, all significantly improving upon the state of the art. Specifically, we obtain polynomial-time constant-approximation algorithms to minimize the total path length when (i) the robots-separation is 2 2/3 and the obstacles-separation is 1 2/3, or (ii) the robots-separation is ≈3.291 and the obstacles-separation ≈1.354. Additionally, we introduce a different strategy yielding a polynomial-time solution when the robots-separation is only 2, and the obstacles-separation is 3. Finally, we show that without any robots-separation assumption, obstacles-separation of at least 1.5 may be necessary for a solution to exist.
Cite as

Tsuri Farhana, Omrit Filtser, and Shalev Goldshtein. Unlabeled Multi-Robot Motion Planning with Improved Separation Trade-Offs. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 43:1-43:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{farhana_et_al:LIPIcs.SoCG.2026.43,
  author =	{Farhana, Tsuri and Filtser, Omrit and Goldshtein, Shalev},
  title =	{{Unlabeled Multi-Robot Motion Planning with Improved Separation Trade-Offs}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{43:1--43: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.43},
  URN =		{urn:nbn:de:0030-drops-258495},
  doi =		{10.4230/LIPIcs.SoCG.2026.43},
  annote =	{Keywords: multi-robot motion planning}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.53
Constructing Doppelgängers of Greedy Geometric Spanners in Practice

Authors: Anirban Ghosh

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

Abstract
Greedy geometric spanners are considered to be the gold standard for their near-optimal guarantees in terms of sparsity and total weight. However, their inefficient construction poses significant challenges for large-scale geometric networks, especially for low values of stretch factors (< 2). We present Θ-Greedy, a simple and practical parallel algorithm engineered for constructing doppelgängers of greedy geometric spanners that empirically resemble the greedy spanners in key structural and performance metrics, including average degree, degree, and lightness. Unlike approximate greedy spanners, doppelgängers of greedy spanners are almost indistinguishable from the actual greedy spanners in practice. In our experiments, Θ-Greedy consistently produced greedy spanner doppelgängers across a broad range of synthetic and real-world datasets, offering the first practical alternative to the computationally intensive greedy spanners. Θ-Greedy can construct a 1.1-spanner on a 128K-element uniformly distributed point set in well under 5 minutes. In contrast, Bucketing, the most practical greedy spanner algorithm, takes around 3 hours. For million-sized point sets, Θ-Greedy can run to completion in a few hours, making it much faster than Bucketing, which takes days to finish. In extensive experiments on synthetic and real-world datasets, Θ-Greedy delivered speedups of up to 147x over Bucketing while preserving greedy-like sparsity and weight. For broader uses of the algorithm and reproducibility, we share our engineered C++ code.
Cite as

Anirban Ghosh. Constructing Doppelgängers of Greedy Geometric Spanners in Practice. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 53:1-53:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ghosh:LIPIcs.SoCG.2026.53,
  author =	{Ghosh, Anirban},
  title =	{{Constructing Doppelg\"{a}ngers of Greedy Geometric Spanners in Practice}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{53:1--53:21},
  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.53},
  URN =		{urn:nbn:de:0030-drops-258599},
  doi =		{10.4230/LIPIcs.SoCG.2026.53},
  annote =	{Keywords: geometric graph, geometric spanners, greedy spanners, algorithm engineering}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.85
ETH-Tight Complexity of Optimal Morse Matching on Bounded-Treewidth Complexes

Authors: Geevarghese Philip and Erlend Raa Vågset

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

Abstract
The Optimal Morse Matching (OMM) problem asks for a discrete gradient vector field on a simplicial complex that minimizes the number of critical simplices. It is NP-hard and has been studied extensively in heuristic, approximation, and parameterized complexity settings. Parameterized by treewidth k, OMM has long been known to be solvable on triangulations of 3-manifolds in 2^O(k²) n^O(1) time and in FPT time for triangulations of arbitrary manifolds, but the exact dependence on k has remained an open question. We resolve this by giving a new 2^O(k log k) n-time algorithm for any finite regular CW complex, and show that no 2^o(k log k) n^O(1)-time algorithm exists unless the Exponential Time Hypothesis (ETH) fails.
Cite as

Geevarghese Philip and Erlend Raa Vågset. ETH-Tight Complexity of Optimal Morse Matching on Bounded-Treewidth Complexes. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 85:1-85:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{philip_et_al:LIPIcs.SoCG.2026.85,
  author =	{Philip, Geevarghese and V\r{a}gset, Erlend Raa},
  title =	{{ETH-Tight Complexity of Optimal Morse Matching on Bounded-Treewidth Complexes}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{85:1--85:19},
  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.85},
  URN =		{urn:nbn:de:0030-drops-258926},
  doi =		{10.4230/LIPIcs.SoCG.2026.85},
  annote =	{Keywords: Discrete Morse Theory, Simplicial Complexes, Optimal Morse Matching, Treewidth, Parameterized Algorithms, Computational Topology, Dynamic Programming, Exponential Time Hypothesis, Topological Data Analysis}
}
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.SoCG.2026.9
Intersection Patterns of Set Systems on Manifolds with Slowly Growing Homological Shatter Functions

Authors: Sergey Avvakumov, Marguerite Bin, and Xavier Goaoc

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

Abstract
A theorem of Matoušek asserts that for any k ≥ 2, any set system whose shatter function is o(n^k) enjoys a fractional Helly theorem of order k: in the k-wise intersection hypergraph, positive density implies a linear-size clique. Kalai and Meshulam conjectured a generalization of that phenomenon to homological shatter functions. It was verified for set systems with bounded homological shatter functions and whose ground set has a forbidden homological minor (which includes ℝ^d by a homological analogue of the van Kampen-Flores theorem). We present two contributions to this line of research: - We study homological minors in certain manifolds (possibly with boundary), for which we prove analogues of the van Kampen-Flores theorem and of the Hanani-Tutte theorem. - We introduce graded analogues of the Radon and Helly numbers of set systems and relate their growth rate to the original parameters. This allows to extend the verification of the Kalai-Meshulam conjecture to sufficiently slowly growing homological shatter functions.
Cite as

Sergey Avvakumov, Marguerite Bin, and Xavier Goaoc. Intersection Patterns of Set Systems on Manifolds with Slowly Growing Homological Shatter Functions. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 9:1-9:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{avvakumov_et_al:LIPIcs.SoCG.2026.9,
  author =	{Avvakumov, Sergey and Bin, Marguerite and Goaoc, Xavier},
  title =	{{Intersection Patterns of Set Systems on Manifolds with Slowly Growing Homological Shatter Functions}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{9:1--9: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.9},
  URN =		{urn:nbn:de:0030-drops-258152},
  doi =		{10.4230/LIPIcs.SoCG.2026.9},
  annote =	{Keywords: Fractional Helly theorem, homological minor, combinatorial convexity}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.10
Fast Free Resolutions of Bifiltered Chain Complexes

Authors: Ulrich Bauer, Tamal K. Dey, Michael Kerber, Florian Russold, and Matthias Söls

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

Abstract
In a k-critical bifiltration, every simplex enters along a staircase with at most k steps. Examples with k > 1 include degree-Rips bifiltrations and models of the multicover bifiltration. We consider the problem of converting a k-critical bifiltration into a 1-critical (i.e. free) chain complex with equivalent homology. This is known as computing a free resolution of the underlying chain complex and is a first step toward post-processing such bifiltrations. We present two algorithms. The first one computes free resolutions corresponding to path graphs and assembles them to a chain complex by computing additional maps. The simple combinatorial structure of path graphs leads to good performance in practice, as demonstrated by extensive experiments. However, its worst-case bound is quadratic in the input size because long paths might yield dense boundary matrices in the output. Our second algorithm replaces the simplex-wise path graphs with ones that maintain short paths which leads to almost linear runtime and output size. We demonstrate that pre-computing a free resolution speeds up the task of computing a minimal presentation of the homology of a k-critical bifiltration in a fixed dimension. Furthermore, our findings show that a chain complex that is minimal in terms of generators can be asymptotically larger than the non-minimal output complex of our second algorithm in terms of description size.
Cite as

Ulrich Bauer, Tamal K. Dey, Michael Kerber, Florian Russold, and Matthias Söls. Fast Free Resolutions of Bifiltered Chain Complexes. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 10:1-10:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bauer_et_al:LIPIcs.SoCG.2026.10,
  author =	{Bauer, Ulrich and Dey, Tamal K. and Kerber, Michael and Russold, Florian and S\"{o}ls, Matthias},
  title =	{{Fast Free Resolutions of Bifiltered Chain Complexes}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{10:1--10:21},
  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.10},
  URN =		{urn:nbn:de:0030-drops-258161},
  doi =		{10.4230/LIPIcs.SoCG.2026.10},
  annote =	{Keywords: Topological Data Analysis, Multi-Parameter Persistence, Multi-Critical Bifiltrations}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.30
Incidences Between Curves and Points on the Grid

Authors: Esther Ezra and Micha Sharir

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
We derive an improved upper bound for the number of incidences between the n vertices of a uniform grid and m convex or concave curves, each pair of which intersect in at most s points, for some integer parameter s ≥ 1. For a square grid, our bound is O(n^{2/3}m^{2/3} + m^{1-1/(3s)} n^{(s+1)/3s} + m + n) . This improves a general bound of O(m n^{1/3}) on the number of incidences with respect to vertices of a grid and convex or concave curves. For a rectangular grid, which fits inside a 1×K rectangle, for some integer K > 1 (which generally may depend on n), the bound also depends on how large K is. The precise result is stated in Theorem 2, but, roughly, we get the same bound as above when K is not too large. Our analysis competes with a celebrated result of Bombieri and Pila [E. Bombieri and J. Pila, 1989], which gives (usually) a sharper bound if we assume that the input curves are algebraic of constant degree and the input points are vertices of the square grid. However, the analysis in [E. Bombieri and J. Pila, 1989] strongly relies on these assumptions, and cannot be extended to handle the more general setup considered here. As a main application, of independent interest, we present a variant of our technique for semi-algebraic range reporting on sets of points of "bounded spread" in the plane.
Cite as

Esther Ezra and Micha Sharir. Incidences Between Curves and Points on the Grid. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 30:1-30:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ezra_et_al:LIPIcs.ISAAC.2025.30,
  author =	{Ezra, Esther and Sharir, Micha},
  title =	{{Incidences Between Curves and Points on the Grid}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{30:1--30:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.30},
  URN =		{urn:nbn:de:0030-drops-249387},
  doi =		{10.4230/LIPIcs.ISAAC.2025.30},
  annote =	{Keywords: Geometric incidences, uniform grid, bounded spread, Pick’s theorem, range searching}
}
Document
DOI: 10.4230/LIPIcs.GD.2025.25
Characterizing and Recognizing Twistedness

Authors: Oswin Aichholzer, Alfredo García, Javier Tejel, Birgit Vogtenhuber, and Alexandra Weinberger

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

Abstract
In a simple drawing of a graph, any two edges intersect in at most one point (either a common endpoint or a proper crossing). A simple drawing is generalized twisted if it fulfills certain rather specific constraints on how the edges are drawn. An abstract rotation system of a graph assigns to each vertex a cyclic order of its incident edges. A realizable rotation system is one that admits a simple drawing such that at each vertex, the edges emanate in that cyclic order, and a generalized twisted rotation system can be realized as a generalized twisted drawing. Generalized twisted drawings have initially been introduced to obtain improved bounds on the size of plane substructures in any simple drawing of K_n. They have since gained independent interest due to their surprising properties. However, the definition of generalized twisted drawings is very geometric and drawing-specific. In this paper, we develop characterizations of generalized twisted drawings that enable a purely combinatorial view on these drawings and lead to efficient recognition algorithms. Concretely, we show that for any n ≥ 7, an abstract rotation system of K_n is generalized twisted if and only if all subrotation systems induced by five vertices are generalized twisted. This implies a drawing-independent and concise characterization of generalized twistedness. Besides, the result yields a simple O(n⁵)-time algorithm to decide whether an abstract rotation system is generalized twisted and sheds new light on the structural features of simple drawings. We further develop a characterization via the rotations of a pair of vertices in a drawing, which we then use to derive an O(n²)-time algorithm to decide whether a realizable rotation system is generalized twisted.
Cite as

Oswin Aichholzer, Alfredo García, Javier Tejel, Birgit Vogtenhuber, and Alexandra Weinberger. Characterizing and Recognizing Twistedness. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{aichholzer_et_al:LIPIcs.GD.2025.25,
  author =	{Aichholzer, Oswin and Garc{\'\i}a, Alfredo and Tejel, Javier and Vogtenhuber, Birgit and Weinberger, Alexandra},
  title =	{{Characterizing and Recognizing Twistedness}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{25:1--25:17},
  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.25},
  URN =		{urn:nbn:de:0030-drops-250116},
  doi =		{10.4230/LIPIcs.GD.2025.25},
  annote =	{Keywords: generalized twisted drawings, simple drawings, rotation systems, recognition, combinatorial characterization, efficient algorithms}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.21
A Unified FPT Framework for Crossing Number Problems

Authors: Éric Colin de Verdière and Petr Hliněný

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
The basic (and traditional) crossing number problem is to determine the minimum number of crossings in a topological drawing of an input graph in the plane. We develop a unified framework that smoothly captures many generalized crossing number problems, and that yields fixed-parameter tractable (FPT) algorithms for them not only in the plane but also on surfaces. Our framework takes the following form. We fix a surface S, an integer r, and a map κ from the set of topological drawings of graphs in S to ℤ_+ ∪ {∞}, satisfying some natural monotonicity conditions, but essentially describing the allowed drawings and how we want to count the crossings in them. Then deciding whether an input graph G has an allowed drawing D on S with κ(D) ≤ r can be done in time quadratic in the size of G (and exponential in other parameters). More generally, we may take as input an edge-colored graph, and distinguish crossings by the colors of the involved edges; and we may allow to perform a bounded number of edge removals and vertex splits to G before drawing it. The proof is a reduction to the embeddability of a graph on a two-dimensional simplicial complex. This framework implies, in a unified way, quadratic FPT algorithms for many topological crossing number variants established in the graph drawing community. Some of these variants already had previously published FPT algorithms, mostly relying on Courcelle’s metatheorem, but for many of those, we obtain an algorithm with a better runtime. Moreover, our framework extends, at no cost, to these crossing number variants in any fixed surface.
Cite as

Éric Colin de Verdière and Petr Hliněný. A Unified FPT Framework for Crossing Number Problems. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 21:1-21:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{colindeverdiere_et_al:LIPIcs.ESA.2025.21,
  author =	{Colin de Verdi\`{e}re, \'{E}ric and Hlin\v{e}n\'{y}, Petr},
  title =	{{A Unified FPT Framework for Crossing Number Problems}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{21:1--21:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.21},
  URN =		{urn:nbn:de:0030-drops-244897},
  doi =		{10.4230/LIPIcs.ESA.2025.21},
  annote =	{Keywords: computational geometry, fixed-parameter tractability, graph drawing, graph embedding, crossing number, two-dimensional simplicial complex, surface}
}
  • Refine by Type
  • 111 Document/PDF
  • 22 Document/HTML
  • 1 Volume

  • Refine by Publication Year
  • 11 2026
  • 11 2025
  • 1 2024
  • 77 2022
  • 2 2021
  • Show More...

  • Refine by Author
  • 15 Goaoc, Xavier
  • 6 Patáková, Zuzana
  • 4 Nusser, André
  • 4 Tancer, Martin
  • 3 Aichholzer, Oswin
  • Show More...

  • Refine by Series/Journal
  • 111 LIPIcs

  • Refine by Classification
  • 76 Theory of computation → Computational geometry
  • 13 Theory of computation → Design and analysis of algorithms
  • 11 Mathematics of computing → Algebraic topology
  • 9 Mathematics of computing → Geometric topology
  • 7 Mathematics of computing → Combinatorics
  • Show More...

  • Refine by Keyword
  • 5 persistent homology
  • 3 Computational Geometry
  • 3 Topological Data Analysis
  • 3 computational geometry
  • 2 Dynamic Time Warping
  • 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