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

DOI10.1016/0925-7721(93)90011-TMaRDI QIDQ686143zbMATH OpenWikidataFDO

Authors K. Mehlhorn, Micha Sharir, Emo 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)

Recommendations

• scientific article; zbMATH DE number 742952
• A tail estimate for Mulmuley's segment intersection algorithm
• Computing a Face in an Arrangement of Line Segments and Related Problems
• On lazy randomized incremental construction
• scientific article; zbMATH DE number 431985

Cites work

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

Cited in

(6)

• A unified approach to tail estimates for randomized incremental construction
• A tail estimate for Mulmuley's segment intersection algorithm
• An $O(E\log E + I)$ Expected Time Algorithm for the Planar Segment Intersection Problem
• Markov incremental constructions
• scientific article; zbMATH DE number 742952 (Why is no real title available?)
• RANDOMIZED EXTERNAL-MEMORY ALGORITHMS FOR LINE SEGMENT INTERSECTION AND OTHER GEOMETRIC PROBLEMS

Describes a project that uses

Uses Software

• Hull

This page was built for publication: Tail estimates for the efficiency of randomized incremental algorithms for line segment intersection

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q686143)