Search

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. In this paper, we develop two fundamental tools for low density graphs, that is, a well-separated pair decomposition and an approximate distance oracle. We believe that by expanding the algorithmic toolbox for low density graphs, we can help provide a useful and realistic graph class for road networks, which in turn, may help explain the many efficient and practical heuristics available for road networks.

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\'echet 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\'echet distance between all graph paths and a polygonal curve. Recently, Gudmundsson, Seybold, and Wong [SODA 2023, arXiv:2211.02951] studied this problem for arbitrary query polygonal curves and $c$-packed graphs. In this paper, we instead require the graphs to be $\lambda$-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., Comment: This is an extended version of the article published in SoCG 2024, doi:10.4230/LIPIcs.SoCG.2024.27. 15 pages, 4 figures

One approach to studying the Fr\'echet 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\'echet 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+\varepsilon)$-approximates the Fr\'echet distance between a $c$-packed curve and a general curve in $\mathbb R^d$, for constant values of $\varepsilon$, $d$ and $c$., Comment: To appear in ISAAC 2024

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 \sqrt[r]{2} \ k^{1/r},2r)$-bicriteria approximation that runs in $O(n^3 \log n)$ time, for all $r \geq 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\H{o}s girth conjecture., Comment: To appear in ESA 2024

We consider the problem of computing an approximate weighted shortest path in a weighted subdivision, with weights assigned from the set $\{0, 1, \infty\}$. We present a data structure $B$, which stores a set of convex, non-overlapping regions. These include zero-cost regions (0-regions) with a weight of $0$ and obstacles with a weight of $\infty$, all embedded in a plane with a weight of $1$. The data structure $B$ can be constructed in expected time $O(N + (n/\varepsilon^3)(\log(n/\varepsilon) + \log N))$, where $n$ is the total number of regions, $N$ represents the total complexity of the regions, and $1 + \varepsilon$ is the approximation factor, for any $0 < \varepsilon < 1$. Using $B$, one can compute an approximate weighted shortest path from any point $s$ to any point $t$ in $O(N + n/\varepsilon^3 + (n/\varepsilon^2) \log(n/\varepsilon) + (\log N)/\varepsilon)$ time. In the special case where the 0-regions and obstacles are polygons (not necessarily convex), $B$ contains a $(1 + \varepsilon)$-spanner of the input vertices.

Given a set of $n$ point robots inside a simple polygon $P$, the task is to move the robots from their starting positions to their target positions along their shortest paths, while the mutual visibility of these robots is preserved. Previous work only considered two robots. In this paper, we present an $O(mn)$ time algorithm, where $m$ is the complexity of the polygon, when all the starting positions lie on a line segment $S$, all the target positions lie on a line segment $T$, and $S$ and $T$ do not intersect. We also argue that there is no polynomial-time algorithm, whose running time depends only on $n$ and $m$, that uses a single strategy for the case where $S$ and $T$ intersect.

Given a set of $n\geq 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, where $q>0$ is related to leader election, which takes $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., Comment: arXiv admin note: text overlap with arXiv:2306.14440

We present a near-linear time approximation algorithm for the subtrajectory cluster problem of $c$-packed trajectories. The problem involves finding $m$ subtrajectories within a given trajectory $T$ such that their Fr\'echet distances are at most $(1 + \varepsilon)d$, and 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 \cdot r$ in length. Previous results by Gudmundsson and Wong \cite{GudmundssonWong2022Cubicupperlower} established an $\Omega(n^3)$ lower bound unless the Strong Exponential Time Hypothesis fails, and they presented an $O(n^3 \log^2 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^2 n/\varepsilon^2)\log(c/\varepsilon)\log(n/\varepsilon))$ time complexity.

Given a point set $P$ in the Euclidean plane and a parameter $t$, we define an \emph{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 $O(n^7)$ time for $n$ points, and a greedy algorithm that computes a $5$-spanner in $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=19 \cdot t_g$, where $t_g$ is a upper bound on the dilation of the greedy triangulation., Comment: conference version: ESA '23

Given a set of $n\geq 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 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 [K. Bose, R. Adhikary, M. K. Kundu, and B. Sau. Arbitrary pattern formation by opaque fat robots with lights. CALDAM, pages 347-359, 2020]. In this work, we reduce the number of colors needed and remove the axis-agreement requirement. 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)$ rounds plus the time needed for the robots to elect a leader.

