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 (6)

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

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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