Kinetic Euclidean minimum spanning tree in the plane

DOI10.1016/j.jda.2012.04.009zbMath1255.68196OpenAlexW2175772512MaRDI QIDQ1932347

Zahed Rahmati, Alireza Zarei

Publication date: 18 January 2013

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2012.04.009

zbMATH Keywords

Delaunay triangulationkinetic data structuresEuclidean minimum spanning tree

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

The Minimum Moving Spanning Tree Problem ⋮ The minimum moving spanning tree problem ⋮ A simple, faster method for kinetic proximity problems

Cites Work

• 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
• An O(N log N) minimal spanning tree algorithm for N points in the plane
• On the randomized construction of the Delaunay tree
• Dynamic Euclidean minimum spanning trees and extrema of binary functions
• A dynamic data structure for 3-d convex hulls and 2-d nearest neighbor queries
• On levels in arrangements of curves, iii
• Computational Geometry in C
• Kinetic and dynamic data structures for closest pair and all nearest neighbors
• Minimum spanning trees of moving points in the plane
• A simple and efficient kinetic spanner