Title: Lower bounds for geometric diameter problems

Speaker: Antoine Vigneron
INRA

Date: Friday Nov 17, 2006
Time 3-4PM
Venue: Room 3584, HKUST

  
Abstract:
We give an Omega(n log n) lower bound for computing
the diameter of a 3D convex polytope. This bound is tight.
We also give a reduction from Hopcroft's problem to the
problem of computing the diameter of a point set in R7.