phyllis@utcsrgv.UUCP (Phyllis Eve Bregman) (04/06/84)
****
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