A simple, faster method for kinetic proximity problems

DOI10.1016/J.COMGEO.2014.12.002MaRDI QIDQ2344057zbMATH OpenOpenAlexFDO

Authors Zahed Rahmati, Mohammad A. Abam, Valerie King, Alireza Zarei, Sue Whitesides

Publication date 12 May 2015

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1311.2032

zbMATH Keywords

(semi-)Yao graphall nearest neighborsclosest pairEuclidean minimum spanning treekinetic data structure

Mathematics Subject Classification ID

Trees (05C05) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Data structures (68P05) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: For a set of $n$ points in the plane, this paper presents simple kinetic data structures (KDS's) for solutions to some fundamental proximity problems, namely, the all nearest neighbors problem, the closest pair problem, and the Euclidean minimum spanning tree (EMST) problem. Also, the paper introduces KDS's for maintenance of two well-studied sparse proximity graphs, the Yao graph and the Semi-Yao graph. We use sparse graph representations, the Pie Delaunay graph and the Equilateral Delaunay graph, to provide new solutions for the proximity problems. Then we design KDS's that efficiently maintain these sparse graphs on a set of $n$ moving points, where the trajectory of each point is assumed to be an algebraic function of constant maximum degree $s$. We use the kinetic Pie Delaunay graph and the kinetic Equilateral Delaunay graph to create KDS's for maintenance of the Yao graph, the Semi-Yao graph, all the nearest neighbors, the closest pair, and the EMST. Our KDS's use $O(n)$ space and $O(nlogn)$ preprocessing time. We provide the first KDS's for maintenance of the Semi-Yao graph and the Yao graph. Our KDS processes $$ (resp. $$) events to maintain the Semi-Yao graph (resp. the Yao graph); each event can be processed in time $O(logn)$ in an amortized sense. Here, $$ is an extremely slow-growing function. Our KDS for maintenance of all the nearest neighbors and the closest pair processes $$ events. For maintenance of the EMST, our KDS processes $$ events. For all three of these problems, each event can be handled in time $O(logn)$ in an amortized sense. We improve the previous randomized kinetic algorithm for maintenance of all the nearest neighbors by Agarwal, Kaplan, and Sharir, and the previous EMST KDS by Rahmati and Zarei.

Recommendations

• Kinetic data structures for all nearest neighbors and closest pair in the plane
• Kinetic pie Delaunay graph and its applications
• Kinetic \(k\)-semi-Yao graph and its applications
• Kinetic and dynamic data structures for closest pair and all nearest neighbors
• Kinetic Euclidean minimum spanning tree in the plane

Cites work

• A data structure for dynamic trees
• A simple and efficient kinetic spanner
• Binary Search Trees of Bounded Balance
• Classes of graphs which approximate the complete Euclidean graph
• Computational Geometry in C
• Connections between Theta-graphs, Delaunay triangulations, and orthogonal surfaces
• Data Structures for Mobile Data
• scientific article; zbMATH DE number 432761 (Why is no real title available?)
• scientific article; zbMATH DE number 3887059 (Why is no real title available?)
• scientific article; zbMATH DE number 4070353 (Why is no real title available?)
• scientific article; zbMATH DE number 732977 (Why is no real title available?)
• scientific article; zbMATH DE number 219238 (Why is no real title available?)
• scientific article; zbMATH DE number 6472653 (Why is no real title available?)
• Indexing moving points
• Intersection reverse sequences and geometric applications.
• Kinetic and dynamic data structures for closest pair and all nearest neighbors
• Kinetic and dynamic data structures for convex hulls and upper envelopes
• Kinetic and Stationary Point-Set Embeddability for Plane Graphs
• Kinetic data structures for all nearest neighbors and closest pair in the plane
• Kinetic Euclidean minimum spanning tree in the plane
• Kinetic pie Delaunay graph and its applications
• Kinetic stable Delaunay graphs
• Minimum spanning trees of moving points in the plane
• On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
• On levels in arrangements of curves
• On minimum and maximum spanning trees of linearly moving points
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Sharp bounds on Davenport-Schinzel sequences of every order
• Static and kinetic geometric spanners with applications
• The tourist in the shopping arcade
• Voronoi Diagrams of Moving Points

Cited in

(9)

• Kinetic \(k\)-semi-Yao graph and its applications
• Kinetic Euclidean minimum spanning tree in the plane
• Kinetic pie Delaunay graph and its applications
• Kinetic reverse \(k\)-nearest neighbor problem
• Kinetic Euclidean minimum spanning tree in the plane
• Approximate $k$-Nearest Neighbor Graph on Moving Points
• Approximating the minimum closest pair distance and nearest neighbor distances of linearly moving points
• A clustering-based approach to kinetic closest pair
• Stable Delaunay graphs

This page was built for publication: A simple, faster method for kinetic proximity problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2344057)