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.

Low density graphs are considered to be a realistic graph class for modelling road networks. It has advantages over other popular graph classes for road networks, such as planar graphs, bounded highway dimension graphs, and spanners. We believe that low density graphs have the potential to be a useful graph class for road networks, but until now, its usefulness is limited by a lack of available tools.

Abstract Given a point set P in the Euclidean plane and a parameter t , we define an oriented t -spanner G as an oriented subgraph of the complete bi-directed graph such that for every pair of points, the shortest closed walk in G through those points is at most a factor t longer than the shortest cycle in the complete graph on P . 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 $$\mathcal {O}(n^7)$$ time for n points, and a greedy algorithm that computes a 5-spanner in $$\mathcal {O}(n\log 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 a plane oriented t -spanner with $$t=7.2 \cdot t_g$$ , where $$t_g$$ is an upper bound on the dilation of the greedy triangulation.

Predicting soccer match outcomes is a challenging task due to the inherently unpredictable nature of the game and the numerous dynamic factors influencing results. While it conventionally relies on meticulous feature engineering, deep learning techniques have recently shown a great promise in learning effective player and team representations directly for soccer outcome prediction. However, existing methods often overlook the heterogeneous nature of interactions among players and teams, which is crucial for accurately modeling match dynamics. To address this gap, we propose HIGFormer (Heterogeneous Interaction Graph Transformer), a novel graph-augmented transformer-based deep learning model for soccer outcome prediction. HIGFormer introduces a multi-level interaction framework that captures both fine-grained player dynamics and high-level team interactions. Specifically, it comprises (1) a Player Interaction Network, which encodes player performance through heterogeneous interaction graphs, combining local graph convolutions with a global graph-augmented transformer; (2) a Team Interaction Network, which constructs interaction graphs from a team-to-team perspective to model historical match relationships; and (3) a Match Comparison Transformer, which jointly analyzes both team and player-level information to predict match outcomes. Extensive experiments on the WyScout Open Access Dataset, a large-scale real-world soccer dataset, demonstrate that HIGFormer significantly outperforms existing methods in prediction accuracy. Furthermore, we provide valuable insights into leveraging our model for player performance evaluation, offering a new perspective on talent scouting and team strategy analysis.

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.

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 Oe(N/ε3) time1, for 0 < ε < 1. Using our spanner, we can compute a (1 + ε)-approximate weighted shortest path between any two points (not necessarily vertices) in Oe(N/ε3) 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 [7] between two polygonal curves in expected Oe(n2/ε2) time, where n is the total number of vertices of the input curves.

Given a set of n ≥ 1 unit disk robots in the Euclidean plane , we consider the Pattern Formation problem, i.e., the robots must reposition themselves to form a given target pattern. This problem arises under obstructed visibility, where a robot cannot see another robot if there is a third robot on the straight line segment between the two robots. Recently, this problem was solved in the asynchonous model for fat robots that agree on at least one axis in the robots with lights model where each robot is equipped with an externally visible persistent light that can assume colors from a fixed set of colors [1] . In this work, we reduce the number of colors needed and remove the axis-agreement requirement in the fully synchronous model. In particular, we present an algorithm requiring 7 colors when scaling the target pattern is allowed and an 8-color algorithm if scaling is not allowed. Our algorithms run in O ( n ) + O ( q log ⁡ n ) rounds with probability at least 1 − n − q .

Given a set of n ≥ 1 autonomous, anonymous, indistinguishable, silent, and possibly disoriented mobile unit disk (i.e., fat) robots operating following Look-Compute-Move cycles in the Euclidean plane , we consider the Pattern Formation problem: from arbitrary starting positions, the robots must reposition themselves to form a given target pattern. This problem arises under obstructed visibility, where a robot cannot see another robot if there is a third robot on the straight line segment between the two robots. We assume that a robot's movement cannot be interrupted by an adversary and that robots have a small O ( 1 ) -sized memory that they can use to store information, but that cannot be communicated to the other robots. To solve this problem, we present an algorithm that works in three steps. First it establishes mutual visibility, then it elects one robot to be the leader, and finally it forms the required pattern. The whole algorithm runs in O ( n ) + O ( q log ⁡ n ) rounds with probability at least 1 − n − q . The algorithms are collision-free and do not require the knowledge of the number of robots.

on Computational Geometry (SoCG'23) was held at The University of Texas at Dallas, USA, from June 12 to 15, 2023, as part of Computational Geometry Week (CG Week).This special issue of Discrete & Computational Geometry features a selection of papers presented at the symposium.Out of 175 submissions to SoCG'23, 61 were accepted for presentation.From these, seven particularly outstanding papers were selected for inclusion in this issue.The papers span diverse areas in computational geometry and topology, including graph drawing, topological data analysis, approximation algorithms, and parameterized complexity.Each paper was submitted, reviewed, and revised in accordance with the journal's high standards.We are grateful to the anonymous referees for their time and effort in verifying and improving these contributions.We also thank the authors for their thoughtful revisions and careful polishing of their work.The papers in this special issue appear in alphabetical order according to the names of the first authors.In the remainder of this foreword, we briefly introduce all accepted papers.Our first paper is "Decomposition of Zero-Dimensional Persistence Modules via Rooted Subsets", by Ángel Javier Alonso and Michael Kerber.In this work, the authors study zero-dimensional persistence modules, giving a decomposition based at the level of sets rather than vector spaces.This formalization allows for a more combinatorial study of the problem, and they are able to identify intervals in persistence that correspond to clusters of points.Using this framework, they give a lower bound for the number of intervals for density-Rips filtrations in Euclidean space, allowing for new and exciting practical insights into the behavior of these commonly used data sets.

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.

Given a set of $n$ sites from $\mathbb{R}^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+\varepsilon)$ times the minimum weighted distance, for any fixed parameter $\varepsilon \in (0,1)$. The diagram size is $O_d(n \log(1/\varepsilon)/\varepsilon^{d-1})$ and the construction time is within an $O_D(\log(n)/\varepsilon^{(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 \emph{optimal size}, up to $Θ(1)^d$-factors. In particular, the obscure $\log(1/\varepsilon)$ 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^2 \log(1/\varepsilon))$ 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 \emph{bisector coresets}, which may be of independent interest. In particular, we show that coresets with $O_d(1/\varepsilon^{(d+3)/2})$ worst-case size can be computed in near-linear time.

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.

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.

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 article, 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 article. We show that for c -packed graphs, one can construct a data structure of \(\tilde{O}(cp)\) size that can answer (1+ε)-approximate map matching queries in \(\tilde{O}(c^4 q \log ^4 p)\) time, where \(\tilde{O}(\cdot)\) hides lower-order factors and dependence on ε.

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.

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 [24] established an Ω(n3) lower bound unless the Strong Exponential Time Hypothesis fails, and they presented an O(n3 log2 n) time algorithm. We circumvent this conditional lower bound by studying subtrajectory cluster on c-packed trajectories, resulting in an algorithm with an O((c2n/ε2) log(c/ε) log(n/ε)) time complexity.

A beer digraph G is a real-valued weighted directed graph where some of the vertices have beer stores. A beer path from a vertex u to a vertex v in G is a path in G from u to v that visits at least one beer store. In this paper we consider the online shortest beer path query in beer digraphs with bounded treewidth t. Assume that a tree decomposition of treewidth t on a beer digraph with n vertices is given. We show that after O(t³n) time preprocessing on the beer digraph, (i) a beer distance query can be answered in O(t³α(n)) time, where α(n) is the inverse Ackermann function, and (ii) a shortest beer path can be reported in O(t³α(n)L) time, where L is the number of edges on the path. In the process we show an improved O(t³α(n)L) time shortest path query algorithm, compared with the currently best O(t⁴α(n)L) time algorithm [Chaudhuri & Zaroliagis, 2000]. We also consider queries in a dynamic setting where the weight of an edge in G can change over time. We show two data structures. Assume t is constant and let β be any constant in (0,1). The first data structure uses O(n) preprocessing time, answers a beer distance query in O(α(n)) time and reports a shortest beer path in O(α(n) L) time. It can be updated in O(n^β) time after an edge weight change. The second data structure has O(n) preprocessing time, answers a beer distance query in O(log n) time, reports a shortest beer path in O(log n + L) time, and can be updated in O(log n) time after an edge weight change.

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 Õ(c4q log4p) 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

The Randomized Incremental Construction (RIC) of search DAGs for point location in planar subdivisions, nearest-neighbor search in 2D points, and extreme point search in 3D convex hulls, are well known to take (n log n) expected time for structures of (n) expected size. Moreover, searching takes w.h.p. (log n) comparisons in the first and w.h.p. (log2 n) comparisons in the latter two DAGs. However, the expected depth of the DAGs and high probability bounds for their size are unknown. Using a novel analysis technique, we show that the three DAGs have w.h.p. i) a size of (n), ii) a depth of (log n), and iii) a construction time of (n log n). One application of these new and improved results are remarkably simple Las Vegas verifiers to obtain search DAGs with optimal worst-case bounds. This positively answers the conjectured logarithmic search cost in the DAG of Delaunay triangulations [Guibas et al.; ICALP 1990] and a conjecture on the depth of the DAG of Trapezoidal subdivisions [Hemmer et al.; ESA 2012]. It also shows that history-based RIC circumvents a lower bound on runtime tail estimates of conflict-graph RICs [Sen; STACS 2019].

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(n5) time algorithm1 and a 3SUM-hardness lower bound, and in the discrete case, an O(n3) time algorithm. We show, in the continuous case, an O(n3 log2 n) time algorithm and a 3OV-hardness lower bound, and in the discrete case, an O(n2 log n) time algorithm and a quadratic lower bound. Our bounds are almost tight unless SETH fails.

