Tail estimates for the efficiency of randomized incremental algorithms for line segment intersection

DOI10.1016/0925-7721(93)90011-TzbMath0781.68120WikidataQ54309534 ScholiaQ54309534MaRDI QIDQ686143

Micha Sharir, Kurt Mehlhorn, Ermo Welzl

Publication date: 1 November 1993

Published in: Computational Geometry (Search for Journal in Brave)

zbMATH Keywords

line segment intersectionrandomized incremental algorithms

Mathematics Subject Classification ID

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

Related Items

Markov incremental constructions, A unified approach to tail estimates for randomized incremental construction

Uses Software

• Hull

Cites Work

• A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons
• Applications of random sampling to on-line algorithms in computational geometry
• On the general motion-planning problem with two degrees of freedom
• Applications of random sampling in computational geometry. II
• Four results on randomized incremental constructions
• A tail estimate for Mulmuley's segment intersection algorithm
• Probability Inequalities for Sums of Bounded Random Variables