Search

A classical problem in computational geometry and graph algorithms is: given a dynamic set S of geometric shapes in the plane, efficiently maintain the connectivity of the intersection graph of S. Previous papers studied the setting where, before the updates, the data structure receives some parameter P. Then, updates could insert and delete disks as long as at all times the disks have a diameter that lies in a fixed range [1/P, 1]. The state-of-the-art for storing disks in a dynamic connectivity data structure is a data structure that uses O(Pn) space and that has amortized O(P log^4 n) expected amortized update time. Connectivity queries between disks are supported in O( log n / loglog n) time. The state-of-the-art for Euclidean disks immediately implies a data structure for connectivity between axis-aligned squares that have their diameter in the fixed range [1/P, 1], with an improved update time of O(P log^4 n) amortized time. We restrict our attention to axis-aligned squares, and study fully-dynamic square intersection graph connectivity. Our result is fully-adaptive to the aspect ratio, spending time proportional to the current aspect ratio {\psi}, as opposed to some previously given maximum P. Our focus on squares allows us to simplify and streamline the connectivity pipeline from previous work. When $n$ is the number of squares and {\psi} is the aspect ratio after insertion (or before deletion), our data structure answers connectivity queries in O(log n / loglog n) time. We can update connectivity information in O({\psi} log^4 n + log^6 n) amortized time. We also improve space usage from O(P n log n) to O(n log^3 n log {\psi}) -- while generalizing to a fully-adaptive aspect ratio -- which yields a space usage that is near-linear in n for any polynomially bounded {\psi}., Comment: To appear at MFCS

Let $R \cup B$ be a set of $n$ points in $\mathbb{R}^2$, and let $k \in 1..n$. Our goal is to compute a line that "best" separates the "red" points $R$ from the "blue" points $B$ with at most $k$ outliers. We present an efficient semi-online dynamic data structure that can maintain whether such a separator exists. Furthermore, we present efficient exact and approximation algorithms that compute a linear separator that is guaranteed to misclassify at most $k$, points and minimizes the distance to the farthest outlier. Our exact algorithm runs in $O(nk + n \log n)$ time, and our $(1+\varepsilon)$-approximation algorithm runs in $O(\varepsilon^{-1/2}((n + k^2) \log n))$ time. Based on our $(1+\varepsilon)$-approximation algorithm we then also obtain a semi-online data structure to maintain such a separator efficiently., Comment: 43 pages, 32 figures

The Earth Mover's Distance is a popular similarity measure in several branches of computer science. It measures the minimum total edge length of a perfect matching between two point sets. The Earth Mover's Distance under Translation ($\mathrm{EMDuT}$) is a translation-invariant version thereof. It minimizes the Earth Mover's Distance over all translations of one point set. For $\mathrm{EMDuT}$ in $\mathbb{R}^1$, we present an $\widetilde{\mathcal{O}}(n^2)$-time algorithm. We also show that this algorithm is nearly optimal by presenting a matching conditional lower bound based on the Orthogonal Vectors Hypothesis. For $\mathrm{EMDuT}$ in $\mathbb{R}^d$, we present an $\widetilde{\mathcal{O}}(n^{2d+2})$-time algorithm for the $L_1$ and $L_\infty$ metric. We show that this dependence on $d$ is asymptotically tight, as an $n^{o(d)}$-time algorithm for $L_1$ or $L_\infty$ would contradict the Exponential Time Hypothesis (ETH). Prior to our work, only approximation algorithms were known for these problems., Comment: Full version of the paper "Fine-Grained Complexity of Earth Mover's Distance under Translation" accepted for SoCG 2024

