Search

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]

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]