Four results on randomized incremental constructions

DOI10.1007/3-540-55210-3_205zbMath1494.68270OpenAlexW1566883427MaRDI QIDQ5096803

Kenneth L. Clarkson, Kurt Mehlhorn, Raimund Seidel

Publication date: 18 August 2022

Published in: STACS 92 (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.968.6359

zbMATH Keywords

computational geometry

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Data structures (68P05) Randomized algorithms (68W20)

Related Items

Mixed-volume computation by dynamic lifting applied to polynomial system solving, Randomized incremental construction of abstract Voronoi diagrams, Tail estimates for the efficiency of randomized incremental algorithms for line segment intersection, Fully dynamic Delaunay triangulation in logarithmic expected per operation, A unified approach to tail estimates for randomized incremental construction, Credal networks

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• Applications of random sampling to on-line algorithms in computational geometry
• Applications of random sampling in computational geometry. II
• Design and implementation of an efficient priority queue