Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/5/84; site ellie.UUCP
Path: utzoo!watmath!sunybcs!ellie!rapaport
From: rapaport@ellie.UUCP (William J. Rapaport)
Newsgroups: ont.events
Subject: COMPTATIONAL GEOMETRY/MESH-CONNECTED COMPUTERS
Message-ID: <699@ellie.UUCP>
Date: Tue, 19-Nov-85 13:52:08 EST
Article-I.D.: ellie.699
Posted: Tue Nov 19 13:52:08 1985
Date-Received: Wed, 20-Nov-85 21:18:32 EST
Distribution: ont
Organization: SUNY/Buffalo Computer Science
Lines: 51


                   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