Four results on randomized incremental constructions

DOI10.1016/0925-7721(93)90009-UMaRDI QIDQ686138zbMATHOpenAlexFDO

Authors Kenneth L. Clarkson, K. Mehlhorn, Raimund Seidel

Publication date 1 November 1993

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0925-7721(93)90009-u

zbMATH Keywords

convex hullspace complexityexpected behaviorrandomized incremental algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Four results on randomized incremental constructions
• On lazy randomized incremental construction
• scientific article; zbMATH DE number 108277
• Towards dynamic randomized algorithms in computational geometry
• Markov incremental constructions

Cites work

• scientific article; zbMATH DE number 432847 (Why is no real title available?)
• scientific article; zbMATH DE number 3887059 (Why is no real title available?)
• scientific article; zbMATH DE number 4032498 (Why is no real title available?)
• scientific article; zbMATH DE number 108277 (Why is no real title available?)
• A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons
• Applications of random sampling in computational geometry. II
• Applications of random sampling to on-line algorithms in computational geometry
• Bounded ordered dictionaries in O(log log N) time and O(n) space
• Design and implementation of an efficient priority queue
• Fully dynamic Delaunay triangulation in logarithmic expected per operation
• On the construction of abstract Voronoi diagrams
• Randomized incremental construction of Delaunay and Voronoi diagrams

Cited in

(33)

• Certifying algorithms
• Combining improvement and refinement techniques: 2D Delaunay mesh adaptation under domain changes
• Range minima queries with respect to a random permutation, and approximate range counting
• Optimal line bipartitions of point sets
• OPTIMAL LINE BIPARTITIONS OF POINT SETS
• Fast skeleton construction
• A conservative front tracking method in \(N\) dimensions
• Faster geometric algorithms via dynamic determinant computation
• Abstract Voronoi diagrams from closed bisecting curves
• On lazy randomized incremental construction
• Random sampling with removal
• An interface-preserving moving mesh in multiple space dimensions
• Markov incremental constructions
• scientific article; zbMATH DE number 742952 (Why is no real title available?)
• On lazy randomized incremental construction
• Regular triangulations of dynamic sets of points
• A computational basis for higher-dimensional computational geometry and applications
• Dynamic well-spaced point sets
• An oracle-based, output-sensitive algorithm for projections of resultant polytopes
• Four results on randomized incremental constructions
• Efficient generation of densely packed convex polyhedra for 3D discrete and finite-discrete element methods
• Incremental constructions con BRIO
• Abstract Voronoi diagrams with disconnected regions
• An introduction to randomization in computational geometry
• Randomized search trees
• Randomized incremental construction of simple abstract Voronoi diagrams in 3-space
• Dynamic data structures for fat objects and their applications
• From proximity to utility: a Voronoi partition of Pareto optima
• Dog Bites Postman
• Randomized incremental construction for the Hausdorff Voronoi diagram revisited and extended
• Decomposing arrangements of hyperplanes: VC-dimension, combinatorial dimension, and point location
• A Complete Implementation for Computing General Dimensional Convex Hulls
• Parallelization alternatives and their performance for the convex hull problem

Describes a project that uses

Uses Software

• Hull

This page was built for publication: Four results on randomized incremental constructions

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