The use of realistic input models has gained popularity in the theory community. Assuming a realistic input model often precludes complicated hypothetical inputs, and the analysis yields bounds that better reflect the behaviour of algorithms in practice. One of the most popular models for polygonal curves and line segments is $\lambda$-low-density. To select the most efficient algorithm for a certain input, one often needs to compute the $\lambda$-low-density value, or at least an approximate value. In this paper, we show that given a set of $n$ line segments in $\mathbb{R}^2$ one can compute a $3$-approximation of the $\lambda$-low density value in $O(n \log n + \lambda n)$ time. We also show how to maintain a $3$-approximation of the $\lambda$-low density value while allowing insertions of new segments in $O(\log n + \lambda^2)$ amortized time per update. Finally, we argue that many real-world data sets have a small $\lambda$-low density value, warranting the recent development of specialised algorithms. This is done by computing approximate $\lambda$-low density values for $12$ real-world data sets.

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\'echet distance. A shortcoming of existing map matching algorithms under the Fr\'echet 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\'echet 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-\delta})$ query time for any $\delta > 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 $\tilde O(cp)$ size that can answer $(1+\varepsilon)$-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 $\varepsilon$., Comment: Journal version, to appear in TALG 2024

Given a set of $n \geq 1$ unit disk robots in the Euclidean plane, we consider the fundamental problem of providing mutual visibility to them: the robots must reposition themselves to reach a configuration where they all see each other. 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 them. This problem was solved by Sharma et al. [G. Sharma, R. Alsaedi, C. Busch, and S. Mukhopadhyay. The complete visibility problem for fat robots with lights. In Proceedings of the 19th International Conference on Distributed Computing and Networking, pages 1-4, 2018.] in the luminous robots model, where each robot is equipped with an externally visible light that can assume colors from a fixed set of colors, using 9 colors and $O(n)$ rounds. In this work, we present an algorithm that requires only 2 colors and $O(n)$ rounds. The number of colors is optimal since at least two colors are required for point robots [G.A. Di Luna, P. Flocchini, S.G. Chaudhuri, F. Poloni, N. Santoro, and G. Viglietta. Mutual visibility by luminous robots without collisions. Information and Computation, 254:392-418, 2017.].

Let $L$ be a set of $n$ axis-parallel lines in $\mathbb{R}^3$. We are are interested in partitions of $\mathbb{R}^3$ by a set $H$ of three planes such that each open cell in the arrangement $\mathcal{A}(H)$ is intersected by as few lines from $L$ as possible. We study such partitions in three settings, depending on the type of splitting planes that we allow. We obtain the following results. $\bullet$ There are sets $L$ of $n$ axis-parallel lines such that, for any set $H$ of three splitting planes, there is an open cell in $\mathcal{A}(H)$ that intersects at least~$\lfloor n/3 \rfloor-1 \approx \frac{1}{3}n$ lines. $\bullet$ If we require the splitting planes to be axis-parallel, then there are sets $L$ of $n$ axis-parallel lines such that, for any set $H$ of three splitting planes, there is an open cell in $\mathcal{A}(H)$ that intersects at least $\frac{3}{2}\lfloor n/4 \rfloor -1 \approx \left( \frac{1}{3}+\frac{1}{24}\right) n$ lines. Furthermore, for any set $L$ of $n$ axis-parallel lines, there exists a set $H$ of three axis-parallel splitting planes such that each open cell in $\mathcal{A}(H)$ intersects at most $\frac{7}{18} n = \left( \frac{1}{3}+\frac{1}{18}\right) n$ lines. $\bullet$ For any set $L$ of $n$ axis-parallel lines, there exists a set $H$ of three axis-parallel and mutually orthogonal splitting planes, such that each open cell in $\mathcal{A}(H)$ intersects at most $\lceil \frac{5}{12} n \rceil \approx \left( \frac{1}{3}+\frac{1}{12}\right) n$ lines., Comment: 21 pages, minor changes, accepted to Computing in Geometry and Topology

We study the problem of sub-trajectory nearest-neighbor queries on polygonal curves under the continuous Fr\'echet distance. Given an $n$ vertex trajectory $P$ and an $m$ vertex 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$. Since in real data $P$ typically contains a very large number of vertices, we focus on answering queries, without restrictions on $P$ or $Q$, using only precomputed structures of ${\mathcal{O}}(n)$ size. We use three baseline algorithms from straightforward extensions of known work, however they have impractical performance on realistic inputs. Therefore, we propose a new Hierarchical Simplification Tree data structure and an adaptive clustering based query algorithm that efficiently explores relevant parts of $P$. The core of our query methods is a novel greedy-backtracking algorithm that solves the Fr\'echet decision problem using ${\cal O}(n+m)$ space and ${\cal O}(nm)$ time in the worst case. Experiments on real and synthetic data show that our heuristic effectively prunes the search space and greatly reduces computations compared to baseline approaches., Comment: Added journal reference

Recent advances in tracking sensors and pose estimation software enable smart systems to use trajectories of skeleton joint locations for supervised learning. We study the problem of accurately recognizing sign language words, which is key to narrowing the communication gap between hard and non-hard of hearing people. Our method explores a geometric feature space that we call `sub-skeleton' aspects of movement. We assess similarity of feature space trajectories using natural, speed invariant distance measures, which enables clear and insightful nearest neighbor classification. The simplicity and scalability of our basic method allows for immediate application in different data domains with little to no parameter tuning. We demonstrate the effectiveness of our basic method, and a boosted variation, with experiments on data from different application domains and tracking technologies. Surprisingly, our simple methods improve sign recognition over recent, state-of-the-art approaches., Comment: To appear in Proc. of the 27th International Conference on Database Systems for Advanced Applications (DASFAA-2022)

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 $\Theta(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., Comment: In SoCG'24

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\'echet 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., Comment: To appear in SODA 2022

The Fr\'echet distance is a popular similarity measure between curves. For some applications, it is desirable to match the curves under translation before computing the Fr\'echet distance between them. This variant is called the Translation Invariant Fr\'echet distance, and algorithms to compute it are well studied. The query version, finding an optimal placement in the plane for a query segment where the Fr\'echet distance becomes minimized, is much less well understood. We study Translation Invariant Fr\'echet distance queries in a restricted setting of horizontal query segments. More specifically, we preprocess a trajectory in $\mathcal O(n^2 \log^2 n) $ time and $\mathcal O(n^{3/2})$ space, such that for any subtrajectory and any horizontal query segment we can compute their Translation Invariant Fr\'echet distance in $\mathcal O(\text{polylog } n)$ time. We hope this will be a step towards answering Translation Invariant Fr\'echet queries between arbitrary trajectories.

We study three covering problems in the plane. Our original motivation for these problems come from trajectory analysis. The first is to decide whether a given set of line segments can be covered by up to four unit-sized, axis-parallel squares. 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. 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., Comment: Journal Version, TCS 2022

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 ${\cal O}(n \log n)$ expected time for structures of ${\cal O}(n)$ expected size. Moreover, searching takes w.h.p. ${\cal O}(\log n)$ comparisons in the first and w.h.p. ${\cal O}(\log^2 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 ${\cal O}(n)$, ii) a depth of ${\cal O}(\log n)$, and iii) a construction time of ${\cal O}(n \log n)$. One application of these new and improved results are \emph{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]., Comment: New high probability bound in Section 4.1; Further applications in Section 5

Solomon and Elkin constructed a shortcutting scheme for weighted trees which results in a 1-spanner for the tree metric induced by the input tree. The spanner has logarithmic lightness, logarithmic diameter, a linear number of edges and bounded degree (provided the input tree has bounded degree). This spanner has been applied in a series of papers devoted to designing bounded degree, low-diameter, low-weight $(1+\epsilon)$-spanners in Euclidean and doubling metrics. In this paper, we present a simple local routing algorithm for this tree metric spanner. The algorithm has a routing ratio of 1, is guaranteed to terminate after $O(\log n)$ hops and requires $O(\Delta \log n)$ bits of storage per vertex where $\Delta$ is the maximum degree of the tree on which the spanner is constructed. This local routing algorithm can be adapted to a local routing algorithm for a doubling metric spanner which makes use of the shortcutting scheme.

In 2012 Driemel et al. \cite{DBLP:journals/dcg/DriemelHW12} 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+\varepsilon)$-approximation algorithm for computing the Fr\'echet 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 $\mathbb{R}^d$ is $c$-packed. We present two approximation algorithms. The first algorithm is a $2$-approximation algorithm and runs in $O(dn^2 \log n)$ time. In the case $d=2$ we develop a faster algorithm that returns a $(6+\varepsilon)$-approximation and runs in $O((n/\varepsilon^3)^{4/3} polylog (n/\varepsilon)))$ 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., Comment: A preliminary version to appear in ISAAC 2020

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., Comment: Journal version, TALG 2022

We present a scalable approach for range and $k$ nearest neighbor queries under computationally expensive metrics, like the continuous Fr\'echet distance on trajectory data. Based on clustering for metric indexes, we obtain a dynamic tree structure whose size is linear in the number of trajectories, regardless of the trajectory's individual sizes or the spatial dimension, which allows one to exploit low `intrinsic dimensionality' of data sets for effective search space pruning. Since the distance computation is expensive, generic metric indexing methods are rendered impractical. We present strategies that (i) improve on known upper and lower bound computations, (ii) build cluster trees without any or very few distance calls, and (iii) search using bounds for metric pruning, interval orderings for reduction, and randomized pivoting for reporting the final results. We analyze the efficiency and effectiveness of our methods with extensive experiments on diverse synthetic and real-world data sets. The results show improvement over state-of-the-art methods for exact queries, and even further speed-ups are achieved for queries that may return approximate results. Surprisingly, the majority of exact nearest-neighbor queries on real data sets are answered without any distance computations.

