Four results on randomized incremental constructions

DOI10.1016/0925-7721(93)90009-UzbMath0781.68112OpenAlexW2076406769MaRDI QIDQ686138

Raimund Seidel, Kurt Mehlhorn, Kenneth L. Clarkson

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)

Related Items

Faster geometric algorithms via dynamic determinant computation, An introduction to randomization in computational geometry, From proximity to utility: a Voronoi partition of Pareto optima, A conservative front tracking method in \(N\) dimensions, Randomized incremental construction of simple abstract Voronoi diagrams in 3-space, Randomized search trees, Efficient generation of densely packed convex polyhedra for 3D discrete and finite-discrete element methods, Decomposing arrangements of hyperplanes: VC-dimension, combinatorial dimension, and point location, Fast skeleton construction, Range minima queries with respect to a random permutation, and approximate range counting, Dynamic well-spaced point sets, Random sampling with removal, Certifying algorithms, Markov incremental constructions, Combining improvement and refinement techniques: 2D Delaunay mesh adaptation under domain changes, Parallelization alternatives and their performance for the convex hull problem, On lazy randomized incremental construction, A computational basis for higher-dimensional computational geometry and applications, Dynamic data structures for fat objects and their applications, Abstract Voronoi Diagrams from Closed Bisecting Curves, ABSTRACT VORONOI DIAGRAMS WITH DISCONNECTED REGIONS, Regular triangulations of dynamic sets of points, Randomized incremental construction for the Hausdorff Voronoi diagram revisited and extended, A Complete Implementation for Computing General Dimensional Convex Hulls, Dog Bites Postman, OPTIMAL LINE BIPARTITIONS OF POINT SETS, AN ORACLE-BASED, OUTPUT-SENSITIVE ALGORITHM FOR PROJECTIONS OF RESULTANT POLYTOPES

Uses Software

• Hull

Cites Work

• On the construction of abstract Voronoi diagrams
• A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons
• Bounded ordered dictionaries in O(log log N) time and O(n) space
• 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
• Applications of random sampling in computational geometry. II
• Design and implementation of an efficient priority queue
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item