Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10 5/3/83; site utcsrgv.UUCP
Path: utzoo!utcsrgv!phyllis
From: phyllis@utcsrgv.UUCP (Phyllis Eve Bregman)
Newsgroups: ont.events
Subject: J. Nievergelt:  "Algorithms and data structures for geometric computation".
Message-ID: <3755@utcsrgv.UUCP>
Date: Thu, 5-Apr-84 18:19:28 EST
Article-I.D.: utcsrgv.3755
Posted: Thu Apr  5 18:19:28 1984
Date-Received: Thu, 5-Apr-84 20:16:54 EST
Organization: CSRG, University of Toronto
Lines: 38

****

      UofT Department of Computer Science Seminar Schedule for
		the week of April 9th, 1984

Tuesday, April 10th, 2:00 P.M., SF1105:  Professor J. Nievergelt,
   ETH, Zurich, Switzerland:  "Algorithms and data structures for
   geometric computation".

   ABSTRACT:  The growing importance of computer applications that
   involve geometric objects (e.g. CAD, graphics, geographic data
   processing) creates a need for libraries of geometric software,
   much as earlier computer applications led to numerical subroutine
   libraries.  What geometric software is sufficiently general to be
   included in a general purpose program library for geometric
   computation?  We present two candidates:  a class of algorithms
   and a data structure.

   Sweep algorithms solve many geometric problems in 2 or more
   dimensions in time O((n+s) log n), where n measures the amount of
   data (e.g. the number of line segments), and s its intricacy
   (e.g. the number of unknown intersections).  Realistic configurations
   are often characterized by s = O(n), thus many practical geometric
   problems can be solved at the asymptotic cost of sorting.

   Data structures suitable for storing geometric objects should
   treat all space dimensions in a symmetric way and support range
   and intersection queries.  The grid file has been designed to meet
   these requirements with the goal of minimizing disk accesses.
   A transformation of geometric objects to points in higher-dimensional
   spaces reduces intersection queries to sweeping simple regions 
   called search cones.
-- 
		Phyllis Eve Bregman
		CSRG, Univ. of Toronto
		{decvax,linus,ihnp4,uw-beaver,allegra,utzoo}!utcsrgv!phyllis
		CSNET:  phyllis@toronto
		(416) 978 6985