Research Interests

My primary research area is computational geometry, in which one studies the design and analysis of algorithms for geometric computation. Computational geometry finds application in problems from solid modeling, CAD/CAM, computer graphics, molecular biology, data structuring, and robotics, as well as problems from discrete geometry and topology.

Most of my work involves identifying, representing, and exploiting geometric and topological information that permit efficient computation. For example, previous results have included

• the algebraic complexity of polygon overlay and boolean operations,
• compact encoding of terrain models via incremental Delaunay triangulation,
• Approximate shape and skeleton by combining Voronoi and Delaunay
• a unifying framework for computing shortest paths among obstacles in the plane under various metrics and orientation restrictions,
• data structures for convex hulls that support insertions and deletions of points,
• geometric search problems where local information is not quite enough,
• the difficulty of geometric assembly,
• output-sensitive algorithms for convex hulls and Voronoi diagrams,
• the application of the above to data fitting, solid modeling, motion planning, etc.

My current focus is on applications of computational geometry in Molecular Biology and Geographic Information Systems (GIS). Examples of the former include docking and folding problems, and scoring protein structures using Delaunay tetrahedralization. Examples of the latter include polygon overlay processing and drainage on TINs. I am especially interested in tasks that require geometric structure.

See my on-line papers for more specifics.