Dynamic Half-Space Reporting, Geometric Optimization, and Minimum Spanning Trees

The authors describe dynamic data structures for half-space range reporting and for maintaining the minima of a decomposable function. Using these data structures, they obtain efficient dynamic algorithms for a number of geometric problems, including closest/farthest neighbor searching, fixed dimension linear programming, bi-chromatic closest pair, diameter, and Euclidean minimum spanning tree. >

Authors

• Pankaj K. Agarwal
• David Eppstein
• Jirí Matousek 0001

Keywords

• Tree data structures
• Heuristic algorithms
• Computer science
• Data structures
• Tree graphs
• Application software
• Computer graphics
• Very large scale integration
• Mathematics
• Triangular
• Time And Space
• Data Structure
• Simplex
• Efficient Algorithm
• Local Point
• Hyperplane
• Leaf Node
• Subtree
• Dynamic Algorithm
• Red Points
• Neighboring Points
• Nearest Neighbor Search
• Closest Neighbors
• Blue Points
• Update Time
• Points In Plane
• Call Detail Records
• Query Time