A Tail Estimate with Exponential Decay for the Randomized Incremental Construction of Search Structures
share
We revisit the randomized incremental construction of the Trapezoidal Search DAG (TSD) for a set of n non-crossing segments, e.g. edges from planar subdivisions. It is well known that this point location structure has O(n) expected size and O(n ln n) expected construction time. Our main result is an improved tail bound, with exponential decay, for the size of the TSD: There is a constant such that the probability for a TSD to exceed its expected size by more than this factor is at most 1/e^n. This yields improved bounds on the TSD construction and their maintenance. I.e. TSD construction takes with high probability O(n ln n) time and TSD size can be made worst case O(n) with an expected rebuild cost of O(1). The proposed analysis technique also shows that the expected depth is O(ln n), which partially solves a recent conjecture by Hemmer et al. that is used in the CGAL implementation of the TSD.
READ FULL TEXT