Abstract Online routing in a planar embedded graph is central to a number of fields and has been studied extensively in the literature. For most planar graphs no O(1)-competitive online routing algorithm exists. A notable exception is the Delaunay triangulation for which Bose and Morin (SIAM J Comput 33(4):937–951, 2004) showed that there exists an online routing algorithm that is O(1)-competitive. However, a Delaunay triangulation can have $$\varOmega (n)$$ Ω ( n ) vertex degree and a total weight that is a linear factor greater than the weight of a minimum spanning tree. We show a simple construction, given a set V of n points in the Euclidean plane, of a planar geometric graph on V that has small weight (within a constant factor of the weight of a minimum spanning tree on V), constant degree, and that admits a local routing strategy that is O(1)-competitive. Moreover, the technique used to bound the weight works generally for any planar geometric graph whilst preserving the admission of an O(1)-competitive routing strategy.

Most of the literature on spanners focuses on building the graph from scratch. This article 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.

We study the problem of sub-trajectory nearest-neighbor queries on polygonal curves under the continuous Fréchet distance. Given a trajectory P with n vertices and a query trajectory Q, we seek to report a vertex-aligned sub-trajectory P' of P that is closest to Q, i.e. P' must start and end on contiguous vertices of P.

We study the problem of augmenting a metric graph by adding k edges while minimizing the radius of the augmented graph. We give a simple 3-approximation algorithm and show that there is no polynomial-time (5/3-ε)-approximation algorithm, for any ε > 0, unless P = NP. We also give two exact algorithms for the special case when the input graph is a tree, one of which is generalized to handle metric graphs with bounded treewidth.

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(n3 log n) time.

