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