A simple, faster method for kinetic proximity problems
From MaRDI portal
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
Euclidean minimum spanning treeclosest pairkinetic data structureall nearest neighbors(semi-)Yao graph
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
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