Let V be a set of n points in mathcal R d , called voters . A point p ∈ mathcal R d is a plurality point for V when the following holds: For every q ∈ mathcal R 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 := {β : any finite multiset V in mathcal R d admits a β-plurality point. We prove that β * d = √3/2, and that 1/√ d ⩽ β * d ⩽ √ 3/2 for all d ⩾ 3. • Define β ( p, V ) := sup {β : p is a β -plurality point for V }. Given a voter set V in mathcal R 2 , we provide an algorithm that runs in O ( n log n ) time and computes a point p such that β ( p , V ) ⩾ β * b . Moreover, for d ⩾ 2, we can compute a point p with β ( p , V ) ⩾ 1/√ d in O ( n ) time. • Define β ( V ) := sup { β : V admits a β -plurality point}. We present an algorithm that, given a voter set V in mathcal R d , computes an ((1-ɛ)ċ β ( V ))-plurality point in time O n 2 ɛ 3d-2 ċ log n ɛ d-1 ċ log 2 1ɛ).

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/ε)).

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.

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.

The Euclidean k-Center problem is a classical problem that has been extensively studied in computer science. Given a set G of n points in Euclidean space, the problem is to determine a set C of k centers (not necessarily part of G) such that the maximum distance between a point in G and its nearest neighbor in C is minimized. In this paper we study the corresponding (k, ℓ)-CENTER problem for polygonal curves under the Fréchet distance, that is, given a set G of n polygonal curves in ℝd, each of complexity m, determine a set C of k polygonal curves in ℝd, each of complexity ℓ, such that the maximum Fréchet distance of a curve in G to its closest curve in C is minimized. In their 2016 paper, Driemel, Krivošija, and Sohler give a near-linear time (1 + ε-approximation algorithm for one-dimensional curves, assuming that k and ℓ are constants. In this paper, we substantially extend and improve the known approximation bounds for curves in dimension 2 and higher. Our analysis thus extends to application-relevant input data such as GPS-trajectories and protein backbones. We show that, if ℓ is part of the input, then there is no polynomial-time approximation scheme unless P = NP. Our constructions yield different bounds for one and two-dimensional curves and the discrete and continuous Fréchet distance. In the case of the discrete Fréchet distance on two-dimensional curves, we show hardness of approximation within a factor close to 2.598. This result also holds when k = 1, and the NP-hardness extends to the case that ℓ = ∞, i.e., for the problem of computing the minimum-enclosing ball under the Fréchet distance. Finally, we observe that a careful adaptation of Gonzalez’ algorithm in combination with a curve simplification yields a 3-approximation in any dimension, provided that an optimal simplification can be computed exactly. We conclude that our approximation bounds are close to being tight.

We study the following problem: preprocess a set $$\mathcal {O}$$ of objects into a data structure that allows us to efficiently report all pairs of objects from $$\mathcal {O}$$ that intersect inside an axis-aligned query range $${Q}$$ . We present data structures of size $$O(n\cdot {{\mathrm{polylog\,}}}n)$$ and with query time $$O((k+1)\cdot {{\mathrm{polylog\,}}}n)$$ time, where k is the number of reported pairs, for two classes of objects in $${\mathbb R}^2$$ : axis-aligned rectangles and objects with small union complexity. For the 3-dimensional case where the objects and the query range are axis-aligned boxes in $${\mathbb R}^3$$ , we present a data structure of size $$O(n\sqrt{n}\cdot {{\mathrm{polylog\,}}}n)$$ and query time $$O((\sqrt{n}+k)\cdot {{\mathrm{polylog\,}}}n)$$ . When the objects and query are fat, we obtain $$O((k+1)\cdot {{\mathrm{polylog\,}}}n)$$ query time using $$O(n\cdot {{\mathrm{polylog\,}}}n)$$ storage.

Let V be a set of n points in R d , which we call voters. A point p ∈ R d is preferred over another point p ′ ∈ R d by a voter υ ∈ V if dist(υ, p ) < dist(υ, p ′). A point p is called a plurality point if it is preferred by at least as many voters as any other point p ′. We present an algorithm that decides in O ( n log n ) time whether V admits a plurality point in the L 2 norm and, if so, finds the (unique) plurality point. We also give efficient algorithms to compute a minimum-cost subset W ⊂ V such that V \ W admits a plurality point, and to compute a so-called minimum-radius plurality ball. Finally, we consider the problem in the personalized L 1 norm, where each point υ ∈ V has a preference vector 〈 w 1 (υ),…, w d (υ)〉 and the distance from υ to any point p ∈ R d is given by ∑ i =1 d w i (υ)· | x i (υ)− x i ( p )|. For this case we can compute in O ( n d −1 ) time the set of all plurality points of V . When all preference vectors are equal, the running time improves to O ( n ).

Let S be a set of n polygonal trajectories in the plane and k be a fixed constant. We present a data structure to store S so that, given a k-vertex query trajectory Q, we can answer the following queries approximately:

Let C be the unit circle in R^2. We can view C as a plane graph whose vertices are all the points on C, and the distance between any two points on C is the length of the smaller arc between them. We consider a graph augmentation problem on C, where we want to place k >= 1 shortcuts on C such that the diameter of the resulting graph is minimized. We analyze for each k with 1 <= k <= 7 what the optimal set of shortcuts is. Interestingly, the minimum diameter one can obtain is not a strictly decreasing function of k. For example, with seven shortcuts one cannot obtain a smaller diameter than with six shortcuts. Finally, we prove that the optimal diameter is 2 + Theta(1/k^(2/3)) for any k.

Given a line segment I=[0,L], the so-called barrier, and a set of n sensors with varying ranges positioned on the line containing I, the barrier coverage problem is to move the sensors so that they cover I, while minimising the total movement. In the case when all the sensors have the same radius the problem can be solved in O(n log n) time (Andrews and Wang, Algorithmica 2017). If the sensors have different radii the problem is known to be NP-hard to approximate within a constant factor (Czyzowicz et al., ADHOC-NOW 2009). We strengthen this result and prove that no polynomial time \rho^{1-\epsilon}-approximation algorithm exists unless P=NP, where \rho is the ratio between the largest radius and the smallest radius. Even when we restrict the number of sensors that are allowed to move by a parameter k, the problem turns out to be W[1]-hard. On the positive side we show that a ((2+\epsilon)\rho+2/\epsilon)-approximation can be computed in O(n^3/\epsilon^2) time and we prove fixed-parameter tractability when parameterized by the total movement assuming all numbers in the input are integers.

Locality-sensitive hashing (LSH) is a fundamental technique for similarity search and similarity estimation in high-dimensional spaces. The basic idea is that similar objects should produce hash collisions with probability significantly larger than objects with low similarity. We consider LSH for objects that can be represented as point sets in either one or two dimensions. To make the point sets finite size we consider the subset of points on a grid. Directly applying LSH (e.g. min-wise hashing) to these point sets would require time proportional to the number of points. We seek to achieve time that is much lower than direct approaches. Technically, we introduce new primitives for range-efficient consistent sampling (of independent interest), and show how to turn such samples into LSH values. Another application of our technique is a data structure for quickly estimating the size of the intersection or union of a set of preprocessed polygons. Curiously, our consistent sampling method uses transformation to a geometric problem.

Let V be a set of n points in R^d, which we call voters, where d is a fixed constant. A point p in R^d is preferred over another point p' in R^d by a voter v in V if dist(v,p) < dist(v,p'). A point p is called a plurality point if it is preferred by at least as many voters as any other point p'. We present an algorithm that decides in O(n log n) time whether V admits a plurality point in the L_2 norm and, if so, finds the (unique) plurality point. We also give efficient algorithms to compute the smallest subset W of V such that V - W admits a plurality point, and to compute a so-called minimum-radius plurality ball. Finally, we consider the problem in the personalized L_1 norm, where each point v in V has a preference vector and the distance from v to any point p in R^d is given by sum_{i=1}^d w_i(v) cdot |x_i(v)-x_i(p)|. For this case we can compute in O(n^(d-1)) time the set of all plurality points of V. When all preference vectors are equal, the running time improves to O(n).

