Markov incremental constructions

DOI10.1007/s00454-009-9170-6zbMath1176.68222MaRDI QIDQ5896960

Wolfgang Mulzer, Bernard Chazelle

Publication date: 27 August 2009

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

Full work available at URL: https://doi.org/10.1007/s00454-009-9170-6

zbMATH Keywords

expander graphs; randomized incremental constructions; Clarkson-Shor bound

Mathematics Subject Classification ID

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

Related Items

Data structures on event graphs

Uses Software

• Hull

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Four results on randomized incremental constructions
• Tail estimates for the efficiency of randomized incremental algorithms for line segment intersection
• A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons
• Stochastic rearrangement rules for self-organizing data structures
• Small-dimensional linear programming and convex hulls made easy
• Randomized incremental construction of Delaunay and Voronoi diagrams
• Applications of random sampling to on-line algorithms in computational geometry
• Fully dynamic Delaunay triangulation in logarithmic expected per operation
• Asymptotics for Euclidean minimal spanning trees on random points
• On the randomized construction of the Delaunay tree
• Optimality of move-to-front for self-organizing data structures with locality of references
• On nearest-neighbor graphs
• Bounds on the cover time
• Applications of random sampling in computational geometry. II
• Randomized geometric algorithms and pseudorandom generators
• Randomized search trees
• A subexponential bound for linear programming
• A fast planar partition algorithm. I
• THE DELAUNAY HIERARCHY
• Self-organizing files with dependent accesses
• A fast planar partition algorithm, II
• On the move-to-front scheme with Markov dependent requests
• Markov Paging
• THE SHUFFLING BUFFER
• Short Random Walks on Graphs
• Incremental constructions con BRIO
• Locality in Page Reference Strings