7 Search Results for "Wong, Sampson"

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-dev.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-dev.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-dev.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-dev.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}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.7
On β-Plurality Points in Spatial Voting Games

Authors: Boris Aronov, Mark de Berg, Joachim Gudmundsson, and Michael Horton

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract
Let V be a set of n points in ℝ^d, called voters. A point p ∈ ℝ^d is a plurality point for V when the following holds: for every q ∈ ℝ^d the number of voters closer to p than to q is at least the number of voters closer to q than to p. Thus, in a vote where each v ∈ V votes for the nearest proposal (and voters for which the proposals are at equal distance abstain), proposal p will not lose against any alternative proposal q. For most voter sets a plurality point does not exist. We therefore introduce the concept of β-plurality points, which are defined similarly to regular plurality points except that the distance of each voter to p (but not to q) is scaled by a factor β, for some constant 0<β⩽1. We investigate the existence and computation of β-plurality points, and obtain the following results. - Define β^*_d := sup{β : any finite multiset V in ℝ^d admits a β-plurality point}. We prove that β^*₂ = √3/2, and that 1/√d ⩽ β^*_d ⩽ √3/2 for all d⩾3. - Define β(V) := sup {β : V admits a β-plurality point}. We present an algorithm that, given a voter set V in {ℝ}^d, computes an (1-ε)⋅ β(V) plurality point in time O(n²/ε^(3d-2) ⋅ log(n/ε^(d-1)) ⋅ log²(1/ε)).
Cite as

Boris Aronov, Mark de Berg, Joachim Gudmundsson, and Michael Horton. On β-Plurality Points in Spatial Voting Games. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 7:1-7:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{aronov_et_al:LIPIcs.SoCG.2020.7,
  author =	{Aronov, Boris and de Berg, Mark and Gudmundsson, Joachim and Horton, Michael},
  title =	{{On \beta-Plurality Points in Spatial Voting Games}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{7:1--7:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.7},
  URN =		{urn:nbn:de:0030-drops-121651},
  doi =		{10.4230/LIPIcs.SoCG.2020.7},
  annote =	{Keywords: Computational geometry, Spatial voting theory, Plurality point, Computational social choice}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.50
Fast Algorithms for Geometric Consensuses

Authors: Sariel Har-Peled and Mitchell Jones

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract
Let P be a set of n points in ℝ^d in general position. A median hyperplane (roughly) splits the point set P in half. The yolk of P is the ball of smallest radius intersecting all median hyperplanes of P. The egg of P is the ball of smallest radius intersecting all hyperplanes which contain exactly d points of P. We present exact algorithms for computing the yolk and the egg of a point set, both running in expected time O(n^(d-1) log n). The running time of the new algorithm is a polynomial time improvement over existing algorithms. We also present algorithms for several related problems, such as computing the Tukey and center balls of a point set, among others.
Cite as

Sariel Har-Peled and Mitchell Jones. Fast Algorithms for Geometric Consensuses. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 50:1-50:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{harpeled_et_al:LIPIcs.SoCG.2020.50,
  author =	{Har-Peled, Sariel and Jones, Mitchell},
  title =	{{Fast Algorithms for Geometric Consensuses}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{50:1--50:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.50},
  URN =		{urn:nbn:de:0030-drops-122088},
  doi =		{10.4230/LIPIcs.SoCG.2020.50},
  annote =	{Keywords: Geometric optimization, centerpoint, voting games}
}
  • Refine by Author
  • 5 Wong, Sampson
  • 4 Gudmundsson, Joachim
  • 3 van Renssen, André
  • 2 Buchin, Kevin
  • 2 Sha, Yuan
  • Show More...

  • Refine by Classification
  • 4 Theory of computation → Computational geometry
  • 3 Theory of computation → Design and analysis of algorithms

  • Refine by Keyword
  • 3 Computational geometry
  • 1 Computational Geometry
  • 1 Computational social choice
  • 1 Continuous Dynamic Time Warping
  • 1 Curve Similarity
  • Show More...

  • Refine by Type
  • 7 document

  • Refine by Publication Year
  • 3 2020
  • 3 2023
  • 1 2022

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact