Tail estimates for the efficiency of randomized incremental algorithms for line segment intersection (Q686143)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Tail estimates for the efficiency of randomized incremental algorithms for line segment intersection |
scientific article |
Statements
Tail estimates for the efficiency of randomized incremental algorithms for line segment intersection (English)
0 references
1 November 1993
0 references
The authors analyze three already known randomized incremental algorithms for line segment intersection in the plane and give tail estimates for their time or space complexity. Particularly, they prove that for each of these algorithms there exists a constant \(C\) such that the probability that the running time (space efficiency) of the algorithm exceeds \(C\) times its expected value can be appropriately bounded.
0 references
randomized incremental algorithms
0 references
line segment intersection
0 references
