[comp.theory] Open problem???

s442215@nexus.YorkU.CA (Binhai Zhu) (11/22/90)

Hi, everybody,

   I'd like to pose a problem which I met when I was working on
my master thesis.

   1) If n points on the plane are already sorted according to 
      their x-coordinates(not according to their y-coordinates).
      Can you compute the Voronoi Diagram of these points in o(nlogn)
      time?

      Or can you proof the lower bound is still $\Omega(nlogn)$?
      /* I think the latter is correct, but I have no idea to prove it*/

Binhai Zhu.