Detecting location-correlated groups in point sets is an important task in a wide variety of applications areas. In addition to merely detecting such groups, the group's shape carries meaning as well. In this paper, we represent a group's shape using a simple geometric object, a line segment. Specifically, given a radius $r$, we say a line segment is representative of a point set $P$ if it is within distance $r$ of each point $p \in P$. We aim to find the shortest such line segment. This problem is equivalent to stabbing a set of circles of radius $r$ using the shortest line segment. We describe an algorithm to find the shortest representative segment in $O(n \log h + h \log^3 h)$ time. Additionally, we show how to maintain a stable approximation of the shortest representative segment when the points in $P$ move.

Abstract. We study the geodesic Voronoi diagram of a set [Formula: see text] of [Formula: see text] linearly moving sites inside a static simple polygon [Formula: see text] with [Formula: see text] 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 [Formula: see text], and that this is tight in the worst case. Moreover, we develop compact, responsive, local, and efficient KDSs for both structures. Our data structures use linear space and process a worst-case optimal number of events. Our bisector and Voronoi center KDSs handle each event in [Formula: see text] 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.

In this article, we study a wide range of variants for computing the (discrete and continuous) Fréchet distance between uncertain curves. An uncertain curve is a sequence of uncertainty regions, where each region is a disk, a line segment, or a set of points. A realisation of a curve is a polyline connecting one point from each region. Given an uncertain curve and a second (certain or uncertain) curve, we seek to compute the lower and upper bound Fréchet distance, which are the minimum and maximum Fréchet distance for any realisations of the curves. We prove that both problems are NP-hard for the Fréchet distance in several uncertainty models, and that the upper bound problem remains hard for the discrete Fréchet distance. In contrast, the lower bound (discrete [ 5 ] and continuous) Fréchet distance can be computed in polynomial time in some models. Furthermore, we show that computing the expected (discrete and continuous) Fréchet distance is #P-hard in some models. On the positive side, we present an FPTAS in constant dimension for the lower bound problem when Δ/δ is polynomially bounded, where δ is the Fréchet distance and Δ bounds the diameter of the regions. We also show a near-linear-time 3-approximation for the decision problem on roughly δ-separated convex regions. Finally, we study the setting with Sakoe–Chiba time bands, where we restrict the alignment between the curves, and give polynomial-time algorithms for the upper bound and expected discrete and continuous Fréchet distance for uncertainty modelled as point sets.

An important data source for traffic analysis is GPS trajectory data. However, due to measurement inaccuracies, such data does not necessarily align well with data describing the road network. Hence, GPS data typically needs to be aligned with the road network before further analysis can take place; this process is called map matching. The challenges in map matching are exacerbated when trajectories are sparse (have a low measurement frequency); we then need to fill the gaps between the measurements with a realistic estimate of the actual route between two points. As vehicle movement is subject to physical constraints (such as acceleration and speed bounds), an estimated route should be physically consistent. We present a method that creates physically consistent estimated routes to perform map matching for sparse trajectories.

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 objects from A that are visible to a query point or a query segment. Our main aim is to obtain fast, O(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²) space. In case A also contains only points, we present a smaller, O(n + m^{2+ε} 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+ε} + n²) space. Finally, we show that we can even handle the case where the objects in A are segments with the same bounds.

We study the problem of polygonal curve simplification under uncertainty, where instead of a sequence of exact points, each uncertain point is represented by a region which contains the (unknown) true location of the vertex. The regions we consider are disks, line segments, convex polygons, and discrete sets of points. We are interested in finding the shortest subsequence of uncertain points such that no matter what the true location of each uncertain point is, the resulting polygonal curve is a valid simplification of the original polygonal curve under the Hausdorff or the Fréchet distance. For both these distance measures, we present polynomial-time algorithms for this problem.

We study the computation of the diameter and radius under the rectilinear link distance within a rectilinear polygonal domain of n vertices and h holes. We introduce a graph of oriented distances to encode the distance between pairs of points of the domain. This helps us transform the problem so that we can search through the candidates more efficiently. Our algorithm computes both the diameter and the radius in O ( min ⁡ ( n ω , n 2 + n h log ⁡ h + χ 2 ) ) time, where ω < 2.373 denotes the matrix multiplication exponent and χ ∈ Ω ( n ) ∩ O ( n 2 ) is the number of edges of the graph of oriented distances. We also provide an alternative algorithm for computing the diameter that runs in O ( n 2 log ⁡ n ) time.

In this paper we study a wide range of variants for computing the (discrete and continuous) Fréchet distance between uncertain curves. We define an uncertain curve as a sequence of uncertainty regions, where each region is a disk, a line segment, or a set of points. A realisation of a curve is a polyline connecting one point from each region. Given an uncertain curve and a second (certain or uncertain) curve, we seek to compute the lower and upper bound Fréchet distance, which are the minimum and maximum Fréchet distance for any realisations of the curves. We prove that both problems are NP-hard for the continuous Fréchet distance, and the upper bound problem remains hard for the discrete Fréchet distance. In contrast, the lower bound discrete Fréchet distance can be computed in polynomial time using dynamic programming. Furthermore, we show that computing the expected discrete or continuous Fréchet distance is #P-hard when the uncertainty regions are modelled as point sets or line segments. On the positive side, we argue that in any constant dimension there is a FPTAS for the lower bound problem when Δ/δ is polynomially bounded, where δ is the Fréchet distance and Δ bounds the diameter of the regions. We then argue there is a near-linear-time 3-approximation for the decision problem when the regions are convex and roughly δ-separated. Finally, we study the setting with Sakoe–Chiba bands, restricting the alignment of the two curves, and give polynomial-time algorithms for upper bound and expected (discrete) Fréchet distance for point-set-modelled uncertainty regions.

We consider the problem of routing a data packet through the visibility graph of a polygonal domain P with n vertices and h holes. We may preprocess P to obtain a label and a routing table for each vertex. Then, we must be able to route a data packet between any two vertices p and q of P , where each step must use only the label of the target node q and the routing table of the current node. For any fixed eps > 0, we pre ent a routing scheme that always achieves a routing path that exceeds the shortest path by a factor of at most 1 + eps. The labels have O(log n) bits, and the routing tables are of size O((eps^{-1} + h) log n). The preprocessing time is O(n^2 log n + hn^2 + eps^{-1}hn). It can be improved to O(n 2 + eps^{-1}n) for simple polygons.

We present a new algorithm for the widely used density-based clustering method DBScan. Our algorithm computes the DBScan-clustering in O(n log n) time in R^2, irrespective of the scale parameter \eps, but assuming the second parameter MinPts is set to a fixed constant, as is the case in practice. We also present an O(n log n) randomized algorithm for HDBScan in the plane---HDBScans is a hierarchical version of DBScan introduced recently---and we show how to compute an approximate version of HDBScan in near-linear time in any fixed dimension.

We introduce the dynamic conflict-free coloring problem for a set S of intervals in R 1 with respect to points, where the goal is to maintain a conflict-free coloring for S under insertions and deletions. We investigate trade-offs between the number of colors used and the number of intervals that are recolored upon insertion or deletion of an interval. Our results include: - a lower bound on the number of recolorings as a function of the number of colors, which implies that with O(1) recolorings per update the worst-case number of colors is Ω(logn/loglogn) , and that any strategy using O(1/ε) colors needs Ω(εn ε ) recolorings; - a coloring strategy that uses O(logn) colors at the cost of O(logn) recolorings, and another strategy that uses O(1/ε) colors at the cost of O(n ε /ε) recolorings; - stronger upper and lower bounds for special cases. We also consider the kinetic setting where the intervals move continuously (but there are no insertions or deletions); here we show how to maintain a coloring with only four colors at the cost of three recolorings per event and show this is tight.

In this paper we study the number of vertex recolorings that an algorithm needs to perform in order to maintain a proper coloring of a graph under insertion and deletion of vertices and edges. We present two algorithms that achieve different trade-offs between the number of recolorings and the number of colors used. For any $$d>0$$ , the first algorithm maintains a proper $$O(\mathcal {C} dN ^{1/d})$$ -coloring while recoloring at most O(d) vertices per update, where $$\mathcal {C} $$ and $$N $$ are the maximum chromatic number and maximum number of vertices, respectively. The second algorithm reverses the trade-off, maintaining an $$O(\mathcal {C} d)$$ -coloring with $$O(dN ^{1/d})$$ recolorings per update. We also present a lower bound, showing that any algorithm that maintains a c-coloring of a 2-colorable graph on $$N $$ vertices must recolor at least $$\varOmega (N ^\frac{2}{c(c-1)})$$ vertices per update, for any constant $$c \ge 2$$ .

We show that for any set of n moving points in R^d and any parameter 2<=k

We study two versions of the 2-center problem for moving points in the plane. Given a set P of n points, the Euclidean 2-center problem asks for two congruent disks of minimum size that together cover P; the rectilinear 2-center problem correspondingly asks for two congruent axis-aligned squares of minimum size that together cover P. Our methods work in the black-box KDS model, where we receive the locations of the points at regular time steps and we know an upper bound d_{max} on the maximum displacement of any point within one time step. We show how to maintain the rectilinear 2-center in amortized sub-linear time per time step, under certain assumptions on the distribution of the point set P. For the Euclidean 2-center we give a similar result: we can maintain in amortized sub-linear time (again under certain assumptions on the distribution) a (1+ε)-approximation of the optimal 2-center. In many cases---namely when the distance between the centers of the disks is relatively large or relatively small---the solution we maintain is actually optimal.

Over the past decade, the kinetic-data-structures framework has become the standard in computational geometry for dealing with moving objects. A fundamental assumption underlying the framework is that the motions of the objects are known in advance. This assumption severely limits the applicability of KDSs. We study KDSs in the black-box model, which is a hybrid of the KDS model and the traditional time-slicing approach. In this more practical model we receive the position of each object at regular time steps and we have an upper bound on dmax, the maximum displacement of any point in one time step. We study the maintenance of the convex hull and the Delaunay triangulation of a planar point set P in the black-box model, under the following assumption on dmax: there is some constant k such that for any point p ∑ P the disk of radius dmax contains at most k points. We analyze our algorithms in terms of ∑k , the so-called k-spread of P. We show how to update the convex hull at each time step in O(k∑k log2 n) amortized time. For the Delaunay triangulation our main contribution is an analysis of the standard edge-flipping approach; we show that the number of flips is O(k2 ∑k2) at each time step.