wlrush@water.waterloo.edu (Wenchantress Wench Wendall) (07/06/89)
will speak on ``Priority Search Trees: Applications and Variations.''
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES
DATA STRUCTURING SEMINAR
-Monday, July 10, 1989
Professor Dr. Thomas Ottman, University of Freiburg, will speak
on "Priority Search Trees: Applications and
Variations."
TIME: 3:30 p.m.
ROOM: DC 1302
ABSTRACT
Priority search trees, invented by McCreight, combine
properties of search trees and heaps. They were
originally used as a data structure in a time and space
optimal algorithm for reporting all pairs of
intersecting rectangles in a given set of iso-oriented
rectangles in the plane. Possible applications,
however, go beyond this special problem. We discuss the
dynamic fixed windowing problem as an example. Here
insertions and deletions of points are possible and
range queries with a translated polygonal window of
fixed size.
Variants of priority search trees are obtained by
choosing an appropriate coordinate system, an
underlying class of leaf search trees, the number of
points to be stored per node, and the memory (internal
or external). We discuss several of these variants, in
particular the difficulties in designing appropriate
external versions. It turns out that a new class of
red-black trees is useful in this context.