On expected- and worst-case segment trees - Bucher, W.; Edelsbrunner, Herbert; Preparata, Franco (Computational Geometry: Theory and Applications, 1983)
The segment tree is a data structure for storing and maintaining a set of intervals on the real line. It has been used for an efficient algorithmic approach in a variety of geometric problems including the problem of deter-mining intersections among axis-parallel rectangles, computing the measure of a set of axis-parallel rectangles, and locating a point in a planar subdivision. A segment tree for n intervals requires 0(n) space in the best case and 0(n log n) space in the worst case. It is shown that segment trees require 0(n log n) space even in the expected case. Additionally, the worst-case upper bound on the space requirement of segment trees is improved over the previously known bound. Surprisingly, the space requirements in the expected and in the worst case differ only little.
published
yes
yes
Keywords: book chapter