A geometric $t$-spanner $\mathcal{G}$ on a set $S$ of $n$ point sites in a metric space $P$ is a subgraph of the complete graph on $S$ such that for every pair of sites $p,q$ the distance in $\mathcal{G}$ is a most $t$ times the distance $d(p,q)$ in $P$. We call a connection between two sites a \emph{link}. In some settings, such as when $P$ is a simple polygon with $m$ vertices and a link is a shortest path in $P$, links can consist of $\Theta (m)$ segments and thus have non-constant complexity. The spanner complexity is a measure of how compact a spanner is, which is equal to the sum of the complexities of all links in the spanner. In this paper, we study what happens if we are allowed to introduce $k$ Steiner points to reduce the spanner complexity. We study such Steiner spanners in simple polygons, polygonal domains, and edge-weighted trees. We show that Steiner points have only limited utility. For a spanner that uses $k$ Steiner points, we provide an $\Omega(mn^{1/(t+1)}/k^{1/(t+1)})$ lower bound on the worst-case complexity of any $(t-\varepsilon)$-spanner, for any constant $\varepsilon \in (0,1)$ and integer constant $t \geq 2$. Additionally, we show NP-hardness for the problem of deciding whether a set of sites in a polygonal domain admits a $3$-spanner with a given maximum complexity using $k$ Steiner points. On the positive side, for trees we show how to build a $2t$-spanner that uses $k$ Steiner points of complexity $O(mn^{1/t}/k^{1/t} + n \log (n/k))$, for any integer $t \geq 1$. We generalize this to forests, and use it to obtain a $2\sqrt{2}t$-spanner in a simple polygon with complexity $O(mn^{1/t}(\log k)^{1+1/t}/k^{1/t} + n\log^2 n)$. When a link can be any path between two sites, we show how to improve the spanning ratio to $(2k+\varepsilon)$, for any constant $\varepsilon \in (0,2k)$, and how to build a $6t$-spanner in a polygonal domain with the same complexity., Comment: 25 pages, 10 figures

In this paper, we consider the Weighted Region Problem. In the Weighted Region Problem, the length of a path is defined as the sum of the weights of the subpaths within each region, where the weight of a subpath is its Euclidean length multiplied by a weight $ \alpha \geq 0 $ depending on the region. We study a restricted version of the problem of determining shortest paths through a single weighted rectangular region. We prove that even this very restricted version of the problem is unsolvable within the Algebraic Computation Model over the Rational Numbers (ACMQ). On the positive side, we provide the equations for the shortest paths that are computable within the ACMQ. Additionally, we provide equations for the bisectors between regions of the Shortest Path Map for a source point on the boundary of (or inside) the rectangular region.

Given two sets $R$ and $B$ of $n$ points in the plane, we present efficient algorithms to find a two-line linear classifier that best separates the "red" points in $R$ from the "blue" points in $B$ and is robust to outliers. More precisely, we find a region $\mathcal{W}_B$ bounded by two lines, so either a halfplane, strip, wedge, or double wedge, containing (most of) the blue points $B$, and few red points. Our running times vary between optimal $O(n\log n)$ and around $O(n^3)$, depending on the type of region $\mathcal{W}_B$ and whether we wish to minimize only red outliers, only blue outliers, or both., Comment: 26 pages, 17 figures. Full version of article to be presented at ISAAC24

Any surface that is intrinsically polyhedral can be represented by a collection of simple polygons (fragments), glued along pairs of equally long oriented edges, where each fragment is endowed with the geodesic metric arising from its Euclidean metric. We refer to such a representation as a portalgon, and we call two portalgons equivalent if the surfaces they represent are isometric. We analyze the complexity of shortest paths in portalgons. We call a fragment happy if any shortest path on the portalgon visits it at most a constant number of times. A portalgon is happy if all of its fragments are happy. We present an efficient algorithm to compute shortest paths on happy portalgons. The number of times that a shortest path visits a fragment is unbounded in general. We contrast this by showing that the intrinsic Delaunay triangulation of any polyhedral surface corresponds to a happy portalgon. Since computing the intrinsic Delaunay triangulation may be inefficient, we provide an efficient algorithm to compute happy portalgons for a restricted class of portalgons., Comment: 34 pages. Full version of a paper to appear in a shorter form in the 39th International Symposium on Computational Geometry (SoCG 2023)