Let $V$ be a set of $n$ points in $\mathbb{R}^d$, called voters. A point $p\in \mathbb{R}^d$ is a plurality point for $V$ when the following holds: for every $q\in\mathbb{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\in 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 $\beta$-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 $\beta$, for some constant $0<\beta\leq 1$. We investigate the existence and computation of $\beta$-plurality points, and obtain the following. * Define $\beta^*_d := \sup \{ \beta : \text{any finite multiset $V$ in $\mathbb{R}^d$ admits a $\beta$-plurality point} \}$. We prove that $\beta^*_2 = \sqrt{3}/2$, and that $1/\sqrt{d} \leq \beta^*_d \leq \sqrt{3}/2$ for all $d\geq 3$. * Define $\beta(p, V) := \sup \{ \beta : \text{$p$ is a $\beta$-plurality point for $V$}\}$. Given a voter set $V \in \mathbb{R}^2$, we provide an algorithm that runs in $O(n \log n)$ time and computes a point $p$ such that $\beta(p, V) \geq \beta^*_2$. Moreover, for $d\geq 2$ we can compute a point $p$ with $\beta(p,V) \geq 1/\sqrt{d}$ in $O(n)$ time. * Define $\beta(V) := \sup \{ \beta : \text{$V$ admits a $\beta$-plurality point}\}$. We present an algorithm that, given a voter set $V$ in $\mathbb{R}^d$, computes an $(1-\varepsilon)\cdot \beta(V)$ plurality point in time $O(\frac{n^2}{\varepsilon^{3d-2}} \cdot \log \frac{n}{\varepsilon^{d-1}} \cdot \log^2 \frac {1}{\varepsilon})$., Comment: 21 pages, 10 figures, SoCG'20

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 [Online routing in triangulations. SIAM Journal on Computing, 33(4):937-951, 2004] showed that there exists an online routing algorithm that is $O(1)$-competitive. However, a Delaunay triangulation can have $\Omega(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.

The yolk is an important concept in spatial voting games as it generalises the equilibrium and provides bounds on the uncovered set. We present near-linear time algorithms for computing the yolk in the spatial voting model in the plane. To the best of our knowledge our algorithm is the first algorithm that does not require precomputing the median lines and hence able to break the existing $O(n^{4/3})$ bound which equals the known upper bound on the number of median lines. We avoid this requirement by using Megiddo's parametric search, which is a powerful framework that could lead to faster algorithms for many other spatial voting problems.

The Euclidean $k$-center problem is a classical problem that has been extensively studied in computer science. Given a set $\mathcal{G}$ of $n$ points in Euclidean space, the problem is to determine a set $\mathcal{C}$ of $k$ centers (not necessarily part of $\mathcal{G}$) such that the maximum distance between a point in $\mathcal{G}$ and its nearest neighbor in $\mathcal{C}$ is minimized. In this paper we study the corresponding $(k,\ell)$-center problem for polygonal curves under the Fr\'echet distance, that is, given a set $\mathcal{G}$ of $n$ polygonal curves in $\mathbb{R}^d$, each of complexity $m$, determine a set $\mathcal{C}$ of $k$ polygonal curves in $\mathbb{R}^d$, each of complexity $\ell$, such that the maximum Fr\'echet distance of a curve in $\mathcal{G}$ to its closest curve in $\mathcal{C}$ is minimized. In this paper, we substantially extend and improve the known approximation bounds for curves in dimension $2$ and higher. We show that, if $\ell$ is part of the input, then there is no polynomial-time approximation scheme unless $\mathsf{P}=\mathsf{NP}$. Our constructions yield different bounds for one and two-dimensional curves and the discrete and continuous Fr\'echet distance. In the case of the discrete Fr\'echet 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 $\mathsf{NP}$-hardness extends to the case that $\ell=\infty$, i.e., for the problem of computing the minimum-enclosing ball under the Fr\'echet 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., Comment: 24 pages; results on minimum-enclosing ball added, additional author added, general revision

Computing the Fr\'echet distance between two polygonal curves takes roughly quadratic time. In this paper, we show that for a special class of curves the Fr\'echet distance computations become easier. Let $P$ and $Q$ be two polygonal curves in $\mathbb{R}^d$ with $n$ and $m$ vertices, respectively. We prove four results for the case when all edges of both curves are long compared to the Fr\'echet distance between them: (1) a linear-time algorithm for deciding the Fr\'echet distance between two curves, (2) an algorithm that computes the Fr\'echet distance in $O((n+m)\log (n+m))$ time, (3) a linear-time $\sqrt{d}$-approximation algorithm, and (4) a data structure that supports $O(m\log^2 n)$-time decision queries, where $m$ is the number of vertices of the query curve and $n$ the number of vertices of the preprocessed curve.

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-\varepsilon}$-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+\varepsilon)\rho+2/\varepsilon)$-approximation can be computed in $O(n^3/\varepsilon^2)$ time and we prove fixed-parameter tractability when parameterized by the total movement assuming all numbers in the input are integers.

