Simple, Faster Kinetic Data Structures
Date
2014-08-28
Authors
Rahmati, Zahed
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Proximity problems and point set embeddability problems are fundamental and well-studied in computational geometry and graph drawing. Examples of such problems that are of particular interest to us in this dissertation include: finding the closest pair among a set P of points, finding the k-nearest neighbors to each point p in P, answering reverse k-nearest neighbor queries, computing the Yao graph, the Semi-Yao graph and the Euclidean minimum spanning tree of P, and mapping the vertices of a planar graph to a set P of points without inducing edge crossings.
In this dissertation, we consider so-called kinetic version of these problems, that is, the points are allowed to move continuously along known trajectories, which are subject to change. We design a set of data structures and a mechanism to efficiently update the data structures. These updates occur at critical, discrete times. Also, a query may arrive at any time. We want to answer queries quickly without solving problems from scratch, so we maintain solutions continuously. We present new techniques for giving kinetic solutions with better performance for some these problems, and we provide the first kinetic results for others. In particular, we provide:
• A simple kinetic data structure (KDS) to maintain all the nearest neighbors and the closest pair. Our deterministic kinetic approach for maintenance of all the nearest neighbors improves the previous randomized kinetic algorithm.
• An exact KDS for maintenance of the Euclidean minimum spanning tree, which improves the previous KDS.
• The first KDS's for maintenance of the Yao graph and the Semi-Yao graph.
• The first KDS to consider maintaining plane graphs on moving points.
• The first KDS for maintenance of all the k-nearest neighbors, for any k ≥ 1.
• The first KDS to answer the reverse k-nearest neighbor queries, for any k ≥ 1 in any fixed dimension, on a set of moving points.
Description
Keywords
Kinetic Data Structures, Proximity Problems, Point Set Embedding Problem, Euclidean Minimum Spanning Tree, Closest Pair, All Nearest Neighbors, Reverse k-Nearest Neighbor Queries, Yao Graph, Semi-Yao graph