Tail estimates for the space complexity of randomized incremental algorithms
Lists
Only you see this
Abstract
We give tail estimates for the space complexity of randomized incremental algorithms for line segment intersection in the plane. For n the number of segments, m is the number of intersections, and m ≥ n ln n ln(3) n, there is a constant c such that the probability that the total space cost exceeds c times the expected space cost is e-O(m/(n ln n)).
BibTeX
@inproceedings{mehlhorn1992tail,
author = {Kurt Mehlhorn and Micha Sharir and Emo Welzl},
title = {{Tail estimates for the space complexity of randomized incremental algorithms}},
booktitle = {SODA},
year = {1992},
url = {https://openreview.net/forum?id=LhSD_sSEMvE},
}Loading related content...