Author name cluster

Sampson Wong

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

5 papers

2 author rows

SODA Conference 2023 Conference Paper

Map matching queries on realistic input graphs under the Fréchet distance

Joachim Gudmundsson
Martin P. Seybold
Sampson Wong

Map matching is a common preprocessing step for analysing vehicle trajectories. In the theory community, the most popular approach for map matching is to compute a path on the road network that is the most spatially similar to the trajectory, where spatial similarity is measured using the Fréchet distance. A shortcoming of existing map matching algorithms under the Fréchet distance is that every time a trajectory is matched, the entire road network needs to be reprocessed from scratch. An open problem is whether one can preprocess the road network into a data structure, so that map matching queries can be answered in sublinear time. In this paper, we investigate map matching queries under the Fréchet distance. We provide a negative result for geometric planar graphs. We show that, unless SETH fails, there is no data structure that can be constructed in polynomial time that answers map matching queries in O((pq) 1-δ ) query time for any δ > 0, where p and q are the complexities of the geometric planar graph and the query trajectory, respectively. We provide a positive result for realistic input graphs, which we regard as the main result of this paper. We show that for c -packed graphs, one can construct a data structure of Õ(cp) size that can answer (1 + ε)-approximate map matching queries in Õ ( c 4 q log 4 p ) time, where Õ (·) hides lower-order factors and dependence of ε. * The full version of the paper can be accessed at https: //arxiv. org/abs/2211. 02951

Details

TCS Journal 2022 Journal Article

Covering a set of line segments with a few squares

Joachim Gudmundsson
Mees van de Kerkhof
André van Renssen
Frank Staals
Lionov Wiratma
Sampson Wong

We study three covering problems in the plane. Our original motivation for these problems comes from trajectory analysis. The first is to decide whether a given set of line segments can be covered by up to k = 4 unit-sized, axis-parallel squares. We give linear time algorithms for k ≤ 3 and an O ( n log ⁡ n ) time algorithm for k = 4. The second is to build a data structure on a trajectory to efficiently answer whether any query subtrajectory is coverable by up to three unit-sized axis-parallel squares. For k = 2 and k = 3 we construct data structures of size O ( n α ( n ) log ⁡ n ) in O ( n α ( n ) log ⁡ n ) time, so that we can test if an arbitrary subtrajectory can be k-covered in O ( log ⁡ n ) time. The third problem is to compute a longest subtrajectory of a given trajectory that can be covered by up to two unit-sized axis-parallel squares. We give O ( n 2 α ( n ) log 2 ⁡ n ) time algorithms for k ≤ 2.

Details DOI

SODA Conference 2022 Conference Paper

Cubic upper and lower bounds for subtrajectory clustering under the continuous Fréchet distance

Joachim Gudmundsson
Sampson Wong

Detecting commuting patterns or migration patterns in movement data is an important problem in computational movement analysis. Given a trajectory, or set of trajectories, this corresponds to clustering similar subtrajectories. We study subtrajectory clustering under the continuous and discrete Fréchet distances. The most relevant theoretical result is by Buchin et al. (2011). They provide, in the continuous case, an O ( n 5 ) time algorithm and a 3SUM-hardness lower bound, and in the discrete case, an O ( n 3 ) time algorithm. We show, in the continuous case, an O ( n 3 log 2 n ) time algorithm and a 3OV-hardness lower bound, and in the discrete case, an O ( n 2 log n ) time algorithm and a quadratic lower bound. Our bounds are almost tight unless SETH fails.

Details

SODA Conference 2021 Conference Paper

Improving the dilation of a metric graph by adding edges

Joachim Gudmundsson
Sampson Wong

Most of the literature on spanners focuses on building the graph from scratch. This paper instead focuses on adding edges to improve an existing graph. A major open problem in this field is: given a graph embedded in a metric space, and a budget of k edges, which k edges do we add to produce a minimum-dilation graph? The special case where k = 1 has been studied in the past, but no major breakthroughs have been made for k > 1. We provide the first positive result, an O ( k )-approximation algorithm that runs in O ( n 3 log n ) time.

Details

AAAI Conference 2019 Conference Paper

Computing the Yolk in Spatial Voting Games without Computing Median Lines

Joachim Gudmundsson
Sampson Wong

The yolk is an important concept in spatial voting games: the yolk center generalises the equilibrium and the yolk radius bounds the uncovered set. We present near-linear time algorithms for computing the yolk in the plane. To the best of our knowledge our algorithm is the first that does not precompute median lines, and hence is able to break the best known upper bound of O(n4/3 ) on the number of limiting median lines. We avoid this requirement by carefully applying Megiddo’s parametric search technique, which is a powerful framework that could lead to faster algorithms for other spatial voting problems.

PDF Details