A widely used class of algorithms for computing tree decompositions of graphs are heuristics that compute an elimination order, i.e., a permutation of the vertex set. In this paper, we propose to turbocharge these heuristics. For a target treewidth k, suppose the heuristic has already computed a partial elimination order of width at most k, but extending it by one more vertex exceeds the target width k. At this moment of regret, we solve a subproblem which is to recompute the last c positions of the partial elimination order such that it can be extended without exceeding width k. We show that this subproblem is fixed-parameter tractable when parameterized by k and c, but it is para-NP-hard and W[1]-hard when parameterized by only k or c, respectively. Our experimental evaluation of the FPT algorithm shows that we can trade a reasonable increase of the running time for quality of the solution.

Interactions between trajectories need to be analyzed in various domains to gain insight into movement patterns. Such interactions often take place with some delayed response. We propose an approach to analyze and visualize delayed responses on two trajectories recorded simultaneously and with the same sampling rate. Central to our approach is the computation of a matching between the trajectories in a so-called delay space. We also introduce a new similarity measure between trajectories, which combines directional and spatial characteristics. To evaluate our approach experimentally, we have implemented it as a prototype visual analytics tool and have applied the tool on two datasets.

Given a trajectory T we study the problem of reporting all subtrajectory clusters of T. To measure similarity between trajectory we choose the Frechet distance. We adapt an existing serial algorithm into a GPU parallel algorithm, resulting in substantial speed-ups, in some cases up to 11× faster, and increasing the size of the data that can be handled in reasonable amount of time, tests were performed on trajectories three times the size as previously managed. This is to the best of our knowledge not only the first GPU implementation of a subtrajectory clustering algorithm but also the first implementation using the continuous Frechet distance, instead of the discrete Frechet distance.