A geometric $t$-spanner for a set $S$ of $n$ point sites is an edge-weighted graph for which the (weighted) distance between any two sites $p,q \in S$ is at most $t$ times the original distance between $p$ and~$q$. We study geometric $t$-spanners for point sets in a constrained two-dimensional environment $P$. In such cases, the edges of the spanner may have non-constant complexity. Hence, we introduce a novel spanner property: the spanner complexity, that is, the total complexity of all edges in the spanner. Let $S$ be a set of $n$ point sites in a simple polygon $P$ with $m$ vertices. We present an algorithm to construct, for any fixed integer $k \geq 1$, a $2\sqrt{2}k$-spanner with complexity $O(mn^{1/k} + n\log^2 n)$ in $O(n\log^2n + m\log n + K)$ time, where $K$ denotes the output complexity. When we relax the restriction that the edges in the spanner are shortest paths, such that an edge in the spanner can be any path between two sites, we obtain for any constant $\varepsilon \in (0,2k)$ a relaxed geodesic $(2k + \varepsilon)$-spanner of the same complexity, where the constant is dependent on $\varepsilon$. When we consider sites in a polygonal domain $P$ with holes, we can construct a relaxed geodesic $6k$-spanner of complexity $O(mn^{1/k} + n\log^2 n)$ in $O((n+m)\log^2n\log m+ K)$ time. Additionally, for any constant $\varepsilon \in (0,1)$ and integer constant $t \geq 2$, we show a lower bound for the complexity of any $(t-\varepsilon)$-spanner of $\Omega(mn^{1/(t-1)} + n)$., Comment: 38 pages, 21 figures, a preliminary version appeared at SoCG 2023

We devise a data structure that can answer shortest path queries for two query points in a polygonal domain $P$ on $n$ vertices. For any $\varepsilon > 0$, the space complexity of the data structure is $O(n^{10+\varepsilon })$ and queries can be answered in $O(\log n)$ time. Alternatively, we can achieve a space complexity of $O(n^{9+\varepsilon })$ by relaxing the query time to $O(\log^2 n)$. This is the first improvement upon a conference paper by Chiang and Mitchell from 1999. They present a data structure with $O(n^{11})$ space complexity and $O(\log n)$ query time. Our main result can be extended to include a space-time trade-off. Specifically, we devise data structures with $O(n^{9+\varepsilon}/\hspace{1pt} \ell^{4 + O(\varepsilon )})$ space complexity and $O(\ell \log^2 n )$ query time, for any integer $1 \leq \ell \leq n$. Furthermore, we present improved data structures with $O(\log n)$ query time for the special case where we restrict one (or both) of the query points to lie on the boundary of $P$. When one of the query points is restricted to lie on the boundary, and the other query point is unrestricted, the space complexity becomes $O(n^{6+\varepsilon})$. When both query points are on the boundary, the space complexity is decreased further to $O(n^{4+\varepsilon })$, thereby improving an earlier result of Bae and Okamoto., Comment: 28 pages, 9 figures

Let $P$ be a set of $n$ colored points. We develop efficient data structures that store $P$ and can answer chromatic $k$-nearest neighbor ($k$-NN) queries. Such a query consists of a query point $q$ and a number $k$, and asks for the color that appears most frequently among the $k$ points in $P$ closest to $q$. Answering such queries efficiently is the key to obtain fast $k$-NN classifiers. Our main aim is to obtain query times that are independent of $k$ while using near-linear space. We show that this is possible using a combination of two data structures. The first data structure allow us to compute a region containing exactly the $k$-nearest neighbors of a query point $q$, and the second data structure can then report the most frequent color in such a region. This leads to linear space data structures with query times of $O(n^{1 / 2} \log n)$ for points in $\mathbb{R}^1$, and with query times varying between $O(n^{2/3}\log^{2/3} n)$ and $O(n^{5/6} {\rm polylog} n)$, depending on the distance measure used, for points in $\mathbb{R}^2$. Since these query times are still fairly large we also consider approximations. If we are allowed to report a color that appears at least $(1-\varepsilon)f^*$ times, where $f^*$ is the frequency of the most frequent color, we obtain a query time of $O(\log n + \log\log_{\frac{1}{1-\varepsilon}} n)$ in $\mathbb{R}^1$ and expected query times ranging between $\tilde{O}(n^{1/2}\varepsilon^{-3/2})$ and $\tilde{O}(n^{1/2}\varepsilon^{-5/2})$ in $\mathbb{R}^2$ using near-linear space (ignoring polylogarithmic factors)., Comment: 37 pages, 9 figures

