Dynamic Euclidean minimum spanning trees and extrema of binary functions

DOI10.1007/BF02574030zbMath0815.68078MaRDI QIDQ1346130

David Eppstein

Publication date: 20 March 1995

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/131349

zbMATH Keywords

spanning treedynamic algorithmsordered nearest neighbor path

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (18)

On Locality-Sensitive Orderings and Their Applications ⋮ Average case analysis of dynamic geometric optimization ⋮ Maintaining minimum spanning trees in dynamic graphs ⋮ Kinetic Euclidean minimum spanning tree in the plane ⋮ Dynamic connectivity in disk graphs ⋮ On bounded leg shortest paths problems ⋮ Energy-efficient paths in radio networks ⋮ Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications ⋮ Straight Skeletons of Three-Dimensional Polyhedra ⋮ Dynamic geometric data structures via shallow cuttings ⋮ On Locality-Sensitive Orderings and Their Applications ⋮ Dynamic data structures for approximate Hausdorff distance in the word RAM ⋮ Stable roommates spanner ⋮ Connected dominating sets on dynamic geometric graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Shortest paths in intersection graphs of unit disks ⋮ Nearly Optimal Planar $k$ Nearest Neighbors Queries under General Distance Functions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Maintenance of configurations in the plane
• Euclidean minimum spanning trees and bichromatic closest pairs
• Maintaining the minimal distance of a point set in polylogarithmic time
• Off-line dynamic maintenance of the width of a planar point set
• Iterated nearest neighbors and finding minimal polytopes
• An optimal algorithm for the on-line closest-pair problem
• A data structure for dynamic range queries
• Geometry Helps in Matching
• Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
• Adding range restriction capability to dynamic data structures
• Decomposable searching problems I. Static-to-dynamic transformation
• Dynamic Three-Dimensional Linear Programming
• Maintenance of geometric extrema
• Static and dynamic algorithms for k-point clustering problems

This page was built for publication: Dynamic Euclidean minimum spanning trees and extrema of binary functions