We study one of the basic tasks in moving object analysis, namely the location of hotspots. A hotspot is a (small) region in which an entity spends a significant amount of time. Finding such regions is useful in many applications, for example in segmentation, clustering, and locating popular places. We may be interested in locating a minimum size hotspot in which the entity spends a fixed amount of time, or locating a fixed size hotspot maximizing the time that the entity spends inside it. Furthermore, we can consider the total time, or the longest contiguous time the entity spends in the hotspot. We solve all four versions of the problem. For a square hotspot, we can solve the contiguous-time versions in O(nlogn) time, where n is the number of trajectory vertices. The algorithms for the total-time versions are roughly quadratic. Finding a hotspot containing relatively the most time, compared to its size, takes O(n3) time. Even though we focus on a single moving entity, our algorithms immediately extend to multiple entities. Finally, we consider hotspots of different shape.

In response to the increasing volume of trajectory data obtained, e.g., from tracking athletes, animals, or meteorological phenomena, we present a new space-efficient algorithm for the analysis of trajectory data. The algorithm combines techniques from computational geometry, data mining, and string processing and offers a modular design that allows for a user-guided exploration of trajectory data incorporating domain-specific constraints and objectives.

Given a trajectory T we study the problem of reporting all subtrajectory clusters of T. To measure similarity between curves we choose the Fréchet distance. We show how the existing sequential algorithm can be modified exploiting parallel algorithms together with the GPU computational power showing substantial speed-ups.

