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, HerbertISTA 
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, Edelsbrunner H. 1983.On expected- and worst-case segment trees. In: Computational Geometry: Theory and Applications. Advances in Computing Research , vol. 1, 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
Google Scholar