We study the problem of constructing a data structure that can store a two-dimensional polygonal curve $P$, such that for any query segment $\overline{ab}$ one can efficiently compute the Fr\'{e}chet distance between $P$ and $\overline{ab}$. First we present a data structure of size $O(n \log n)$ that can compute the Fr\'{e}chet distance between $P$ and a horizontal query segment $\overline{ab}$ in $O(\log n)$ time, where $n$ is the number of vertices of $P$. In comparison to prior work, this significantly reduces the required space. We extend the type of queries allowed, as we allow a query to be a horizontal segment $\overline{ab}$ together with two points $s, t \in P$ (not necessarily vertices), and ask for the Fr\'{e}chet distance between $\overline{ab}$ and the curve of $P$ in between $s$ and $t$. Using $O(n\log^2n)$ storage, such queries take $O(\log^3 n)$ time, simplifying and significantly improving previous results. We then generalize our results to query segments of arbitrary orientation. We present an $O(nk^{3+\varepsilon}+n^2)$ size data structure, where $k \in [1..n]$ is a parameter the user can choose, and $\varepsilon > 0$ is an arbitrarily small constant, such that given any segment $\overline{ab}$ and two points $s, t \in P$ we can compute the Fr\'{e}chet distance between $\overline{ab}$ and the curve of $P$ in between $s$ and $t$ in $O((n/k)\log^2n+\log^4 n)$ time. This is the first result that allows efficient exact Fr\'{e}chet distance queries for arbitrarily oriented segments. We also present two applications of our data structure: we show that we can compute a local $\delta$-simplification (with respect to the Fr\'{e}chet distance) of a polygonal curve in $O(n^{5/2+\varepsilon})$ time, and that we can efficiently find a translation of an arbitrary query segment $\overline{ab}$ that minimizes the Fr\'{e}chet distance with respect to a subcurve of $P$.

Let $P$ be a simple polygon with $n$ vertices, and let $A$ be a set of $m$ points or line segments inside $P$. We develop data structures that can efficiently count the number of objects from $A$ that are visible to a query point or a query segment. Our main aim is to obtain fast, $O(\mathop{\textrm{polylog}} nm$), query times, while using as little space as possible. In case the query is a single point, a simple visibility-polygon-based solution achieves $O(\log nm)$ query time using $O(nm^2)$ space. In case $A$ also contains only points, we present a smaller, $O(n + m^{2 + \varepsilon}\log n)$-space, data structure based on a hierarchical decomposition of the polygon. Building on these results, we tackle the case where the query is a line segment and $A$ contains only points. The main complication here is that the segment may intersect multiple regions of the polygon decomposition, and that a point may see multiple such pieces. Despite these issues, we show how to achieve $O(\log n\log nm)$ query time using only $O(nm^{2 + \varepsilon} + n^2)$ space. Finally, we show that we can even handle the case where the objects in $A$ are segments with the same bounds., Comment: 27 pages, 13 figures

Our aim is to develop dynamic data structures that support $k$-nearest neighbors ($k$-NN) queries for a set of $n$ point sites in the plane in $O(f(n) + k)$ time, where $f(n)$ is some polylogarithmic function of $n$. The key component is a general query algorithm that allows us to find the $k$-NN spread over $t$ substructures simultaneously, thus reducing an $O(tk)$ term in the query time to $O(k)$. Combining this technique with the logarithmic method allows us to turn any static $k$-NN data structure into a data structure supporting both efficient insertions and queries. For the fully dynamic case, this technique allows us to recover the deterministic, worst-case, $O(\log^2n/\log\log n +k)$ query time for the Euclidean distance claimed before, while preserving the polylogarithmic update times. We adapt this data structure to also support fully dynamic \emph{geodesic} $k$-NN queries among a set of sites in a simple polygon. For this purpose, we design a shallow cutting based, deletion-only $k$-NN data structure. More generally, we obtain a dynamic planar $k$-NN data structure for any type of distance functions for which we can build vertical shallow cuttings. We apply all of our methods in the plane for the Euclidean distance, the geodesic distance, and general, constant-complexity, algebraic distance functions., Comment: 21 pages, 7 figures

Given two distributions $P$ and $S$ of equal total mass, the Earth Mover's Distance measures the cost of transforming one distribution into the other, where the cost of moving a unit of mass is equal to the distance over which it is moved. We give approximation algorithms for the Earth Mover's Distance between various sets of geometric objects. We give a $(1 + \varepsilon)$-approximation when $P$ is a set of weighted points and $S$ is a set of line segments, triangles or $d$-dimensional simplices. When $P$ and $S$ are both sets of line segments, sets of triangles or sets of simplices, we give a $(1 + \varepsilon)$-approximation with a small additive term. All algorithms run in time polynomial in the size of $P$ and $S$, and actually calculate the transport plan (that is, a specification of how to move the mass), rather than just the cost. To our knowledge, these are the first combinatorial algorithms with a provable approximation ratio for the Earth Mover's Distance when the objects are continuous rather than discrete points.

