Computational geometry (C.A. Wang)

Many problems rising in different areas, such as computer graphics, VLSI, Pattern Recognition and robotics, can be solved efficiently if some geometric structures are available. For example, problems such as finding the closest pair of a set of points, finding the nearest neighbor for each point of the set, constructing the Euclidean minimum spanning tree of the set, constructing the convex hull of the set played an important role in Pattern Recognition. These problems can be solved in linear-time if the Delaunay triangulation (or its dual, Voronoi diagram) of the set is available. Research on constructing Delaunay triangulations and Voronoi diagrams in the presence of barriers has recently become quite active as these two geometric structures are useful tools for robot's motion planning.

A considerable amount of applications involve mass geometric computations. For instance, detecting and reporting the intersections of hundreds of thousands of rectangles (polygons) may be required in layouts of VLSI design and hidden surface removal in computer graphics. Designing parallel algorithms becomes essential for these applications.

Theoretical problems such as triangulations and practical problems such as robot path finding, collision detection, and VLSI layout are particularly interesting in our recent research.

Revised: 1995.11.2