Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site watmath.UUCP
Path: utzoo!watmath!mwang
From: mwang@watmath.UUCP (mwang)
Newsgroups: ont.events
Subject: UW Data Struct. Seminar, Dr. Klein on "Fixed Windowing Problems"
Message-ID: <16940@watmath.UUCP>
Date: Mon, 21-Oct-85 10:52:50 EDT
Article-I.D.: watmath.16940
Posted: Mon Oct 21 10:52:50 1985
Date-Received: Tue, 22-Oct-85 05:09:57 EDT
Expires: Wed, 30-Oct-85 00:00:00 EDT
Organization: U of Waterloo, Ontario
Lines: 31


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