Search Results

Documents authored by Wong, Sampson

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.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.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 Õ(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 Õ(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 Õ(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
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.ISAAC.2024.37
Approximating the Fréchet Distance When Only One Curve Is c-Packed

Authors: Joachim Gudmundsson, Tiancheng Mai, and Sampson Wong

Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)

Abstract
One approach to studying the Fréchet distance is to consider curves that satisfy realistic assumptions. By now, the most popular realistic assumption for curves is c-packedness. Existing algorithms for computing the Fréchet distance between c-packed curves require both curves to be c-packed. In this paper, we only require one of the two curves to be c-packed. Our result is a nearly-linear time algorithm that (1+ε)-approximates the Fréchet distance between a c-packed curve and a general curve in ℝ^d, for constant values of ε, d and c.
Cite as

Joachim Gudmundsson, Tiancheng Mai, and Sampson Wong. Approximating the Fréchet Distance When Only One Curve Is c-Packed. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 37:1-37:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{gudmundsson_et_al:LIPIcs.ISAAC.2024.37,
  author =	{Gudmundsson, Joachim and Mai, Tiancheng and Wong, Sampson},
  title =	{{Approximating the Fr\'{e}chet Distance When Only One Curve Is c-Packed}},
  booktitle =	{35th International Symposium on Algorithms and Computation (ISAAC 2024)},
  pages =	{37:1--37:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-354-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{322},
  editor =	{Mestre, Juli\'{a}n and Wirth, Anthony},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.37},
  URN =		{urn:nbn:de:0030-drops-221649},
  doi =		{10.4230/LIPIcs.ISAAC.2024.37},
  annote =	{Keywords: Fr\'{e}chet distance, c-packed curve, approximation algorithm}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2024.56
Data Structures for Approximate Fréchet Distance for Realistic Curves

Authors: Ivor van der Hoog, Eva Rotenberg, and Sampson Wong

Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)

Abstract
The Fréchet distance is a popular distance measure between curves P and Q. Conditional lower bounds prohibit (1+ε)-approximate Fréchet distance computations in strongly subquadratic time, even when preprocessing P using any polynomial amount of time and space. As a consequence, the Fréchet distance has been studied under realistic input assumptions, for example, assuming both curves are c-packed. In this paper, we study c-packed curves in Euclidean space ℝ^d and in general geodesic metrics 𝒳. In ℝ^d, we provide a nearly-linear time static algorithm for computing the (1+ε)-approximate continuous Fréchet distance between c-packed curves. Our algorithm has a linear dependence on the dimension d, as opposed to previous algorithms which have an exponential dependence on d. In general geodesic metric spaces X, little was previously known. We provide the first data structure, and thereby the first algorithm, under this model. Given a c-packed input curve P with n vertices, we preprocess it in O(n log n) time, so that given a query containing a constant ε and a curve Q with m vertices, we can return a (1+ε)-approximation of the discrete Fréchet distance between P and Q in time polylogarithmic in n and linear in m, 1/ε, and the realism parameter c. Finally, we show several extensions to our data structure; to support dynamic extend/truncate updates on P, to answer map matching queries, and to answer Hausdorff distance queries.
Cite as

Ivor van der Hoog, Eva Rotenberg, and Sampson Wong. Data Structures for Approximate Fréchet Distance for Realistic Curves. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 56:1-56:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{vanderhoog_et_al:LIPIcs.ISAAC.2024.56,
  author =	{van der Hoog, Ivor and Rotenberg, Eva and Wong, Sampson},
  title =	{{Data Structures for Approximate Fr\'{e}chet Distance for Realistic Curves}},
  booktitle =	{35th International Symposium on Algorithms and Computation (ISAAC 2024)},
  pages =	{56:1--56:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-354-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{322},
  editor =	{Mestre, Juli\'{a}n and Wirth, Anthony},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.56},
  URN =		{urn:nbn:de:0030-drops-221846},
  doi =		{10.4230/LIPIcs.ISAAC.2024.56},
  annote =	{Keywords: Fr\'{e}chet distance, data structures, approximation algorithms}
}
Artifact
Software
DOI: 10.4230/artifacts.22471
L-Budget Clustering (SWAT 24)

Authors: Kevin Buchin, Maike Buchin, Joachim Gudmundsson, Lukas Plätz, Lea Thiel, and Sampson Wong

Abstract
Cite as

Kevin Buchin, Maike Buchin, Joachim Gudmundsson, Lukas Plätz, Lea Thiel, Sampson Wong. L-Budget Clustering (SWAT 24) (Software). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-22471,
   title = {{L-Budget Clustering (SWAT 24)}}, 
   author = {Buchin, Kevin and Buchin, Maike and Gudmundsson, Joachim and Pl\"{a}tz, Lukas and Thiel, Lea and Wong, Sampson},
   note = {Software, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:c28806ab33cb4a564e1d492efd322b1dc32f7245;origin=https://github.com/NathenMat/SWAT24;visit=swh:1:snp:a052784ff6c68e081ad8aefeaedc032aef15e906;anchor=swh:1:rev:1d5a24b78bbc02b2b3c1e30bce4378db47c66101}{\texttt{swh:1:dir:c28806ab33cb4a564e1d492efd322b1dc32f7245}} (visited on 2024-11-28)},
   url = {https://github.com/NathenMat/SWAT24},
   doi = {10.4230/artifacts.22471},
}
Document
DOI: 10.4230/LIPIcs.ESA.2024.36
Bicriteria Approximation for Minimum Dilation Graph Augmentation

Authors: Kevin Buchin, Maike Buchin, Joachim Gudmundsson, and Sampson Wong

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
Spanner constructions focus on the initial design of the network. However, networks tend to improve over time. In this paper, we focus on the improvement step. Given a graph and a budget k, which k edges do we add to the graph to minimise its dilation? Gudmundsson and Wong [TALG'22] provided the first positive result for this problem, but their approximation factor is linear in k. Our main result is a (2 √[r]{2} k^{1/r},2r)-bicriteria approximation that runs in O(n³ log n) time, for all r ≥ 1. In other words, if t^* is the minimum dilation after adding any k edges to a graph, then our algorithm adds O(k^{1+1/r}) edges to the graph to obtain a dilation of 2rt^*. Moreover, our analysis of the algorithm is tight under the Erdős girth conjecture.
Cite as

Kevin Buchin, Maike Buchin, Joachim Gudmundsson, and Sampson Wong. Bicriteria Approximation for Minimum Dilation Graph Augmentation. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 36:1-36:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{buchin_et_al:LIPIcs.ESA.2024.36,
  author =	{Buchin, Kevin and Buchin, Maike and Gudmundsson, Joachim and Wong, Sampson},
  title =	{{Bicriteria Approximation for Minimum Dilation Graph Augmentation}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{36:1--36:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John 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.2024.36},
  URN =		{urn:nbn:de:0030-drops-211079},
  doi =		{10.4230/LIPIcs.ESA.2024.36},
  annote =	{Keywords: Greedy spanner, Graph augmentation}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2024.27
Map-Matching Queries Under Fréchet Distance on Low-Density Spanners

Authors: Kevin Buchin, Maike Buchin, Joachim Gudmundsson, Aleksandr Popov, and Sampson Wong

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract
Map matching is a common task when analysing GPS tracks, such as vehicle trajectories. The goal is to match a recorded noisy polygonal curve to a path on the map, usually represented as a geometric graph. The Fréchet distance is a commonly used metric for curves, making it a natural fit. The map-matching problem is well-studied, yet until recently no-one tackled the data structure question: preprocess a given graph so that one can query the minimum Fréchet distance between all graph paths and a polygonal curve. Recently, Gudmundsson, Seybold, and Wong [Gudmundsson et al., 2023] studied this problem for arbitrary query polygonal curves and c-packed graphs. In this paper, we instead require the graphs to be λ-low-density t-spanners, which is significantly more representative of real-world networks. We also show how to report a path that minimises the distance efficiently rather than only returning the minimal distance, which was stated as an open problem in their paper.
Cite as

Kevin Buchin, Maike Buchin, Joachim Gudmundsson, Aleksandr Popov, and Sampson Wong. Map-Matching Queries Under Fréchet Distance on Low-Density Spanners. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 27:1-27:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{buchin_et_al:LIPIcs.SoCG.2024.27,
  author =	{Buchin, Kevin and Buchin, Maike and Gudmundsson, Joachim and Popov, Aleksandr and Wong, Sampson},
  title =	{{Map-Matching Queries Under Fr\'{e}chet Distance on Low-Density Spanners}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{27:1--27:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.27},
  URN =		{urn:nbn:de:0030-drops-199723},
  doi =		{10.4230/LIPIcs.SoCG.2024.27},
  annote =	{Keywords: Map Matching, Fr\'{e}chet Distance, Data Structures}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2024.62
Approximating Multiplicatively Weighted Voronoi Diagrams: Efficient Construction with Linear Size

Authors: Joachim Gudmundsson, Martin P. Seybold, and Sampson Wong

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract
Given a set of n sites from ℝ^d, each having some positive weight factor, the Multiplicatively Weighted Voronoi Diagram is a subdivision of space that associates each cell to the site whose weighted Euclidean distance is minimal for all points in the cell. We give novel approximation algorithms that output a cube-based subdivision such that the weighted distance of a point with respect to the associated site is at most (1+ε) times the minimum weighted distance, for any fixed parameter ε ∈ (0,1). The diagram size is O_d(n log(1/ε)/ε^{d-1}) and the construction time is within an O_D(log(n)/ε^{(d+5)/2})-factor of the size bound. We also prove a matching lower bound for the size, showing that the proposed method is the first to achieve optimal size, up to Θ(1)^d-factors. In particular, the obscure log(1/ε) factor is unavoidable. As a by-product, we obtain a factor d^{O(d)} improvement in size for the unweighted case and O(d log(n) + d² log(1/ε)) point-location time in the subdivision, improving the known query bound by one d-factor. The key ingredients of our approximation algorithms are the study of convex regions that we call cores, an adaptive refinement algorithm to obtain optimal size, and a novel notion of bisector coresets, which may be of independent interest. In particular, we show that coresets with O_d(1/ε^{(d+3)/2}) worst-case size can be computed in near-linear time.
Cite as

Joachim Gudmundsson, Martin P. Seybold, and Sampson Wong. Approximating Multiplicatively Weighted Voronoi Diagrams: Efficient Construction with Linear Size. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 62:1-62:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{gudmundsson_et_al:LIPIcs.SoCG.2024.62,
  author =	{Gudmundsson, Joachim and Seybold, Martin P. and Wong, Sampson},
  title =	{{Approximating Multiplicatively Weighted Voronoi Diagrams: Efficient Construction with Linear Size}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{62:1--62:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.62},
  URN =		{urn:nbn:de:0030-drops-200078},
  doi =		{10.4230/LIPIcs.SoCG.2024.62},
  annote =	{Keywords: Multiplicatively Weighted Voronoi Diagram, Compressed QuadTree, Adaptive Refinement, Bisector Coresets, Semi-Separated Pair Decomposition, Lower Bound}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2024.18
Dynamic L-Budget Clustering of Curves

Authors: Kevin Buchin, Maike Buchin, Joachim Gudmundsson, Lukas Plätz, Lea Thiel, and Sampson Wong

Published in: LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)

Abstract
A key goal of clustering is data reduction. In center-based clustering of complex objects therefore not only the number of clusters but also the complexity of the centers plays a crucial role. We propose L-Budget Clustering as unifying perspective on this task, optimizing the clustering under the constraint that the summed complexity of all centers is at most L. We present algorithms for clustering planar curves under the Fréchet distance, but note that our algorithms more generally apply to objects in metric spaces if a notion of simplification of objects is applicable. A scenario in which data reduction is of particular importance is when the space is limited. Our main result is an efficient (8 + ε)-approximation algorithm with a (1 + ε)-resource augmentation that maintains an L-budget clustering under insertion of curves using only O(Lε^{-1}) space and O^*(L³log(L) + L²log(r^*/r₀)) time where O^* hides factors of ε^{-1}.
Cite as

Kevin Buchin, Maike Buchin, Joachim Gudmundsson, Lukas Plätz, Lea Thiel, and Sampson Wong. Dynamic L-Budget Clustering of Curves. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 18:1-18:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{buchin_et_al:LIPIcs.SWAT.2024.18,
  author =	{Buchin, Kevin and Buchin, Maike and Gudmundsson, Joachim and Pl\"{a}tz, Lukas and Thiel, Lea and Wong, Sampson},
  title =	{{Dynamic L-Budget Clustering of Curves}},
  booktitle =	{19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)},
  pages =	{18:1--18:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-318-8},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{294},
  editor =	{Bodlaender, Hans L.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.18},
  URN =		{urn:nbn:de:0030-drops-200588},
  doi =		{10.4230/LIPIcs.SWAT.2024.18},
  annote =	{Keywords: clustering, streaming algorithm, polygonal curves, Fr\'{e}chet distance, storage efficiency, simplification, approximation algorithms}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2023.34
Computing a Subtrajectory Cluster from c-Packed Trajectories

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

Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)

Abstract
We present a near-linear time approximation algorithm for the subtrajectory cluster problem of c-packed trajectories. Given a trajectory T of complexity n, an approximation factor ε, and a desired distance d, the problem involves finding m subtrajectories of T such that their pair-wise Fréchet distance is at most (1 + ε)d. At least one subtrajectory must be of length l or longer. A trajectory T is c-packed if the intersection of T and any ball B with radius r is at most c⋅r in length. Previous results by Gudmundsson and Wong [Gudmundsson and Wong, 2022] established an Ω(n³) lower bound unless the Strong Exponential Time Hypothesis fails, and they presented an O(n³ log² n) time algorithm. We circumvent this conditional lower bound by studying subtrajectory cluster on c-packed trajectories, resulting in an algorithm with an O((c² n/ε²)log(c/ε)log(n/ε)) time complexity.
Cite as

Joachim Gudmundsson, Zijin Huang, André van Renssen, and Sampson Wong. Computing a Subtrajectory Cluster from c-Packed Trajectories. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 34:1-34:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{gudmundsson_et_al:LIPIcs.ISAAC.2023.34,
  author =	{Gudmundsson, Joachim and Huang, Zijin and van Renssen, Andr\'{e} and Wong, Sampson},
  title =	{{Computing a Subtrajectory Cluster from c-Packed Trajectories}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{34:1--34:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-289-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{283},
  editor =	{Iwata, Satoru and Kakimura, Naonori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.34},
  URN =		{urn:nbn:de:0030-drops-193364},
  doi =		{10.4230/LIPIcs.ISAAC.2023.34},
  annote =	{Keywords: Subtrajectory cluster, c-packed trajectories, Computational geometry}
}
Document
DOI: 10.4230/LIPIcs.ESA.2023.26
Oriented Spanners

Authors: Kevin Buchin, Joachim Gudmundsson, Antonia Kalb, Aleksandr Popov, Carolin Rehs, André van Renssen, and Sampson Wong

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
Given a point set P in the Euclidean plane and a parameter t, we define an oriented t-spanner as an oriented subgraph of the complete bi-directed graph such that for every pair of points, the shortest cycle in G through those points is at most a factor t longer than the shortest oriented cycle in the complete bi-directed graph. We investigate the problem of computing sparse graphs with small oriented dilation. As we can show that minimising oriented dilation for a given number of edges is NP-hard in the plane, we first consider one-dimensional point sets. While obtaining a 1-spanner in this setting is straightforward, already for five points such a spanner has no plane embedding with the leftmost and rightmost point on the outer face. This leads to restricting to oriented graphs with a one-page book embedding on the one-dimensional point set. For this case we present a dynamic program to compute the graph of minimum oriented dilation that runs in 𝒪(n⁸) time for n points, and a greedy algorithm that computes a 5-spanner in 𝒪(nlog n) time. Expanding these results finally gives us a result for two-dimensional point sets: we prove that for convex point sets the greedy triangulation results in an oriented 𝒪(1)-spanner.
Cite as

Kevin Buchin, Joachim Gudmundsson, Antonia Kalb, Aleksandr Popov, Carolin Rehs, André van Renssen, and Sampson Wong. Oriented Spanners. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 26:1-26:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{buchin_et_al:LIPIcs.ESA.2023.26,
  author =	{Buchin, Kevin and Gudmundsson, Joachim and Kalb, Antonia and Popov, Aleksandr and Rehs, Carolin and van Renssen, Andr\'{e} and Wong, Sampson},
  title =	{{Oriented Spanners}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{26:1--26:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. 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.2023.26},
  URN =		{urn:nbn:de:0030-drops-186796},
  doi =		{10.4230/LIPIcs.ESA.2023.26},
  annote =	{Keywords: computational geometry, spanner, oriented graph, greedy triangulation}
}
Document
DOI: 10.4230/LIPIcs.ESA.2023.99
The Tight Spanning Ratio of the Rectangle Delaunay Triangulation

Authors: André van Renssen, Yuan Sha, Yucheng Sun, and Sampson Wong

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
Spanner construction is a well-studied problem and Delaunay triangulations are among the most popular spanners. Tight bounds are known if the Delaunay triangulation is constructed using an equilateral triangle, a square, or a regular hexagon. However, all other shapes have remained elusive. In this paper we extend the restricted class of spanners for which tight bounds are known. We prove that Delaunay triangulations constructed using rectangles with aspect ratio A have spanning ratio at most √2 √{1+A² + A √{A²+1}}, which matches the known lower bound.
Cite as

André van Renssen, Yuan Sha, Yucheng Sun, and Sampson Wong. The Tight Spanning Ratio of the Rectangle Delaunay Triangulation. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 99:1-99:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{vanrenssen_et_al:LIPIcs.ESA.2023.99,
  author =	{van Renssen, Andr\'{e} and Sha, Yuan and Sun, Yucheng and Wong, Sampson},
  title =	{{The Tight Spanning Ratio of the Rectangle Delaunay Triangulation}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{99:1--99:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. 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.2023.99},
  URN =		{urn:nbn:de:0030-drops-187523},
  doi =		{10.4230/LIPIcs.ESA.2023.99},
  annote =	{Keywords: Spanners, Delaunay Triangulation, Spanning Ratio}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2022.22
Computing Continuous Dynamic Time Warping of Time Series in Polynomial Time

Authors: Kevin Buchin, André Nusser, and Sampson Wong

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

Abstract
Dynamic Time Warping is arguably the most popular similarity measure for time series, where we define a time series to be a one-dimensional polygonal curve. The drawback of Dynamic Time Warping is that it is sensitive to the sampling rate of the time series. The Fréchet distance is an alternative that has gained popularity, however, its drawback is that it is sensitive to outliers. Continuous Dynamic Time Warping (CDTW) is a recently proposed alternative that does not exhibit the aforementioned drawbacks. CDTW combines the continuous nature of the Fréchet distance with the summation of Dynamic Time Warping, resulting in a similarity measure that is robust to sampling rate and to outliers. In a recent experimental work of Brankovic et al., it was demonstrated that clustering under CDTW avoids the unwanted artifacts that appear when clustering under Dynamic Time Warping and under the Fréchet distance. Despite its advantages, the major shortcoming of CDTW is that there is no exact algorithm for computing CDTW, in polynomial time or otherwise. In this work, we present the first exact algorithm for computing CDTW of one-dimensional curves. Our algorithm runs in time 𝒪(n⁵) for a pair of one-dimensional curves, each with complexity at most n. In our algorithm, we propagate continuous functions in the dynamic program for CDTW, where the main difficulty lies in bounding the complexity of the functions. We believe that our result is an important first step towards CDTW becoming a practical similarity measure between curves.
Cite as

Kevin Buchin, André Nusser, and Sampson Wong. Computing Continuous Dynamic Time Warping of Time Series in Polynomial Time. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 22:1-22:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{buchin_et_al:LIPIcs.SoCG.2022.22,
  author =	{Buchin, Kevin and Nusser, Andr\'{e} and Wong, Sampson},
  title =	{{Computing Continuous Dynamic Time Warping of Time Series in Polynomial Time}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{22:1--22:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.22},
  URN =		{urn:nbn:de:0030-drops-160307},
  doi =		{10.4230/LIPIcs.SoCG.2022.22},
  annote =	{Keywords: Computational Geometry, Curve Similarity, Fr\'{e}chet distance, Dynamic Time Warping, Continuous Dynamic Time Warping}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2020.9
Approximating the Packedness of Polygonal Curves

Authors: Joachim Gudmundsson, Yuan Sha, and Sampson Wong

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Abstract
In 2012 Driemel et al. [Anne Driemel et al., 2012] introduced the concept of c-packed curves as a realistic input model. In the case when c is a constant they gave a near linear time (1+ε)-approximation algorithm for computing the Fréchet distance between two c-packed polygonal curves. Since then a number of papers have used the model. In this paper we consider the problem of computing the smallest c for which a given polygonal curve in ℝ^d is c-packed. We present two approximation algorithms. The first algorithm is a 2-approximation algorithm and runs in O(dn² log n) time. In the case d = 2 we develop a faster algorithm that returns a (6+ε)-approximation and runs in O((n/ε³)^{4/3} polylog (n/ε))) time. We also implemented the first algorithm and computed the approximate packedness-value for 16 sets of real-world trajectories. The experiments indicate that the notion of c-packedness is a useful realistic input model for many curves and trajectories.
Cite as

Joachim Gudmundsson, Yuan Sha, and Sampson Wong. Approximating the Packedness of Polygonal Curves. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 9:1-9:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{gudmundsson_et_al:LIPIcs.ISAAC.2020.9,
  author =	{Gudmundsson, Joachim and Sha, Yuan and Wong, Sampson},
  title =	{{Approximating the Packedness of Polygonal Curves}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{9:1--9:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.9},
  URN =		{urn:nbn:de:0030-drops-133530},
  doi =		{10.4230/LIPIcs.ISAAC.2020.9},
  annote =	{Keywords: Computational geometry, trajectories, realistic input models}
}
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact