Search

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 (t k) 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 2 ⁡ n / 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 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. • A general query algorithm to find the k -NN spread over t substructures simultaneously. • A fully dynamic k -NN data structure with O (f (n) + k) query time. • An efficient insertion-only k -NN data structure for any distance metric with an efficient static k -NN data structure. [ABSTRACT FROM AUTHOR]

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 ∈ 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 ≥ 1, a 2 √ 2k-spanner with complexity O(mn1/k + n log²n) in O(n log²n + 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 ε ∈ (0, 2k) a relaxed geodesic (2k +ε)-spanner of the same complexity, where the constant is dependent on ε. When we consider sites in a polygonal domain P with holes, we can construct a relaxed geodesic 6k-spanner of complexity O(mn1/k + n log² n) in O((n + m) log²n log m + K) time. Additionally, for any constant ε ∈ (0, 1) and integer constant t ≥ 2, we show a lower bound for the complexity of any (t − ε)-spanner of Ω(mn1/(t−1) + n). [ABSTRACT FROM AUTHOR]

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) space, supports queries in worst case O (log 2 n) time, and updates in O (log 5 n) amortized time. This leads to an O (n α (n) log 5 n) time algorithm to solve the agglomerative clustering problem. This is a significant improvement over the current best O (n 2) time algorithms. [ABSTRACT FROM AUTHOR]

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(m3), 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 O(log2m) 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. [ABSTRACT FROM AUTHOR]

The challenge of map construction involves creating a representation of a travel network using data from the paths traveled by entities within the network. Although numerous algorithms for constructing maps can effectively piece together the overall layout of a network, accurately capturing smaller details like the positions of intersections and turns tends to be more difficult. This difficulty is especially pronounced when the data is noisy or collected at irregular intervals. In this paper we present Roadster , a map construction system that combines efficient cluster computation and a sophisticated method to construct a map from a set of such clusters. First, edges are extracted by producing a number of subtrajectory clusters, of varying widths, which naturally correspond to paths in the network. Second, representative paths are extracted from the candidate clusters. The geometry of each representative path is improved in a process involving several stages, that leads to map edges. The rich information obtained from the clustering process is also used to compute map vertices, and to finally connect them using map edges. An experimental evaluation of Roadster , using vehicle and hiking GPS data, shows that the system can produce maps of higher quality than previous methods. • We present a system to build maps from GPS tracks, based on subtrajectory clustering. • Our method uses a fast Fréchet clustering algorithm to identify potential roads. • Roadster features enhanced intersection placement and cluster selection algorithms. • We include a detailed experimental evaluation comparing to the state of the art. • Our results outperform previous methods in both global and local evaluations. [ABSTRACT FROM AUTHOR]

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

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. [ABSTRACT FROM AUTHOR]