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, 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

- 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 with Timothy Chan,
- the application of the above to data fitting, solid modeling, motion planning, etc.

My current focus is on applications of computational geometry in Geographic Information Systems (GIS). Examples include line simplification, polygon overlay processing, and drainage on TINs. I am especially interested in tasks that require geometric structure. We are implementing compact Voronoi diagrams as a reasonable representation of such structure.

See my on-line recent papers for more specifics.

Go to Home page for Jack, UBC CS, or IAM