A simple, faster method for kinetic proximity problems

DOI10.1016/j.comgeo.2014.12.002zbMath1314.65032arXiv1311.2032OpenAlexW1993674183MaRDI QIDQ2344057

Alireza Zarei, Zahed Rahmati, Mohammad Ali Abam, Valerie King, S. H. 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

Euclidean minimum spanning treeclosest pairkinetic data structureall nearest neighbors(semi-)Yao graph

Mathematics Subject Classification ID

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

Related Items (6)

Kinetic \(k\)-semi-Yao graph and its applications ⋮ Kinetic Reverse k-Nearest Neighbor Problem ⋮ Approximate $k$-Nearest Neighbor Graph on Moving Points ⋮ Stable Delaunay graphs ⋮ Approximating the minimum closest pair distance and nearest neighbor distances of linearly moving points ⋮ A clustering-based approach to kinetic closest pair

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Kinetic and dynamic data structures for convex hulls and upper envelopes
• Classes of graphs which approximate the complete Euclidean graph
• On minimum and maximum spanning trees of linearly moving points
• Indexing moving points
• On levels in arrangements of curves
• A data structure for dynamic trees
• Kinetic Euclidean minimum spanning tree in the plane
• On topological changes in the Delaunay triangulation of moving points
• Intersection reverse sequences and geometric applications.
• Kinetic Pie Delaunay Graph and Its Applications
• Connections between Theta-Graphs, Delaunay Triangulations, and Orthogonal Surfaces
• On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
• Computational Geometry in C
• Data Structures for Mobile Data
• Voronoi Diagrams of Moving Points
• Kinetic and Stationary Point-Set Embeddability for Plane Graphs
• Kinetic and dynamic data structures for closest pair and all nearest neighbors
• Kinetic data structures for all nearest neighbors and closest pair in the plane
• Sharp bounds on Davenport-Schinzel sequences of every order
• Minimum spanning trees of moving points in the plane
• Kinetic stable Delaunay graphs
• Binary Search Trees of Bounded Balance
• A simple and efficient kinetic spanner

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