# On expected- and worst-case segment trees

Bucher W, Edelsbrunner H. 1983.On expected- and worst-case segment trees. In: Computational Geometry: Theory and Applications. Advances in Computing Research , vol. 1, 109–125.

Download

**No fulltext has been uploaded. References only!**

*Book Chapter*|

*Published*|

*English*

Author

Bucher, W.;
Edelsbrunner, Herbert

^{ISTA}^{}Book Editor

Preparata, Franco

Series Title

Advances in Computing Research

Abstract

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.

Publishing Year

Date Published

1983-01-01

Book Title

Computational Geometry: Theory and Applications

Volume

1

Page

109 - 125

IST-REx-ID

### Cite this

Bucher W, Edelsbrunner H. On expected- and worst-case segment trees. In: Preparata F, ed.

*Computational Geometry: Theory and Applications*. Vol 1. Elsevier; 1983:109-125.Bucher, W., & Edelsbrunner, H. (1983). On expected- and worst-case segment trees. In F. Preparata (Ed.),

*Computational Geometry: Theory and Applications*(Vol. 1, pp. 109–125). Elsevier.Bucher, W., and Herbert Edelsbrunner. “On Expected- and Worst-Case Segment Trees.” In

*Computational Geometry: Theory and Applications*, edited by Franco Preparata, 1:109–25. Elsevier, 1983.W. Bucher and H. Edelsbrunner, “On expected- and worst-case segment trees,” in

*Computational Geometry: Theory and Applications*, vol. 1, F. Preparata, Ed. Elsevier, 1983, pp. 109–125.Bucher, W., and Herbert Edelsbrunner. “On Expected- and Worst-Case Segment Trees.”

*Computational Geometry: Theory and Applications*, edited by Franco Preparata, vol. 1, Elsevier, 1983, pp. 109–25.**Link(s) to Main File(s)**

Access Level

Closed Access