DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2026.15

Euclidean Noncrossing Steiner Spanners of Nearly Optimal Sparsity

Authors: Sujoy Bhore, Sándor Kisfaludi‑Bak, Lazar Milenković, Csaba D. Tóth, Karol Węgrzycki, and Sampson Wong

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

Abstract

A Euclidean noncrossing Steiner (1+ε)-spanner for a point set P ⊂ ℝ² is a planar straight-line graph that, for any two points a, b ∈ P, contains a path whose length is at most 1+ε times the Euclidean distance between a and b. We construct a Euclidean noncrossing Steiner (1+ε)-spanner with O(n/ε^{3/2}) edges for any set of n points in the plane. This result improves upon the previous best upper bound of O(n/ε⁴) obtained nearly three decades ago. We also establish an almost matching lower bound: There exist n points in the plane for which any Euclidean noncrossing Steiner (1+ε)-spanner has Ω_μ(n/ε^{3/2-μ}) edges for any μ > 0. Our lower bound uses recent generalizations of the Szemerédi-Trotter theorem to disk-tube incidences in geometric measure theory.

Cite as

Sujoy Bhore, Sándor Kisfaludi‑Bak, Lazar Milenković, Csaba D. Tóth, Karol Węgrzycki, and Sampson Wong. Euclidean Noncrossing Steiner Spanners of Nearly Optimal Sparsity. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 15:1-15:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bhore_et_al:LIPIcs.SoCG.2026.15,
  author =	{Bhore, Sujoy and Kisfaludi‑Bak, S\'{a}ndor and Milenkovi\'{c}, Lazar and T\'{o}th, Csaba D. and W\k{e}grzycki, Karol and Wong, Sampson},
  title =	{{Euclidean Noncrossing Steiner Spanners of Nearly Optimal Sparsity}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{15:1--15: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.15},
  URN =		{urn:nbn:de:0030-drops-258210},
  doi =		{10.4230/LIPIcs.SoCG.2026.15},
  annote =	{Keywords: geometric network design, spanners, crossing number, incidences}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2026.55

Linear Time Single-Source Shortest Path Algorithms in Euclidean Graph Classes

Authors: Joachim Gudmundsson, Yuan Sha, and Sampson Wong

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

Abstract

In the celebrated paper of Henzinger, Klein, Rao and Subramanian (1997), it was shown that planar graphs admit a linear time single-source shortest path algorithm. Their algorithm unfortunately does not extend to Euclidean graph classes. We give criteria and prove that any Euclidean graph class satisfying the criteria admits a linear time single-source shortest path algorithm. As a main ingredient, we show that the contracted graphs of these Euclidean graph classes admit sublinear separators.

Cite as

Joachim Gudmundsson, Yuan Sha, and Sampson Wong. Linear Time Single-Source Shortest Path Algorithms in Euclidean Graph Classes. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 55:1-55:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{gudmundsson_et_al:LIPIcs.SoCG.2026.55,
  author =	{Gudmundsson, Joachim and Sha, Yuan and Wong, Sampson},
  title =	{{Linear Time Single-Source Shortest Path Algorithms in Euclidean Graph Classes}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{55:1--55:14},
  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.55},
  URN =		{urn:nbn:de:0030-drops-258618},
  doi =		{10.4230/LIPIcs.SoCG.2026.55},
  annote =	{Keywords: Graph algorithms, Single-Source Shortest Path, Euclidean Graphs, Recursive Division}
}

Document

DOI: 10.4230/LIPIcs.ESA.2025.25

Instance-Optimal Imprecise Convex Hull

Authors: Sarita de Berg, Ivor van der Hoog, Eva Rotenberg, Daniel Rutschmann, and Sampson Wong

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

Abstract

Imprecise measurements of a point set P = (p₁, …, p_n) can be modelled by a family of regions F = (R₁, …, R_n), where each imprecise region R_i ∈ F contains a unique point p_i ∈ P. A retrieval models an accurate measurement by replacing an imprecise region R_i with its corresponding point p_i. We construct the convex hull of an imprecise point set in the plane, by determining the cyclic ordering of the convex hull vertices of P as efficiently as possible. Efficiency is interpreted in two ways: (i) minimising the number of retrievals, and (ii) the computation time to determine the set of regions that must be retrieved. Previous works focused on only one of these two aspects: either minimising retrievals or optimising algorithmic runtime. Our contribution is the first to simultaneously achieve both. Let r(F, P) denote the minimal number of retrievals required by any algorithm to determine the convex hull of P for a given instance (F, P). For a family F of n constant-complexity polygons, our main result is a reconstruction algorithm that performs Θ(r(F, P)) retrievals in O(r(F, P) log³ n) time. Compared to previous approaches that achieve optimal retrieval counts, we improve the runtime per retrieval from polynomial to polylogarithmic. We extend the generality of previous results to simple k-gons, to pairwise disjoint disks with radii in [1,k], and to unit disks where at most k disks overlap in a single point. Our runtime scales linearly with k.

Cite as

Sarita de Berg, Ivor van der Hoog, Eva Rotenberg, Daniel Rutschmann, and Sampson Wong. Instance-Optimal Imprecise Convex Hull. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 25:1-25:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{deberg_et_al:LIPIcs.ESA.2025.25,
  author =	{de Berg, Sarita and van der Hoog, Ivor and Rotenberg, Eva and Rutschmann, Daniel and Wong, Sampson},
  title =	{{Instance-Optimal Imprecise Convex Hull}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{25:1--25:15},
  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.25},
  URN =		{urn:nbn:de:0030-drops-244932},
  doi =		{10.4230/LIPIcs.ESA.2025.25},
  annote =	{Keywords: convex hull, imprecise geometry preprocessing model, partial information}
}

Document

DOI: 10.4230/LIPIcs.ESA.2025.12

Subtrajectory Clustering and Coverage Maximization in Cubic Time, or Better

Authors: Jacobus Conradi and Anne Driemel

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

Abstract

Many application areas collect unstructured trajectory data. In subtrajectory clustering, one is interested to find patterns in this data using a hybrid combination of segmentation and clustering. We analyze two variants of this problem based on the well-known SetCover and CoverageMaximization problems. In both variants the set system is induced by metric balls under the Fréchet distance centered at polygonal curves. Our algorithms focus on improving the running time of the update step of the generic greedy algorithm by means of a careful combination of sweeps through a candidate space. In the first variant, we are given a polygonal curve P of complexity n, distance threshold Δ and complexity bound 𝓁 and the goal is to identify a minimum-size set of center curves 𝒞, where each center curve is of complexity at most 𝓁 and every point p on P is covered. A point p on P is covered if it is part of a subtrajectory π_p of P such that there is a center c ∈ 𝒞 whose Fréchet distance to π_p is at most Δ. We present an approximation algorithm for this problem with a running time of 𝒪((n²𝓁 + √{k_Δ}n^{5/2})log²n), where k_Δ is the size of an optimal solution. The algorithm gives a bicriterial approximation guarantee that relaxes the Fréchet distance threshold by a constant factor and the size of the solution by a factor of 𝒪(log n). The second problem variant asks for the maximum fraction of the input curve P that can be covered using k center curves, where k ≤ n is a parameter to the algorithm. For the second problem variant, our techniques lead to an algorithm with a running time of 𝒪((k+𝓁)n²log²n) and similar approximation guarantees. Note that in both algorithms k,k_Δ ∈ O(n) and hence the running time is cubic, or better if k ≪ n.

Cite as

Jacobus Conradi and Anne Driemel. Subtrajectory Clustering and Coverage Maximization in Cubic Time, or Better. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 12:1-12:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{conradi_et_al:LIPIcs.ESA.2025.12,
  author =	{Conradi, Jacobus and Driemel, Anne},
  title =	{{Subtrajectory Clustering and Coverage Maximization in Cubic Time, or Better}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{12:1--12: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.12},
  URN =		{urn:nbn:de:0030-drops-244806},
  doi =		{10.4230/LIPIcs.ESA.2025.12},
  annote =	{Keywords: Clustering, Set cover, Fr\'{e}chet distance, Approximation algorithms}
}

Document

DOI: 10.4230/LIPIcs.ESA.2025.84

Property Testing of Curve Similarity

Authors: Peyman Afshani, Maike Buchin, Anne Driemel, Marena Richter, and Sampson Wong

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

Abstract

We propose sublinear algorithms for probabilistic testing of the discrete and continuous Fréchet distance - a standard similarity measure for curves. We assume the algorithm is given access to the input curves via a query oracle: a query returns the set of vertices of the curve that lie within a radius δ of a specified vertex of the other curve. The goal is to use a small number of queries to determine with constant probability whether the two curves are similar (i.e., their discrete Fréchet distance is at most δ) or they are "ε-far" (for 0 < ε < 2) from being similar, i.e., more than an ε-fraction of the two curves must be ignored for them to become similar. We present two algorithms which are sublinear assuming that the curves are t-approximate shortest paths in the ambient metric space, for some t ≪ n. The first algorithm uses O(t/ε log t/ε) queries and is given the value of t in advance. The second algorithm does not have explicit knowledge of the value of t and therefore needs to gain implicit knowledge of the straightness of the input curves through its queries. We show that the discrete Fréchet distance can still be tested using roughly O({t³+t² log n}/ε) queries ignoring logarithmic factors in t. Our algorithms work in a matrix representation of the input and may be of independent interest to matrix testing. Our algorithms use a mild uniform sampling condition that constrains the edge lengths of the curves, similar to a polynomially bounded aspect ratio. Applied to testing the continuous Fréchet distance of t-straight curves, our algorithms can be used for (1+ε')-approximate testing using essentially the same bounds as stated above with an additional factor of poly(1/(ε')).

Cite as

Peyman Afshani, Maike Buchin, Anne Driemel, Marena Richter, and Sampson Wong. Property Testing of Curve Similarity. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 84:1-84:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{afshani_et_al:LIPIcs.ESA.2025.84,
  author =	{Afshani, Peyman and Buchin, Maike and Driemel, Anne and Richter, Marena and Wong, Sampson},
  title =	{{Property Testing of Curve Similarity}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{84:1--84:16},
  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.84},
  URN =		{urn:nbn:de:0030-drops-245522},
  doi =		{10.4230/LIPIcs.ESA.2025.84},
  annote =	{Keywords: Fr\'{e}chet distance, Trajectory Analysis, Curve Similarity, Property Testing, Monotonicity Testing}
}

Document

DOI: 10.4230/LIPIcs.WADS.2025.9

Online Routing in Directed Yao₄^∞ Graphs

Authors: Prosenjit Bose, Jean-Lou De Carufel, and John Stuart

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract

The x⃑{Yao₄^∞} and x⃑{Yao₄} graphs are two families of directed geometric graphs whose vertices are points in the plane, and each vertex has up to four outgoing edges. Consider a horizontal and a vertical line through each vertex v, defining four quadrants around v. Then v has an outgoing edge to the closest vertex in each of its four quadrants. When the distance is measured using the Euclidean norm, the resulting graph is the x⃑{Yao₄} graph, whereas with the L_∞-norm, we obtain the x⃑{Yao^{∞}₄} graph, which is a sub-graph of the well-known L_∞-Delaunay graph. In this paper, we provide a local routing algorithm with routing ratio at most 85.22 for x⃑{Yao^{∞}₄} graphs. Prior to this work, no constant spanning or routing ratios for x⃑{Yao₄^∞} graphs were previously known. Now, x⃑{Yao₄^∞} graphs are the sparsest family of directed planar graphs supporting a competitive local routing strategy. Furthermore, we show that no local routing algorithm for x⃑{Yao₄^∞} graphs can have a routing ratio lower than 7+√2≈ 8.41. Moreover, we prove that the spanning ratio is at least 5+√2≈ 6.41 in the worst case. The techniques we develop in this paper also allow us to prove lower bounds of 7-√3+√{5-2√3}≈ 6.51 and 7+√2 for the spanning and routing ratios of x⃑{Yao₄}, respectively.

Cite as

Prosenjit Bose, Jean-Lou De Carufel, and John Stuart. Online Routing in Directed Yao₄^∞ Graphs. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 9:1-9:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bose_et_al:LIPIcs.WADS.2025.9,
  author =	{Bose, Prosenjit and De Carufel, Jean-Lou and Stuart, John},
  title =	{{Online Routing in Directed Yao₄^∞ Graphs}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{9:1--9:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.9},
  URN =		{urn:nbn:de:0030-drops-242404},
  doi =		{10.4230/LIPIcs.WADS.2025.9},
  annote =	{Keywords: Geometric Spanners, Yao Graphs, Local Routing Algorithms}
}

Document

DOI: 10.4230/LIPIcs.WADS.2025.21

A WSPD, Separator and Small Tree Cover for c-Packed Graphs

Authors: Lindsey Deryckere, Joachim Gudmundsson, André van Renssen, Yuan Sha, and Sampson Wong

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract

The c-packedness property, proposed in 2010, is a geometric property that captures the spatial distribution of a set of edges. Despite the recent interest in c-packedness, its utility has so far been limited to Fréchet distance problems. An open problem is whether a wider variety of algorithmic and data structure problems can be solved efficiently under the c-packedness assumption, and more specifically, on c-packed graphs. In this paper, we prove two fundamental properties of c-packed graphs: that there exists a linear-size well-separated pair decomposition under the graph metric, and there exists a constant size balanced separator. We then apply these fundamental properties to obtain a small tree cover for the metric space and distance oracles under the shortest path metric. In particular, we obtain a tree cover of constant size, an exact distance oracle of near-linear size and an approximate distance oracle of linear size.

Cite as

Lindsey Deryckere, Joachim Gudmundsson, André van Renssen, Yuan Sha, and Sampson Wong. A WSPD, Separator and Small Tree Cover for c-Packed Graphs. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 21:1-21:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{deryckere_et_al:LIPIcs.WADS.2025.21,
  author =	{Deryckere, Lindsey and Gudmundsson, Joachim and van Renssen, Andr\'{e} and Sha, Yuan and Wong, Sampson},
  title =	{{A WSPD, Separator and Small Tree Cover for c-Packed Graphs}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{21:1--21:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.21},
  URN =		{urn:nbn:de:0030-drops-242529},
  doi =		{10.4230/LIPIcs.WADS.2025.21},
  annote =	{Keywords: Well-separated pair decomposition, separator, tree cover, distance oracles, realistic graphs}
}

Document

DOI: 10.4230/LIPIcs.WADS.2025.33

Spanner for the 0/1/∞ Weighted Region Problem

Authors: Joachim Gudmundsson, Zijin Huang, André van Renssen, and Sampson Wong

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract

We consider the problem of computing an approximate weighted shortest path in a weighted planar subdivision, with weights assigned from the set {0, 1, ∞}. The subdivision includes zero-cost regions (0-regions) with weight 0 and obstacles with weight ∞, all embedded in a plane with weight 1. In a polygonal domain, where the 0-regions and obstacles are non-overlapping polygons (not necessarily convex) with in total N vertices, we present an algorithm that computes a (1 + ε)-approximate spanner of the input vertices in expected Õ(N/ε³) time, for 0 < ε < 1. Using our spanner, we can compute a (1 + ε)-approximate weighted shortest path between any two points (not necessarily vertices) in Õ(N/ε³) time. Furthermore, we prove that our results more generally apply to non-polygonal convex regions. Using this generalisation, one can approximate the weak partial Fréchet similarity [Buchin et al., 2009] between two polygonal curves in expected Õ(n²/ε²) time, where n is the total number of vertices of the input curves.

Cite as

Joachim Gudmundsson, Zijin Huang, André van Renssen, and Sampson Wong. Spanner for the 0/1/∞ Weighted Region Problem. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 33:1-33:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gudmundsson_et_al:LIPIcs.WADS.2025.33,
  author =	{Gudmundsson, Joachim and Huang, Zijin and van Renssen, Andr\'{e} and Wong, Sampson},
  title =	{{Spanner for the 0/1/∞ Weighted Region Problem}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{33:1--33:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.33},
  URN =		{urn:nbn:de:0030-drops-242644},
  doi =		{10.4230/LIPIcs.WADS.2025.33},
  annote =	{Keywords: weighted region problem, approximate shortest path, spanner}
}

Document

DOI: 10.4230/LIPIcs.SEA.2025.7

Continuous Map Matching to Paths Under Travel Time Constraints

Authors: Yannick Bosch and Sabine Storandt

Published in: LIPIcs, Volume 338, 23rd International Symposium on Experimental Algorithms (SEA 2025)

Abstract

In this paper, we study the problem of map matching with travel time constraints. Given a sequence of k spatio-temporal measurements and an embedded path graph with travel time costs, the goal is to snap each measurement to a close-by location in the graph, such that consecutive locations can be reached from one another along the path within the timestamp difference of the respective measurements. This problem arises in public transit data processing as well as in map matching of movement trajectories to general graphs. We show that the classical approach for this problem, which relies on selecting a finite set of candidate locations in the graph for each measurement, cannot guarantee to find a consistent solution. We propose a new algorithm that can deal with an infinite set of candidate locations per measurement. We prove that our algorithm always detects a consistent map matching path (if one exists). Despite the enlarged candidate set, we also demonstrate that our algorithm has superior running time in theory and practice. For a path graph with n nodes, we show that our algorithm runs in 𝒪(k² n log {nk}) and under mild assumptions in 𝒪(k n ^λ + n log³ n) for λ ≈ 0.695. This is a significant improvement over the baseline, which runs in 𝒪(k n²) and which might not even identify a correct solution. The performance of our algorithm hinges on an efficient segment-circle intersection data structure. We describe how to design and implement such a data structure for our application. In the experimental evaluation, we demonstrate the usefulness of our novel algorithm on a diverse set of generated measurements as well as GTFS data.

Cite as

Yannick Bosch and Sabine Storandt. Continuous Map Matching to Paths Under Travel Time Constraints. In 23rd International Symposium on Experimental Algorithms (SEA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 338, pp. 7:1-7:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bosch_et_al:LIPIcs.SEA.2025.7,
  author =	{Bosch, Yannick and Storandt, Sabine},
  title =	{{Continuous Map Matching to Paths Under Travel Time Constraints}},
  booktitle =	{23rd International Symposium on Experimental Algorithms (SEA 2025)},
  pages =	{7:1--7:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-375-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{338},
  editor =	{Mutzel, Petra and Prezza, Nicola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2025.7},
  URN =		{urn:nbn:de:0030-drops-232457},
  doi =		{10.4230/LIPIcs.SEA.2025.7},
  annote =	{Keywords: Map matching, Travel time, Segment-circle intersection data structure}
}

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2025.133

Faster, Deterministic and Space Efficient Subtrajectory Clustering

Authors: Ivor van der Hoog, Thijs van der Horst, and Tim Ophelders

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract

Given a trajectory T and a distance Δ, we wish to find a set C of curves of complexity at most 𝓁, such that we can cover T with subcurves that each are within Fréchet distance Δ to at least one curve in C. We call C an (𝓁,Δ)-clustering and aim to find an (𝓁,Δ)-clustering of minimum cardinality. This problem variant was introduced by Akitaya et al. (2021) and shown to be NP-complete. The main focus has therefore been on bicriteria approximation algorithms, allowing for the clustering to be an (𝓁, Θ(Δ))-clustering of roughly optimal size. We present algorithms that construct (𝓁,4Δ)-clusterings of 𝒪(k log n) size, where k is the size of the optimal (𝓁, Δ)-clustering. We use 𝒪(n³) space and 𝒪(k n³ log⁴ n) time. Our algorithms significantly improve upon the clustering quality (improving the approximation factor in Δ) and size (whenever 𝓁 ∈ Ω(log n / log k)). We offer deterministic running times improving known expected bounds by a factor near-linear in 𝓁. Additionally, we match the space usage of prior work, and improve it substantially, by a factor super-linear in n𝓁, when compared to deterministic results.

Cite as

Ivor van der Hoog, Thijs van der Horst, and Tim Ophelders. Faster, Deterministic and Space Efficient Subtrajectory Clustering. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 133:1-133:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{vanderhoog_et_al:LIPIcs.ICALP.2025.133,
  author =	{van der Hoog, Ivor and van der Horst, Thijs and Ophelders, Tim},
  title =	{{Faster, Deterministic and Space Efficient Subtrajectory Clustering}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{133:1--133:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l 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.2025.133},
  URN =		{urn:nbn:de:0030-drops-235109},
  doi =		{10.4230/LIPIcs.ICALP.2025.133},
  annote =	{Keywords: Fr\'{e}chet distance, clustering, set cover}
}

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2025.36

Faster Fréchet Distance Under Transformations

Authors: Kevin Buchin, Maike Buchin, Zijin Huang, André Nusser, and Sampson Wong

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract

We study the problem of computing the Fréchet distance between two polygonal curves under transformations. First, we consider translations in the Euclidean plane. Given two curves π and σ of total complexity n and a threshold δ ≥ 0, we present an 𝒪̃(n^{7 + 1/3}) time algorithm to determine whether there exists a translation t ∈ ℝ² such that the Fréchet distance between π and σ + t is at most δ. This improves on the previous best result, which is an 𝒪(n⁸) time algorithm. We then generalize this result to any class of rationally parameterized transformations, which includes translation, rotation, scaling, and arbitrary affine transformations. For a class T of rationally parametrized transformations with k degrees of freedom, we show that one can determine whether there is a transformation τ ∈ T such that the Fréchet distance between π and τ(σ) is at most δ in 𝒪̃(n^{3k+4/3}) time.

Cite as

Kevin Buchin, Maike Buchin, Zijin Huang, André Nusser, and Sampson Wong. Faster Fréchet Distance Under Transformations. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 36:1-36:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{buchin_et_al:LIPIcs.ICALP.2025.36,
  author =	{Buchin, Kevin and Buchin, Maike and Huang, Zijin and Nusser, Andr\'{e} and Wong, Sampson},
  title =	{{Faster Fr\'{e}chet Distance Under Transformations}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{36:1--36:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l 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.2025.36},
  URN =		{urn:nbn:de:0030-drops-234137},
  doi =		{10.4230/LIPIcs.ICALP.2025.36},
  annote =	{Keywords: Fr\'{e}chet distance, curve similarity, shape matching}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2025.27

Computing Oriented Spanners and Their Dilation

Authors: Kevin Buchin, Antonia Kalb, Anil Maheshwari, Saeed Odak, Carolin Rehs, Michiel Smid, and Sampson Wong

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

Abstract

Given a point set P in a metric space and a real number t ≥ 1, an oriented t-spanner is an oriented graph G = (P, E), where for every pair of distinct points p and q in P, the shortest oriented closed walk in G that contains p and q is at most a factor t longer than the perimeter of the smallest triangle in P containing p and q. The oriented dilation of a graph G is the minimum t for which G is an oriented t-spanner. For arbitrary point sets of size n in ℝ^d, where d ≥ 2 is a constant, the only known oriented spanner construction is an oriented 2-spanner with binom(n,2) edges. Moreover, there exists a set P of four points in the plane, for which the oriented dilation is larger than 1.46, for any oriented graph on P. We present the first algorithm that computes, in Euclidean space, a sparse oriented spanner whose oriented dilation is bounded by a constant. More specifically, for any set of n points in ℝ^d, where d is a constant, we construct an oriented (2+ε)-spanner with 𝒪(n) edges in 𝒪(n log n) time and 𝒪(n) space. Our construction uses the well-separated pair decomposition and an algorithm that computes a (1+ε)-approximation of the minimum-perimeter triangle in P containing two given query points in 𝒪(log n) time. While our algorithm is based on first computing a suitable undirected graph and then orienting it, we show that, in general, computing the orientation of an undirected graph that minimises its oriented dilation is NP-hard, even for point sets in the Euclidean plane. We further prove that even if the oriented graph is already given, computing its oriented dilation is APSP-hard for points in a general metric space. We complement this result with an algorithm that approximates the oriented dilation of a given graph in subcubic time for point sets in ℝ^d, where d is a constant.

Cite as

Kevin Buchin, Antonia Kalb, Anil Maheshwari, Saeed Odak, Carolin Rehs, Michiel Smid, and Sampson Wong. Computing Oriented Spanners and Their Dilation. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 27:1-27:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{buchin_et_al:LIPIcs.SoCG.2025.27,
  author =	{Buchin, Kevin and Kalb, Antonia and Maheshwari, Anil and Odak, Saeed and Rehs, Carolin and Smid, Michiel and Wong, Sampson},
  title =	{{Computing Oriented Spanners and Their Dilation}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{27:1--27:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.27},
  URN =		{urn:nbn:de:0030-drops-231792},
  doi =		{10.4230/LIPIcs.SoCG.2025.27},
  annote =	{Keywords: spanner, oriented graph, dilation, orientation, well-separated pair decomposition, minimum-perimeter triangle}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2025.54

The Fréchet Distance Unleashed: Approximating a Dog with a Frog

Authors: Sariel Har-Peled, Benjamin Raichel, and Eliot W. Robson

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

Abstract

We show that a variant of the continuous Fréchet distance between polygonal curves can be computed using essentially the same algorithm used to solve the discrete version. The new variant is not necessarily monotone, but this shortcoming can be easily handled via refinement. Combined with a Dijkstra/Prim type algorithm, this leads to a realization of the Fréchet distance (i.e., a morphing) that is locally optimal (aka locally correct), that is both easy to compute, and in practice, takes near linear time on many inputs. The new morphing has the property that the leash is always as short as possible. These matchings/morphings are more natural, and are better than the ones computed by standard algorithms - in particular, they handle noise more graciously. This should make the Fréchet distance more useful for real world applications. We implemented the new algorithm, and various strategies to obtain fast practical performance. We performed extensive experiments with our new algorithm, and released publicly available (and easily installable and usable) Julia and Python packages. In particular, the Julia implementation, for computing the regular Fréchet distance, seems to be {significantly faster} than other currently available implementations. See Table 2.2. Our algorithms can be used to compute the almost-exact Fréchet distance between polygonal curves. Implementations and numerous examples are available here: https://frechet.xyz.

Cite as

Sariel Har-Peled, Benjamin Raichel, and Eliot W. Robson. The Fréchet Distance Unleashed: Approximating a Dog with a Frog. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 54:1-54:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{harpeled_et_al:LIPIcs.SoCG.2025.54,
  author =	{Har-Peled, Sariel and Raichel, Benjamin and Robson, Eliot W.},
  title =	{{The Fr\'{e}chet Distance Unleashed: Approximating a Dog with a Frog}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{54:1--54:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.54},
  URN =		{urn:nbn:de:0030-drops-232066},
  doi =		{10.4230/LIPIcs.SoCG.2025.54},
  annote =	{Keywords: Curve similarity, Fr\'{e}chet distance}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2025.22

Transforming Dogs on the Line: On the Fréchet Distance Under Translation or Scaling in 1D

Authors: Lotte Blank, Jacobus Conradi, Anne Driemel, Benedikt Kolbe, André Nusser, and Marena Richter

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

Abstract

The Fréchet distance is a computational mainstay for comparing polygonal curves. The Fréchet distance under translation, which is a translation invariant version, considers the similarity of two curves independent of their location in space. It is defined as the minimum Fréchet distance that arises from allowing arbitrary translations of the input curves. This problem and numerous variants of the Fréchet distance under some transformations have been studied, with more work concentrating on the discrete Fréchet distance, leaving a significant gap between the discrete and continuous versions of the Fréchet distance under transformations. Our contribution is twofold: First, we present an algorithm for the Fréchet distance under translation on 1-dimensional curves of complexity n with a running time of 𝒪(n^{8/3} log³ n). To achieve this, we develop a novel framework for the problem for 1-dimensional curves, which also applies to other scenarios and leads to our second contribution. We present an algorithm with the same running time of 𝒪(n^{8/3} log³ n) for the Fréchet distance under scaling for 1-dimensional curves. For both algorithms we match the running times of the discrete case and improve the previously best known bounds of 𝒪̃(n⁴). Our algorithms rely on technical insights but are conceptually simple, essentially reducing the continuous problem to the discrete case across different length scales.

Cite as

Lotte Blank, Jacobus Conradi, Anne Driemel, Benedikt Kolbe, André Nusser, and Marena Richter. Transforming Dogs on the Line: On the Fréchet Distance Under Translation or Scaling in 1D. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 22:1-22:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{blank_et_al:LIPIcs.SoCG.2025.22,
  author =	{Blank, Lotte and Conradi, Jacobus and Driemel, Anne and Kolbe, Benedikt and Nusser, Andr\'{e} and Richter, Marena},
  title =	{{Transforming Dogs on the Line: On the Fr\'{e}chet Distance Under Translation or Scaling in 1D}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{22:1--22:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.22},
  URN =		{urn:nbn:de:0030-drops-231746},
  doi =		{10.4230/LIPIcs.SoCG.2025.22},
  annote =	{Keywords: Fr\'{e}chet distance under translation, Fr\'{e}chet distance under scaling, time series, shape matching}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2025.48

Exact Algorithms for Minimum Dilation Triangulation

Authors: Sándor P. Fekete, Phillip Keldenich, and Michael Perk

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

Abstract

We provide a spectrum of new theoretical insights and practical results for finding a Minimum Dilation Triangulation (MDT), a natural geometric optimization problem of considerable previous attention: Given a set P of n points in the plane, find a triangulation T, such that a shortest Euclidean path in T between any pair of points increases by the smallest possible factor compared to their straight-line distance. No polynomial-time algorithm is known for the problem; moreover, evaluating the objective function involves computing the sum of (possibly many) square roots. On the other hand, the problem is not known to be NP-hard. (1) We provide practically robust methods and implementations for computing an MDT for benchmark sets with up to 30,000 points in reasonable time on commodity hardware, based on new geometric insights into the structure of optimal edge sets. Previous methods only achieved results for up to 200 points, so we extend the range of optimally solvable instances by a factor of 150. (2) We develop scalable techniques for accurately evaluating many shortest-path queries that arise as large-scale sums of square roots, allowing us to certify exact optimal solutions, with previous work relying on (possibly inaccurate) floating-point computations. (3) We resolve an open problem by establishing a lower bound of 1.44116 on the dilation of the regular 84-gon (and thus for arbitrary point sets), improving the previous worst-case lower bound of 1.4308 and greatly reducing the remaining gap to the upper bound of 1.4482 from the literature. In the process, we provide optimal solutions for regular n-gons up to n = 100.

Cite as

Sándor P. Fekete, Phillip Keldenich, and Michael Perk. Exact Algorithms for Minimum Dilation Triangulation. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 48:1-48:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{fekete_et_al:LIPIcs.SoCG.2025.48,
  author =	{Fekete, S\'{a}ndor P. and Keldenich, Phillip and Perk, Michael},
  title =	{{Exact Algorithms for Minimum Dilation Triangulation}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{48:1--48:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.48},
  URN =		{urn:nbn:de:0030-drops-232006},
  doi =		{10.4230/LIPIcs.SoCG.2025.48},
  annote =	{Keywords: dilation, minimum dilation triangulation, exact algorithms, algorithm engineering, experimental evaluation}
}

31 Search Results for "Wong, Sampson"

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Thanks for your feedback!

Could not send message