An important task in terrain analysis is computing \emph{viewsheds}. A viewshed is the union of all the parts of the terrain that are visible from a given viewpoint or set of viewpoints. The complexity of a viewshed can vary significantly depending on the terrain topography and the viewpoint position. In this work we study a new topographic attribute, the \emph{prickliness}, that measures the number of local maxima in a terrain from all possible angles of view. We show that the prickliness effectively captures the potential of 2.5D TIN terrains to have high complexity viewsheds. We present optimal (for 1.5D terrains) and near-optimal (for 2.5D terrains) algorithms to compute it for TIN terrains, and efficient approximate algorithms for raster DEMs. We validate the usefulness of the prickliness attribute with experiments in a large set of real terrains.

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

We study the geodesic Voronoi diagram of a set $S$ of $n$ linearly moving sites inside a static simple polygon $P$ with $m$ vertices. We identify all events where the structure of the Voronoi diagram changes, bound the number of such events, and then develop a kinetic data structure (KDS) that maintains the geodesic Voronoi diagram as the sites move. To this end, we first analyze how often a single bisector, defined by two sites, or a single Voronoi center, defined by three sites, can change. For both these structures we prove that the number of such changes is at most $O(m^3)$, and that this is tight in the worst case. Moreover, we develop compact, responsive, local, and efficient kinetic data structures for both structures. Our data structures use linear space and process a worst-case optimal number of events. Our bisector and Voronoi center kinetic data structures handle each event in $O(\log^2 m)$ time. Both structures can be extended to efficiently support updating the movement of the sites as well. Using these data structures as building blocks we obtain a compact KDS for maintaining the full geodesic Voronoi diagram.

We study continuous analogues of "vitality" for discrete network flows/paths, and consider problems related to placing segment barriers that have highest impact on a flow/path in a polygonal domain. This extends the graph-theoretic notion of "most vital arcs" for flows/paths to geometric environments. We give hardness results and efficient algorithms for various versions of the problem, (almost) completely separating hard and polynomially-solvable cases.

We consider the problem of testing, for a given set of planar regions $\cal R$ and an integer $k$, whether there exists a convex shape whose boundary intersects at least $k$ regions of $\cal R$. We provide a polynomial time algorithm for the case where the regions are disjoint line segments with a constant number of orientations. On the other hand, we show that the problem is NP-hard when the regions are intersecting axis-aligned rectangles or 3-oriented line segments. For several natural intermediate classes of shapes (arbitrary disjoint segments, intersecting 2-oriented segments) the problem remains open.

We present an efficient dynamic data structure that supports geodesic nearest neighbor queries for a set $S$ of point sites in a static simple polygon $P$. Our data structure allows us to insert a new site in $S$, delete a site from $S$, and ask for the site in $S$ closest to an arbitrary query point $q \in P$. All distances are measured using the geodesic distance, that is, the length of the shortest path that is completely contained in $P$. Our data structure achieves polylogarithmic update and query times, and uses $O(n\log^3n\log m + m)$ space, where $n$ is the number of sites in $S$ and $m$ is the number of vertices in $P$. The crucial ingredient in our data structure is an implicit representation of a vertical shallow cutting of the geodesic distance functions. We show that such an implicit representation exists, and that we can compute it efficiently., Comment: full version of our SoCG 2018 paper. arXiv admin note: substantial text overlap with arXiv:1707.02961

We study the problem of convexifying drawings of planar graphs. Given any planar straight-line drawing of an internally 3-connected graph, we show how to morph the drawing to one with strictly convex faces while maintaining planarity at all times. Our morph is convexity-increasing, meaning that once an angle is convex, it remains convex. We give an efficient algorithm that constructs such a morph as a composition of a linear number of steps where each step either moves vertices along horizontal lines or moves vertices along vertical lines. Moreover, we show that a linear number of steps is worst-case optimal. To obtain our result, we use a well-known technique by Hong and Nagamochi for finding redrawings with convex faces while preserving y-coordinates. Using a variant of Tutte's graph drawing algorithm, we obtain a new proof of Hong and Nagamochi's result which comes with a better running time. This is of independent interest, as Hong and Nagamochi's technique serves as a building block in existing morphing algorithms., Comment: Preliminary version in Proc. WG 2018

