Several computational geometry
algorithms for efficiently processing tens or hundreds of millions of objects
are presented. They include: nearest point determination, line segment
intersection, areas of all the nonempty polygon intersections in two planar
graphs, volume and area of the union of many polyhedra, and connected component
determination in an 1000x1000x1000 cellular universe.
For example, preprocessing ten million points and then performing ten million
closest point queries takes a total of 77 seconds on a a laptop. Design
techniques include local topological data structures, uniform grids, and
generally keeping it simple. These algorithms also parallelize well. These
algorithms are useful to process large geometric databases occur in VLSI design,
CAD/CAM, and Geographic Information Science.

DATE:
July 26, 2004, Monday @ 15:00
PLACE: EA-409

Biography of Dr.
Franklin: Dr. W. Randolph Franklin is an Associate
Professor at Rensselaer Polytechnic Institute, Troy NY, USA. He has been the
Director of the Numeric, Symbolic, and Geometric Computation Program at the US
National Science Foundation, where he took the lead in two Computational
Algorithms and Representations for Geometric Objects (CARGO) solicitations that
were joint with DARPA. Franklin has held visiting
positions at UC Berkeley, Genova, Italy, Laval, Canada, CSIRO, Canberra,
Australia, and the National University of Singapore. Franklin's degrees are from
Toronto and Harvard.
Franklin's research interests are computational cartography, computer graphics,
computational geometry, and geographic information science, emphasizing small,
simple, and fast data structures and algorithms.