Analysing a football match is without doubt an important task for coaches, talent scouts, players and even media; and with current technologies more and more match data is collected. Several companies offer the ability to track the position of the players and the ball with high accuracy and high resolution. They also offer software that include basic analysis tools, for example straight-forward statistics about distance run and number of passes. It is, however, a non-trivial task to perform more advanced analysis. We present a collection of tools that we developed specifically for analysing the performance of football players and teams.

Greedy forwarding is an efficient and scalable geographic routing algorithm for wireless networks. To guarantee the success of greedy forwarding, many research efforts assign virtual coordinates to nodes to obtain a greedy embedding of the network. Different from these existing efforts, this paper presents an approach that enables greedy forwarding to succeed in directional wireless networks by selecting links in the network instead of assigning virtual coordinates to the nodes. Specifically, this paper studies the following problem: given a set of nodes on the Euclidean plane, how can we add a minimum number of point-to-point links, such that the greedy forwarding algorithm succeeds on the resulting network. The motivation for studying this problem is that each point-to-point link in directional wireless networks is realized by a pair of directional antennas, so minimizing the number of links will reduce the network installation cost. This paper first presents the properties of the graphs supporting greedy forwarding, and then solves the above problem optimally by Integer Linear Programming and also sub-optimally by a polynomial-time 3-approximation algorithm. Finally, this paper compares the polynomial-time algorithm with the optimal solution, showing that the polynomial-time algorithm can actually generate within 1.1 times the number of links found by the optimal solution in most cases.

