Discrete Mathematics and Optimization Seminar
AVNER MAGEN |
University of Toronto
Monday January 19th at 4.30pm
Burnside 1205
Title. Sublinear Geometric Algorithms.
Abstract.
We initiate an investigation of sublinear algorithms
for geometric problems in two and three dimensions.
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 O(sqrt{n}),
where n is the size of the input. We also provide sublinear solutions for
the approximate evaluation of the volume of a convex polytope
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)