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