Four results on randomized incremental constructions

DOI10.1016/0925-7721(93)90009-UzbMATH Open0781.68112OpenAlexW2076406769MaRDI QIDQ686138FDOQ686138

Raimund Seidel, K. 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

Recommendations

• Four results on randomized incremental constructions
• On lazy randomized incremental construction
• scientific article
• Towards dynamic randomized algorithms in computational geometry
• Markov incremental constructions

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)

Cites Work

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

Cited In (30)

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

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)