rapaport@ellie.UUCP (William J. Rapaport) (11/19/85)
UNIVERSITY AT BUFFALO
STATE UNIVERSITY OF NEW YORK
DEPARTMENT OF
COMPUTER SCIENCE
COLLOQUIUM
RUSS MILLER
Department of Computer Science
University at Buffalo
COMPUTATIONAL GEOMETRY ON A MESH-CONNECTED COMPUTER
The field of computational geometry offers elegant serial
solutions and efficient serial algorithms for many problems.
We will present optimal (in the O-notational sense) parallel
algorithms for determining several fundamental geometric
properties of figures on an SIMD mesh-connected array of
simple processing elements. For example, given a figure
represented by the Cartesian coordinates of O(n) planar
points, distributed one point per processor on a mesh-
connected computer with n processing elements, we give
THETA(sqrt(n)) algorithms for identifying the convex hull of
the figure and for determining a smallest enclosing box of
the figure. We will also present optimal solutions to a
variety of area, nearest-neighbor, and intersection problems
involving convex figures, circles, hyperplanes, and iso-
oriented rectangles.
Thursday, December 5, 1985
4:00 P.M.
Bell 337, Amherst Campus
Coffee and doughnuts will be served at 3:30 P.M., 224 Bell Hall
For further information, call (716) 636-3181.
--
William J. Rapaport
Assistant Professor
Dept. of Computer Science, SUNY Buffalo, Buffalo, NY 14260
(716) 636-3193, 3180
uucp: ...{allegra,decvax,watmath}!sunybcs!rapaport
...{cmc12,hao,harpo}!seismo!rochester!rocksvax!sunybcs!rapaport
cs: rapaport@buffalo
arpa: rapaport%buffalo@csnet-relay
bitnet: rapaport@sunybcs