Estimating output changes by input changes is the main task in causal analysis. In previous work, input and output Self-Organizing Maps (SOMs) were associated for causal analysis of multivariate and nonlinear data. Based on the association, a weight distribution of the output conditional on a given input was obtained over the output map space. Such a weighted SOM pattern of the output changes when the input changes. In order to analyze the change, it is important to measure the difference of the patterns. Many methods have been proposed for the dissimilarity measure of patterns. However, it remains a major challenge when attempting to measure how the patterns change. In this paper, we propose a visualization approach that simplifies the comparison of the difference in terms of the pattern property. Using this approach, the change can be analyzed by integrating colors and star glyph shapes representing the property dissimilarity. Ecological data is used to demonstrate the usefulness of our approach and the experimental results show that our approach provides the change information effectively., Comment: 8 pages, 3 figures, conference, llncs style

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., Comment: A shorter version appears in Proceedings of ISAAC 2017

Let $C$ be the unit circle in $\mathbb{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\geq 1$ \emph{shortcuts} on $C$ such that the diameter of the resulting graph is minimized. We analyze for each $k$ with $1\leq k\leq 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^{\frac{2}{3}})$ for any~$k$., Comment: An extended abstract appeared in ISAAC 2017

We consider the problem of augmenting an n-vertex graph embedded in a metric space, by inserting one additional edge in order to minimize the diameter of the resulting graph. We present exact algorithms for the cases when (i) the input graph is a path, running in O(n \log^3 n) time, and (ii) the input graph is a tree, running in O(n^2 \log n) time. We also present an algorithm that computes a (1+\eps)-approximation in O(n + 1/\eps^3) time, for paths in R^d, where d is a constant.

Team-based invasion sports such as football, basketball and hockey are similar in the sense that the players are able to move freely around the playing area; and that player and team performance cannot be fully analysed without considering the movements and interactions of all players as a group. State of the art object tracking systems now produce spatio-temporal traces of player trajectories with high definition and high frequency, and this, in turn, has facilitated a variety of research efforts, across many disciplines, to extract insight from the trajectories. We survey recent research efforts that use spatio-temporal data from team sports as input, and involve non-trivial computation. This article categorises the research efforts in a coherent framework and identifies a number of open research questions., Comment: 42 pages, 11 figures

We introduce the concept of compactly representing a large number of state sequences, e.g., sequences of activities, as a flow diagram. We argue that the flow diagram representation gives an intuitive summary that allows the user to detect patterns among large sets of state sequences. Simplified, our aim is to generate a small flow diagram that models the flow of states of all the state sequences given as input. For a small number of state sequences we present efficient algorithms to compute a minimal flow diagram. For a large number of state sequences we show that it is unlikely that efficient algorithms exist. More specifically, the problem is W[1]-hard if the number of state sequences is taken as a parameter. We thus introduce several heuristics for this problem. We argue about the usefulness of the flow diagram by applying the algorithms to two problems in sports analysis. We evaluate the performance of our algorithms on a football data set and generated data., Comment: 18 pages, 8 figures