Let (S,d) be a finite metric space, where each element p∈S has a non-negative weight w (p). We study spanners for the set S with respect to the following weighted distance function: $$\mathbf{d}_{\omega}(p,q)=\left\{\begin{array}{ll}0&\mbox{ if $p=q$,}\\ \operatorname {w}(p)+\mathbf{d}(p,q)+ \operatorname {w}(q)&\mbox{ if $p\neq q$.}\end{array}\right.$$ We present a general method for turning spanners with respect to the d-metric into spanners with respect to the d ω -metric. For any given ε>0, we can apply our method to obtain (5+ε)-spanners with a linear number of edges for three cases: points in Euclidean space ℝ d , points in spaces of bounded doubling dimension, and points on the boundary of a convex body in ℝ d where d is the geodesic distance function. We also describe an alternative method that leads to (2+ε)-spanners for weighted point points in ℝ d and for points on the boundary of a convex body in ℝ d . The number of edges in these spanners is O(nlog n). This bound on the stretch factor is nearly optimal: in any finite metric space and for any ε>0, it is possible to assign weights to the elements such that any non-complete graph has stretch factor larger than 2−ε.

In this paper we consider query versions of visibility testing and visibility counting. Let S be a set of n disjoint line segments in ℜ2 and let s be an element of S. Visibility testing is to preprocess S so that we can quickly determine if s is visible from a query point q. Visibility counting involves preprocessing S so that one can quickly estimate the number of segments in S visible from a query point q.

Time plays an important role in the analysis of moving object data. For many applications it is not sufficient to only compare objects at exactly the same times, or to consider only the geometry of their trajectories. We show how to leverage between these two approaches by extending a tool from curve analysis, namely the free space diagram. Our approach also allows us to take further attributes of the objects like speed or direction into account. We demonstrate the usefulness of the new tool by applying it to the problem of detecting single file movement. A single file is a set of moving entities, which are following each other, one behind the other. Our algorithm is the first one developed for detecting such movement patterns. For this application, we analyse demonstrate the performance of our tool both theoretically experimentally.

We present a new and simple (1+ε)-spanner of size O(nε2) for a set of n points in the plane, which can be maintained efficiently as the points move. Assuming the trajectories of the points can be described by polynomials whose degrees are at most s, the number of topological changes to the spanner is O((n/ε2).λs+2(n)), and at each event the spanner can be updated in O(1) time.

We study the problem of detecting a single file behavior in a set of trajectories. A group of entities is moving in single file if they are following each other, one behind the other. This movement pattern occurs often, among animals, humans, and vehicles. It is challenging to detect because it does not have a fixed layout.In this paper we first model the notion of following behind, on which we base our definition of single file. We present efficient algorithms for detecting following behind and single file behaviors. We test and evaluate these algorithms on real and generated test data.

Given a Euclidean graph G in $\mathbb{R}^d$ with n vertices and m edges, we consider the problem of adding an edge to G such that the stretch factor of the resulting graph is minimized. Currently, the fastest algorithm for computing the stretch factor of a graph with positive edge weights runs in $\cal{O}$$(nm+n^2 \log n)$ time, resulting in a trivial $\cal{O}$$(n^3m+n^4 \log n)$-time algorithm for computing the optimal edge. First, we show that a simple modification yields the optimal solution in $\cal{O}$$(n^4)$ time using $\cal{O}$$(n^2)$ space. To reduce the running time we consider several approximation algorithms.

Given an arbitrary real constant ε > 0, and a geometric graph G in d -dimensional Euclidean space with n points, O ( n ) edges, and constant dilation, our main result is a data structure that answers (1 + ε)-approximate shortest-path-length queries in constant time. The data structure can be constructed in O ( n log n ) time using O ( n log n ) space. This represents the first data structure that answers (1 + ε)-approximate shortest-path queries in constant time, and hence functions as an approximate distance oracle. The data structure is also applied to several other problems. In particular, we also show that approximate shortest-path queries between vertices in a planar polygonal domain with “rounded” obstacles can be answered in constant time. Other applications include query versions of closest-pair problems, and the efficient computation of the approximate dilations of geometric graphs. Finally, we show how to extend the main result to answer (1 + ε)-approximate shortest-path-length queries in constant time for geometric spanner graphs with m = ω( n ) edges. The resulting data structure can be constructed in O ( m + n log n ) time using O ( n log n ) space.

The aperture angle α(x, Q) of a point x∉ Q in the plane with respect to a convex polygon Q is the angle of the smallest cone with apex x that contains Q. The aperture angle approximation error of a compact convex set C in the plane with respect to an inscribed convex polygon Q ⊂ C is the minimum aperture angle of any x ∈ C ࢨ Q with respect to Q. We show that for any compact convex set C in the plane and any k > 2, there is an inscribed convex k-gon Q ⊂ C with aperture angle approximation error (1 - 2/k+1)π. This bound is optimal, and settles a conjecture by Fekete from the early 1990s. The same proof technique can be used to prove a conjecture by Brass: If a polygon P admits no approximation by a sub-k-gon (the convex hull of k vertices of P) with Hausdorff distance σ, but all subpolygons of P (the convex hull of some vertices of P) admit such an approximation, then P is a (k+1)-gon. This implies the following result: For any k > 2 and any convex polygon P of perimeter at most 1 there is a sub-k-gon Q of P such that the Hausdorff-distance of P and Q is at most 1/k+1 sin π/k+1.

Moving point object data can be analyzed through the discovery of patterns. We consider the computational efficiency of computing two of the most basic spatio-temporal patterns in trajectories, namely flocks and meetings. The patterns are large enough subgroups of the moving point objects that exhibit similar movement and proximity for a certain amount of time. We consider the problem of computing a longest duration flock or meeting. We give several exact and approximation algorithms, and also show that some variants are as hard as MaxClique to compute and approximate.

Given a Euclidean graph G in Rd with n vertices and m edges we consider the problem of adding a shortcut such that the stretch factor of the resulting graph is minimized. Currently, the fastest algorithm for computing the stretch factor of a Euclidean graph runs in O(mn+n2 log n) time, resulting in a trivial O(mn3+n4 log n) time algorithm for computing the optimal shortcut. First, we show that a simple modification yields the optimal solution in O(n4) time using O(n2) space. To reduce the running times we consider several approximation algorithms. Our main result is a (2+ε)-approximation algorithm with running time O(nm+n2(log n+1/ε3d)) using O(n2) space.

Abstract. We consider the problem of computing a minimum weight pseudo-triangulation of a set S of n points in the plane. We first present an O(n log n)-time algorithm that produces a pseudo-triangulation of weight O(wt(M(S)) · log n) which is shown to be asymptotically worstcase optimal, i.e., there exists a point set S for which every pseudotriangulation has weight Ω(log n · wt(M(S))), where wt(M(S)) is the weight of a minimum spanning tree of S. We also present a constant factor approximation algorithm running in cubic time. In the process we give an algorithm that produces a minimum weight pseudo-triangulation of a simple polygon. 1

A box-tree is a bounding-volume hierarchy that uses axis-aligned boxes as bounding volumes. We describe a new algorithm to construct a box-tree for objects in a 3D scene, and we analyze its worst-case query time for approximate range queries. If the input scene has certain characteristics that we derived from our application---collision detection in industrial installations---then the query times are polylogarithmic, not only for searching with boxes but also for range searching with other constant-complexity ranges.

Given a set V of n points in $\IR^d$ and a real constant t>1, we present the first O(nlog n)-time algorithm to compute a geometric t-spanner on V. A geometric t-spanner on V is a connected graph G = (V,E) with edge weights equal to the Euclidean distances between the endpoints, and with the property that, for all $u,v\in V$, the distance between u and v in G is at most t times the Euclidean distance between u and v. The spanner output by the algorithm has O(n) edges and weight $O(1)\cdot wt(MST)$, and its degree is bounded by a constant.

A box-tree is a \ifasci so-called \emph{bounding-volume hierarchy} \else bounding-volume hierarchy \fi that uses axis-aligned boxes as bounding volumes. The query complexity of a box-tree with respect to a given type of query is the maximum number of nodes visited when answering such a query. We describe several new algorithms for constructing box-trees with small worst-case query complexity with respect to queries with axis-parallel boxes and with points. We also prove lower bounds on the worst-case query complexity for box-trees, which show that our results are optimal or close to optimal. Finally, we present algorithms to convert box-trees to R-trees, resulting in R-trees with (almost) optimal query complexity.