Markov incremental constructions

DOI10.1007/S00454-009-9170-6MaRDI QIDQ5896960zbMATH OpenOpenAlexFDO

Authors 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 graphsrandomized incremental constructionsClarkson-Shor bound

Mathematics Subject Classification ID

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

Recommendations

• Four results on randomized incremental constructions
• Four results on randomized incremental constructions
• scientific article; zbMATH DE number 1256644
• Incremental constructions con BRIO
• On lazy randomized incremental construction

Cites work

• scientific article; zbMATH DE number 431985 (Why is no real title available?)
• scientific article; zbMATH DE number 47926 (Why is no real title available?)
• scientific article; zbMATH DE number 1220053 (Why is no real title available?)
• scientific article; zbMATH DE number 2102775 (Why is no real title available?)
• scientific article; zbMATH DE number 777288 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• scientific article; zbMATH DE number 1433426 (Why is no real title available?)
• scientific article; zbMATH DE number 964896 (Why is no real title available?)
• A fast planar partition algorithm, II
• A fast planar partition algorithm. I
• A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons
• A subexponential bound for linear programming
• Applications of random sampling in computational geometry. II
• Applications of random sampling to on-line algorithms in computational geometry
• Asymptotics for Euclidean minimal spanning trees on random points
• Bounds on the cover time
• Four results on randomized incremental constructions
• Fully dynamic Delaunay triangulation in logarithmic expected per operation
• Incremental constructions con BRIO
• Locality in Page Reference Strings
• Markov Paging
• On nearest-neighbor graphs
• On the move-to-front scheme with Markov dependent requests
• On the randomized construction of the Delaunay tree
• Optimality of move-to-front for self-organizing data structures with locality of references
• Randomized geometric algorithms and pseudorandom generators
• Randomized incremental construction of Delaunay and Voronoi diagrams
• Randomized search trees
• Realistic image synthesis using photon mapping. With a foreword by Pat Hanrahan
• Self-organizing files with dependent accesses
• Short Random Walks on Graphs
• Small-dimensional linear programming and convex hulls made easy
• Stochastic rearrangement rules for self-organizing data structures
• THE DELAUNAY HIERARCHY
• THE SHUFFLING BUFFER
• Tail estimates for the efficiency of randomized incremental algorithms for line segment intersection

Cited in

(2)

• Incremental constructions con BRIO
• Four results on randomized incremental constructions

Describes a project that uses

Uses Software

• Hull

This page was built for publication: Markov incremental constructions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5896960)