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.