Monday January 19th at 4.30pm

We give optimal algorithms for detecting intersection of convex polygons and polyhedra, point location in two-dimensional

Delaunay triangulations and Voronoi diagrams, and ray shooting in convex polyhedra, all of which run in expected time

where

in 3D and the length of the shortest path between two points on the boundary.

Joint work with Bernard Chazelle and Ding Liu (Princeton University)