We present an efficient dynamic data structure that supports geodesic nearest neighbor queries for a set of point sites $S$ in a static simple polygon $P$. Our data structure allows us to insert a new site in $S$, delete a site from $S$, and ask for the site in $S$ closest to an arbitrary query point $q \in P$. All distances are measured using the geodesic distance, that is, the length of the shortest path that is completely contained in $P$. Our data structure supports queries in $O(\sqrt{n}\log n\log^2 m)$ time, where $n$ is the number of sites currently in $S$, and $m$ is the number of vertices of $P$, and updates in $O(\sqrt{n}\log^3 m)$ time. The space usage is $O(n\log m + m)$. If only insertions are allowed, we can support queries in worst-case $O(\log^2 n\log^2 m)$ time, while allowing for $O(\log n\log^3 m)$ amortized time insertions. We can achieve the same running times in case there are both insertions and deletions, but the order of these operations is known in advance.

We study an agglomerative clustering problem motivated by interactive glyphs in geo-visualization. Consider a set of disjoint square glyphs on an interactive map. When the user zooms out, the glyphs grow in size relative to the map, possibly with different speeds. When two glyphs intersect, we wish to replace them by a new glyph that captures the information of the intersecting glyphs. We present a fully dynamic kinetic data structure that maintains a set of $n$ disjoint growing squares. Our data structure uses $O(n (\log n \log\log n)^2)$ space, supports queries in worst case $O(\log^3 n)$ time, and updates in $O(\log^7 n)$ amortized time. This leads to an $O(n\alpha(n)\log^7 n)$ time algorithm to solve the agglomerative clustering problem. This is a significant improvement over the current best $O(n^2)$ time algorithms., Comment: 14 pages, 7 figures

Let P be a set of points in R^d, and let M be a function that maps any subset of P to a positive real number. We examine the problem of computing the exact mean and variance of M when a subset of points in P is selected according to a well-defined random distribution. We consider two distributions; in the first distribution (which we call the Bernoulli distribution), each point p in P is included in the random subset independently, with probability pi(p). In the second distribution (the fixed-size distribution), a subset of exactly s points is selected uniformly at random among all possible subsets of s points in P. This problem is a crucial part of modern ecological analyses; each point in P represents a species in d-dimensional trait space, and the goal is to compute the statistics of a geometric measure on this trait space, when subsets of species are selected under random processes. We present efficient exact algorithms for computing the mean and variance of several geometric measures when point sets are selected under one of the described random distributions. More specifically, we provide algorithms for the following measures: the bounding box volume, the convex hull volume, the mean pairwise distance (MPD), the squared Euclidean distance from the centroid, and the diameter of the minimum enclosing disk. We also describe an efficient (1-e)-approximation algorithm for computing the mean and variance of the mean pairwise distance. We implemented three of our algorithms and we show that our implementations can provide major speedups compared to the existing imprecise approaches.

We revisit the minimum-link path problem: Given a polyhedral domain and two points in it, connect the points by a polygonal path with minimum number of edges. We consider settings where the vertices and/or the edges of the path are restricted to lie on the boundary of the domain, or can be in its interior. Our results include bit complexity bounds, a novel general hardness construction, and a polynomial-time approximation scheme. We fully characterize the situation in 2D, and provide first results in dimensions 3 and higher for several variants of the problem. Concretely, our results resolve several open problems. We prove that computing the minimum-link diffuse reflection path, motivated by ray tracing in computer graphics, is NP-hard, even for two-dimensional polygonal domains with holes. This has remained an open problem [1] despite a large body of work on the topic. We also resolve the open problem from [2] mentioned in the handbook [3] (see Chapter 27.5, Open problem 3) and The Open Problems Project [4] (see Problem 22): "What is the complexity of the minimum-link path problem in 3-space?" Our results imply that the problem is NP-hard even on terrains (and hence, due to discreteness of the answer, there is no FPTAS unless P=NP), but admits a PTAS., Comment: An abridged version of this paper appeared in the proceedings of the 32nd International Symposium on Computational Geometry in 2016

