Average case analysis of dynamic geometric optimization

DOI10.1016/0925-7721(95)00018-6zbMath0849.68121OpenAlexW2013987819WikidataQ127720909 ScholiaQ127720909MaRDI QIDQ1917043

David Eppstein

Publication date: 4 November 1996

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0925-7721(95)00018-6

zbMATH Keywords

maximum spanning treerotating caliper graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (3)

On some geometric problems of color-spanning sets ⋮ On Some Geometric Problems of Color-Spanning Sets ⋮ Maintaining the extent of a moving point set

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computing Euclidean maximum spanning trees
• Voronoi diagrams from convex hulls
• Euclidean minimum spanning trees and bichromatic closest pairs
• Small-dimensional linear programming and convex hulls made easy
• Off-line dynamic maintenance of the width of a planar point set
• Helly-type theorems and generalized linear programming
• Dynamic Euclidean minimum spanning trees and extrema of binary functions
• A data structure for dynamic trees
• Incremental topological flipping works for regular triangulations
• A fast planar partition algorithm. I
• Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
• Decomposable searching problems I. Static-to-dynamic transformation
• On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
• ON MAINTAINING THE WIDTH AND DIAMETER OF A PLANAR POINT-SET ONLINE
• Fully Dynamic Point Location in a Monotone Subdivision

This page was built for publication: Average case analysis of dynamic geometric optimization