[ont.events] UW Data Struct. Seminar, Dr. Klein on "Fixed Windowing Problems"

mwang@watmath.UUCP (mwang) (10/21/85)

DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES

DATA STRUCTURING SEMINAR

                    - Tuesday, October 29, 1985.

Dr.  Rolf Klein of the Universitat Karlsruhe will speak
on ``Fixed Windowing Problems''.

TIME:                12:30 PM  (Please Note)

ROOM:              MC 5158

ABSTRACT

Given  a  point  set  in  the  plane and a fixed planar
polygon (a window) a window query consists of enumerat-
ing  the  points in a given translate of the window.  A
recently  presented  result  shows  that  a static data
                                            ------
structure  of  optimal  size enables window queries for
convex  polygons  to  be  answered in optimal time.  We
show  that  there is a simpler, alternative data struc-
ture of optimal size which not only supports non-convex
window queries in optimal time but also allows updating
of the point set in optimal time.

                         October 21, 1985