We present algorithms and data structures that support the interactive analysis of the grouping structure of one-, two-, or higher-dimensional time-varying data while varying all defining parameters. Grouping structures characterise important patterns in the temporal evaluation of sets of time-varying data. We follow Buchin et al. [JoCG 2015] who define groups using three parameters: group-size, group-duration, and inter-entity distance. We give upper and lower bounds on the number of maximal groups over all parameter values, and show how to compute them efficiently. Furthermore, we describe data structures that can report changes in the set of maximal groups in an output-sensitive manner. Our results hold in $\mathbb{R}^d$ for fixed $d$., Comment: Full version of our SoCG 2016 paper

Point feature map labeling is a geometric problem, in which a set of input points must be labeled with a set of disjoint rectangles (the bounding boxes of the label texts). Typically, labeling models either use internal labels, which must touch their feature point, or external (boundary) labels, which are placed on one of the four sides of the input points' bounding box and which are connected to their feature points by crossing-free leader lines. In this paper we study polynomial-time algorithms for maximizing the number of internal labels in a mixed labeling model that combines internal and external labels. The model requires that all leaders are parallel to a given orientation $\theta \in [0,2\pi)$, whose value influences the geometric properties and hence the running times of our algorithms., Comment: Full version for the paper accepted at CIAC 2015

An important task in trajectory analysis is clustering. The results of a clustering are often summarized by a single representative trajectory and an associated size of each cluster. We study the problem of computing a suitable representative of a set of similar trajectories. To this end we define a central trajectory $\mathcal{C}$, which consists of pieces of the input trajectories, switches from one entity to another only if they are within a small distance of each other, and such that at any time $t$, the point $\mathcal{C}(t)$ is as central as possible. We measure centrality in terms of the radius of the smallest disk centered at $\mathcal{C}(t)$ enclosing all entities at time $t$, and discuss how the techniques can be adapted to other measures of centrality. We first study the problem in $\mathbb{R}^1$, where we show that an optimal central trajectory $\mathcal{C}$ representing $n$ trajectories, each consisting of $\tau$ edges, has complexity $\Theta(\tau n^2)$ and can be computed in $O(\tau n^2 \log n)$ time. We then consider trajectories in $\mathbb{R}^d$ with $d\geq 2$, and show that the complexity of $\mathcal{C}$ is at most $O(\tau n^{5/2})$ and can be computed in $O(\tau n^3)$ time., Comment: Full version

We study the problem of visibility in polyhedral terrains in the presence of multiple viewpoints. We consider a triangulated terrain with $m>1$ viewpoints (or guards) located on the terrain surface. A point on the terrain is considered \emph{visible} if it has an unobstructed line of sight to at least one viewpoint. We study several natural and fundamental visibility structures: (1) the visibility map, which is a partition of the terrain into visible and invisible regions; (2) the \emph{colored} visibility map, which is a partition of the terrain into regions whose points have exactly the same visible viewpoints; and (3) the Voronoi visibility map, which is a partition of the terrain into regions whose points have the same closest visible viewpoint. We study the complexity of each structure for both 1.5D and 2.5D terrains, and provide efficient algorithms to construct them. Our algorithm for the visibility map in 2.5D terrains improves on the only existing algorithm in this setting. To the best of our knowledge, the other structures have not been studied before., Comment: Manuscript accompanying shorter version in ISAAC 2013; some algorithms and bounds have improved with respect to the ISAAC version. The journal version will appear in IJCGA (without Section 4)

The collective motion of a set of moving entities like people, birds, or other animals, is characterized by groups arising, merging, splitting, and ending. Given the trajectories of these entities, we define and model a structure that captures all of such changes using the Reeb graph, a concept from topology. The trajectory grouping structure has three natural parameters that allow more global views of the data in group size, group duration, and entity inter-distance. We prove complexity bounds on the maximum number of maximal groups that can be present, and give algorithms to compute the grouping structure efficiently. We also study how the trajectory grouping structure can be made robust, that is, how brief interruptions of groups can be disregarded in the global structure, adding a notion of persistence to the structure. Furthermore, we showcase the results of experiments using data generated by the NetLogo flocking model and from the Starkey project. The Starkey data describe the movement of elk, deer, and cattle. Although there is no ground truth for the grouping structure in this data, the experiments show that the trajectory grouping structure is plausible and has the desired effects when changing the essential parameters. Our research provides the first complete study of trajectory group evolvement, including combinatorial, algorithmic, and experimental results.