149 Search Results for "Buchin, Kevin"

Volume

LIPIcs, Volume 189

37th International Symposium on Computational Geometry (SoCG 2021)

SoCG 2021, June 7-11, 2021, Buffalo, NY, USA (Virtual Conference)

Editors: Kevin Buchin and Éric Colin de Verdière

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.47
A Constant-Factor Approximation for Continuous Dynamic Time Warping in 2D

Authors: Kevin Buchin, Maike Buchin, Jan Erik Swiadek, and Sampson Wong

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract
Continuous Dynamic Time Warping (CDTW) is a robust similarity measure for polygonal curves that has recently found a variety of applications. Despite its practical use, not much is known about the algorithmic complexity of computing it in 2D, especially when one requires either an exact solution or strong approximation guarantees. We fill this gap by introducing a 5-approximation algorithm with running time O(n⁵) under the 1-norm. This is the first constant-factor approximation for 2D CDTW with polynomial running time. We extend our algorithm to all polygonal norms on ℝ², which we subsequently use in order to achieve a (5+ε)-approximation with time complexity O(n⁵/ε^{1/2}) for CDTW in 2D under any fixed norm. The latter result in particular includes the usual Euclidean 2-norm.
Cite as

Kevin Buchin, Maike Buchin, Jan Erik Swiadek, and Sampson Wong. A Constant-Factor Approximation for Continuous Dynamic Time Warping in 2D. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 47:1-47:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{buchin_et_al:LIPIcs.ICALP.2026.47,
  author =	{Buchin, Kevin and Buchin, Maike and Swiadek, Jan Erik and Wong, Sampson},
  title =	{{A Constant-Factor Approximation for Continuous Dynamic Time Warping in 2D}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{47:1--47:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.47},
  URN =		{urn:nbn:de:0030-drops-264365},
  doi =		{10.4230/LIPIcs.ICALP.2026.47},
  annote =	{Keywords: Continuous Dynamic Time Warping, Curve Similarity, Geometric Approximation Algorithm}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2026.10
Robotic Arm Rotation: Standing up Is Harder Than You Think

Authors: Nicolas Bousquet, Frank Connor, Remy El Sabeh, Louis-Roy Langevin, Amer E. Mouawad, Naomi Nishimura, and Agnes Totschnig

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

Abstract
We study motion-planning problems for planar robotic arms that rotate around fixed centers while avoiding collisions. In the SM-RAMP model, each unit-length arm may rotate at most once; the question is whether all arms can be rotated to the vertical position. We resolve an open problem of Bousquet et al. [Bousquet et al., 2026] by proving that SM-RAMP is NP-complete, even in the horizontal-to-vertical setting. Our hardness proof uses a structural analysis of rotation-propagation chains and introduces a combinatorial abstraction of independent interest, the Lighthouse Propagation problem, which we show is itself NP-complete. We then consider the multi-move variant MM-RAMP, where each arm may rotate multiple times among a fixed set of allowed angles (or orientations). We prove that MM-RAMP is PSPACE-complete even when each arm has only a few allowed angles, in sharp contrast with the single-move case. Finally, we give two fixed-parameter tractable algorithms: for MAX-SM-RAMP parameterized by the number k of arms to be made vertical, and for 2A-MM-RAMP (restricted to horizontal and vertical) parameterized by the number 𝓁 of allowed rotations.
Cite as

Nicolas Bousquet, Frank Connor, Remy El Sabeh, Louis-Roy Langevin, Amer E. Mouawad, Naomi Nishimura, and Agnes Totschnig. Robotic Arm Rotation: Standing up Is Harder Than You Think. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 10:1-10:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bousquet_et_al:LIPIcs.SWAT.2026.10,
  author =	{Bousquet, Nicolas and Connor, Frank and El Sabeh, Remy and Langevin, Louis-Roy and Mouawad, Amer E. and Nishimura, Naomi and Totschnig, Agnes},
  title =	{{Robotic Arm Rotation: Standing up Is Harder Than You Think}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{10:1--10:17},
  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.10},
  URN =		{urn:nbn:de:0030-drops-260467},
  doi =		{10.4230/LIPIcs.SWAT.2026.10},
  annote =	{Keywords: search, optimization, robotics, robotic arms, parameterized complexity, computational geometry, combinatorial reconfiguration}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2026.18
On Fréchet Traveling Salesmen Problems

Authors: Omrit Filtser, Tzalik Maimon, and Michal Moiseev

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

Abstract
The Fréchet distance is a well-studied distance measure between two curves. In this work, we demonstrate that the merit of Fréchet distance extends beyond evaluating similarity, and introduce a new setting in which it proves useful. Consider a situation where two agents are required to visit a given set of sites, while staying close to each other throughout their traversal. In this paper, we study problems where the goal is to construct two curves whose vertices are from a given set of points, under the constraint that the Fréchet distance between the curves is kept as small as possible. This problem can be viewed as a variant of the Traveling Salesman Problem (TSP), and thus may be of interest in routing, network planning and more. We present a near-linear algorithm for this problem under the discrete Fréchet distance, and explore several variants of the problem, including minimizing the lengths of the curves and balancing the number of sites assigned to each agent. Lastly, we prove that the problem is NP-hard under the continuous Fréchet Distance.
Cite as

Omrit Filtser, Tzalik Maimon, and Michal Moiseev. On Fréchet Traveling Salesmen Problems. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 18:1-18:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{filtser_et_al:LIPIcs.SWAT.2026.18,
  author =	{Filtser, Omrit and Maimon, Tzalik and Moiseev, Michal},
  title =	{{On Fr\'{e}chet Traveling Salesmen Problems}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{18:1--18:17},
  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.18},
  URN =		{urn:nbn:de:0030-drops-260545},
  doi =		{10.4230/LIPIcs.SWAT.2026.18},
  annote =	{Keywords: Fr\'{e}chet distance, traveling salesman 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.24
Single-Criteria Metric r-Dominating Set Problem via Minor-Preserving Support

Authors: Reilly Browne and Hsien-Chih Chang

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

Abstract
Given an unweighted graph G, the minimum r-dominating set problem asks for a subset of vertices S of the smallest cardinality, such that every vertex in G is within radius r to some vertex in S. While the r-dominating set problem on planar graph admits PTAS from Baker’s shifting/layering technique when r is a constant, the problem becomes significantly harder when r can depend on n. In fact, under Exponential-Time Hypothesis, Fox-Epstein ηl [SODA 2019] observed that no efficient PTAS can exist for the unbounded r-dominating set problem on planar graphs. One may consider even harder weighted-variant known as the vertex-weighted metric r-dominating set, where edges are associated with lengths, and every vertex is associated with a positive-valued weight, and the goal is to compute an r-dominating set with minimum total weight. As a result, people resorted to bicriteria algorithms by allowing the returned solution to use radius-(1+ε)r balls instead, in addition to the total weight being a 1+ε approximation to the optimal value. We establish the first single-criteria polynomial-time O(1)-approximation algorithm for the vertex-weighted metric r-dominating set problem on planar graphs when r is part of the input, and can be arbitrarily large compared to n. Our new (single-criteria) O(1)-approximation algorithm uses the quasi-uniformity sampling technique of Chan et al. [SODA 2012] by bounding the shallow cell complexity of the (unbounded) radius-r ball system to be linear in n. To this end we have two technical innovations: 1) The discrete ball system on planar graphs are neither pseudodisks nor have well-defined boundaries for standard union-complexity arguments. We construct a support graph for arbitrary distance ball systems as contractions of Voronoi cells; the sparseness comes as a byproduct. 2) We present an assignment of each depth-(≥3) cell to a unique 3-tuple of ball centers. This allows us to use standard Clarkson-Shor techniques to reduce the counting to cells of depth exactly 3, which we prove to be size O(n) by a novel geometric argument based on our support being a Voronoi contraction.
Cite as

Reilly Browne and Hsien-Chih Chang. Single-Criteria Metric r-Dominating Set Problem via Minor-Preserving Support. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 24:1-24:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{browne_et_al:LIPIcs.SoCG.2026.24,
  author =	{Browne, Reilly and Chang, Hsien-Chih},
  title =	{{Single-Criteria Metric r-Dominating Set Problem via Minor-Preserving Support}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{24:1--24: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.24},
  URN =		{urn:nbn:de:0030-drops-258300},
  doi =		{10.4230/LIPIcs.SoCG.2026.24},
  annote =	{Keywords: Minimum dominating set, planar graphs, shallow cell 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.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.60
Space-Efficient Approximate Spherical Range Counting in High Dimensions

Authors: Andreas Kalavas and Ioannis Psarros

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

Abstract
We study the following range searching problem in high-dimensional Euclidean spaces: given a finite set P ⊂ ℝ^d, where each p ∈ P is assigned a weight w_p, and radius r > 0, we need to preprocess P into a data structure such that when a new query point q ∈ ℝ^d arrives, the data structure reports the cumulative weight of points of P within Euclidean distance r from q. Solving the problem exactly seems to require space usage that is exponential to the dimension, a phenomenon known as the curse of dimensionality. Thus, we focus on approximate solutions where points up to (1+ε)r away from q may be taken into account, where ε > 0 is an input parameter known during preprocessing. We build a data structure with near-linear space usage, and query time in n^{1-Θ(ε⁴/log(1/ε))}+t_q^ϱ⋅n^{1-ϱ}, for some ϱ = Θ(ε²), where t_q is the number of points of P in the ambiguity zone, i.e., at distance between r and (1+ε)r from the query q. To the best of our knowledge, this is the first data structure with efficient space usage (subquadratic or near-linear for any ε > 0) and query time that remains sublinear for any sublinear t_q. We supplement our worst-case bounds with a query-driven preprocessing algorithm to build data structures that are well-adapted to the query distribution.
Cite as

Andreas Kalavas and Ioannis Psarros. Space-Efficient Approximate Spherical Range Counting in High Dimensions. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 60:1-60:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{kalavas_et_al:LIPIcs.SoCG.2026.60,
  author =	{Kalavas, Andreas and Psarros, Ioannis},
  title =	{{Space-Efficient Approximate Spherical Range Counting in High Dimensions}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{60:1--60: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.60},
  URN =		{urn:nbn:de:0030-drops-258670},
  doi =		{10.4230/LIPIcs.SoCG.2026.60},
  annote =	{Keywords: Approximate range counting, partition trees, high dimensions}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.70
Tree-Like Shortcuttings of Trees

Authors: Hung Le, Lazar Milenković, Shay Solomon, and Cuong Than

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

Abstract
Sparse shortcuttings of trees - equivalently, sparse 1-spanners for tree metrics with bounded hop-diameter - have been studied extensively (under different names and settings), since the pioneering works of [Andrew Chi-Chih Yao, 1982; Chazelle, 1987; Noga Alon and Baruch Schieber, 1987; Hans L. Bodlaender et al., 1994], initially motivated by applications to range queries, online tree product, and MST verification, to name a few. These constructions were also lifted from trees to other graph families using known low-distortion embedding results. The works of [Andrew Chi-Chih Yao, 1982; Chazelle, 1987; Noga Alon and Baruch Schieber, 1987; Hans L. Bodlaender et al., 1994] establish a tight tradeoff between hop-diameter and sparsity (or average degree) for tree shortcuttings and imply constant-hop shortcuttings for n-node trees with sparsity O(log^* n). Despite their small sparsity, all known constant-hop shortcuttings contain dense subgraphs (of sparsity Ω(log n)), which is a significant drawback for many applications. We initiate a systematic study of constant-hop tree shortcuttings that are "tree-like". We focus on two well-studied graph parameters that measure how far a graph is from a tree: arboricity and treewidth. Our contribution is twofold. - New upper and lower bounds for tree-like shortcuttings of trees, including an optimal tradeoff between hop-diameter and treewidth for all hop-diameter up to O(log log n). We also provide a lower bound for larger values of k, which together yield hop-diameter× treewidth = Ω((log log n)²) for all values of hop-diameter, resolving an open question of [Arnold Filtser and Hung Le, 2022; H. Le, 2023]. - Applications of these bounds, focusing on low-dimensional Euclidean and doubling metrics. A seminal work of Arya et al. [S. Arya et al., 1995] presented a (1+ε)-spanner with constant hop-diameter and sparsity O(log^* n), but with large arboricity. We show that constant hop-diameter is sufficient to achieve arboricity O(log^*{n}). Furthermore, we present a (1+ε)-stretch routing scheme in the fixed-port model with 3 hops and a local memory of O(log²n / log log n) bits, resolving an open question of [Omri Kahalon et al., 2022].
Cite as

Hung Le, Lazar Milenković, Shay Solomon, and Cuong Than. Tree-Like Shortcuttings of Trees. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 70:1-70:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{le_et_al:LIPIcs.SoCG.2026.70,
  author =	{Le, Hung and Milenkovi\'{c}, Lazar and Solomon, Shay and Than, Cuong},
  title =	{{Tree-Like Shortcuttings of Trees}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{70:1--70: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.70},
  URN =		{urn:nbn:de:0030-drops-258776},
  doi =		{10.4230/LIPIcs.SoCG.2026.70},
  annote =	{Keywords: spanner, tree shortcutting, arboricity, treewidth}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.76
A Fast Algorithm for the Hecke Representation of the Braid Group, and Applications to the Computation of the HOMFLY-PT Polynomial and the Search for Interesting Braids

Authors: Clément Maria and Hoel Queffelec

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

Abstract
Knot theory is an active field of mathematics, in which combinatorial and computational methods play an important role. One side of computational knot theory, that has gained interest in recent years, both for complexity analysis and practical algorithms, is quantum topology and the computation of topological invariants issued from the theory. In this article, we leverage the rigidity brought by the representation-theoretic origins of the quantum invariants for algorithmic purposes. We do so by exploiting braids and the algebraic properties of the braid group to describe, analyze, and implement a fast algorithm to compute the Hecke representation of the braid group. We apply this construction to design a parameterized algorithm to compute the HOMFLY-PT polynomial of knots, and demonstrate its interest experimentally. Finally, we combine our fast Hecke representation algorithm with Garside theory, to implement a reservoir sampling search and find non-trivial braids with trivial Hecke representations with coefficients in ℤ/pℤ. We find explicitly several such braids, for the 4-strand and 5-strand braid groups.
Cite as

Clément Maria and Hoel Queffelec. A Fast Algorithm for the Hecke Representation of the Braid Group, and Applications to the Computation of the HOMFLY-PT Polynomial and the Search for Interesting Braids. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 76:1-76:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{maria_et_al:LIPIcs.SoCG.2026.76,
  author =	{Maria, Cl\'{e}ment and Queffelec, Hoel},
  title =	{{A Fast Algorithm for the Hecke Representation of the Braid Group, and Applications to the Computation of the HOMFLY-PT Polynomial and the Search for Interesting Braids}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{76:1--76: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.76},
  URN =		{urn:nbn:de:0030-drops-258838},
  doi =		{10.4230/LIPIcs.SoCG.2026.76},
  annote =	{Keywords: Hecke representation of the braid group, parameterized algorithm, HOMFLY-PT polynomial of knots, reservoir sampling, faithfulness of Hecke representation}
}
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.93
Simplicial Approximation to CW Complexes with Spherical Delaunay Triangulations

Authors: Raphaël Tinarrage

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

Abstract
Simplicial approximation provides a framework for constructing simplicial complexes that are homotopy equivalent to a given manifold, provided a CW structure is explicitly known. However, its conventional implementation quickly becomes intractable on a computer: barycentric subdivision produces poorly shaped simplices, and the star condition introduces many vertices. To address these limitations, this article develops a subdivision scheme based on spherical Delaunay triangulations, which attains better refinement properties than barycentric subdivisions. Moreover, the star condition is reframed as two independent problems, one geometric and the other combinatorial, respectively tackled in the language of locally equiconnected spaces and the list homomorphism problem, allowing an exponential reduction in the number of vertices. Via a prototype implementation, we obtain simplicial complexes homotopy equivalent to Grassmannians and Stiefel manifolds up to dimension 5.
Cite as

Raphaël Tinarrage. Simplicial Approximation to CW Complexes with Spherical Delaunay Triangulations. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 93:1-93:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{tinarrage:LIPIcs.SoCG.2026.93,
  author =	{Tinarrage, Rapha\"{e}l},
  title =	{{Simplicial Approximation to CW Complexes with Spherical Delaunay Triangulations}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{93:1--93:22},
  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.93},
  URN =		{urn:nbn:de:0030-drops-258991},
  doi =		{10.4230/LIPIcs.SoCG.2026.93},
  annote =	{Keywords: Triangulation of manifolds, Simplicial approximation, CW complexes, Delaunay complexes, List homomorphism problem, Topological Data Analysis}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.5
Bifunction and Interlevel Delaunay Trifiltrations

Authors: Ángel Javier Alonso, Michael Kerber, Tung Lam, Michael Lesnick, and Abhishek Rathod

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

Abstract
A key property of the Delaunay filtration is that it is topologically (i.e., weakly) equivalent to the offset (union-of-balls) filtration. Recently, this filtration has been extended to point clouds equipped with an ℝ-valued function, yielding a computable 2-parameter filtration that satisfies an analogous weak equivalence. Motivated in part by the study of time-varying data, we introduce a 3-parameter extension of the Delaunay filtration for point clouds equipped with an ℝ²-valued function, also satisfying an analogous weak equivalence. For a point cloud X ⊂ ℝ^d, our trifiltration has size O(|X|^{⌈(d+1)/2⌉+1}). We present an algorithm that computes this trifiltration in time O(|X|^{⌈d/2⌉+2}), together with an implementation. Our experiments demonstrate that the implementation can handle thousands of points in ℝ³, with memory growth that is nearly linear.
Cite as

Ángel Javier Alonso, Michael Kerber, Tung Lam, Michael Lesnick, and Abhishek Rathod. Bifunction and Interlevel Delaunay Trifiltrations. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 5:1-5:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{alonso_et_al:LIPIcs.SoCG.2026.5,
  author =	{Alonso, \'{A}ngel Javier and Kerber, Michael and Lam, Tung and Lesnick, Michael and Rathod, Abhishek},
  title =	{{Bifunction and Interlevel Delaunay Trifiltrations}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{5:1--5: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.5},
  URN =		{urn:nbn:de:0030-drops-258118},
  doi =		{10.4230/LIPIcs.SoCG.2026.5},
  annote =	{Keywords: Delaunay triangulation, Multiparameter persistent homology, Interlevel, Bowyer-Watson}
}
  • Refine by Type
  • 147 Document/PDF
  • 49 Document/HTML
  • 1 Artifact
  • 1 Volume

  • Refine by Publication Year
  • 18 2026
  • 32 2025
  • 5 2024
  • 2 2023
  • 4 2022
  • Show More...

  • Refine by Author
  • 38 Buchin, Kevin
  • 13 Wong, Sampson
  • 9 Buchin, Maike
  • 8 Gudmundsson, Joachim
  • 8 Löffler, Maarten
  • Show More...

  • Refine by Series/Journal
  • 144 LIPIcs
  • 3 DagSemProc

  • Refine by Classification
  • 94 Theory of computation → Computational geometry
  • 14 Theory of computation → Design and analysis of algorithms
  • 5 Mathematics of computing → Discrete mathematics
  • 5 Mathematics of computing → Graphs and surfaces
  • 5 Theory of computation → Problems, reductions and completeness
  • Show More...

  • Refine by Keyword
  • 15 Fréchet distance
  • 5 clustering
  • 5 parameterized complexity
  • 5 simple polygon
  • 4 Computational Geometry
  • 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