Path: utzoo!censor!geac!torsqnt!lethe!yunexus!nexus.YorkU.CA!s442215
From: s442215@nexus.YorkU.CA (Binhai Zhu)
Newsgroups: comp.theory
Subject: Open problem???
Message-ID: <17966@yunexus.YorkU.CA>
Date: 22 Nov 90 02:55:51 GMT
Sender: news@yunexus.YorkU.CA
Organization: York University, Toronto, Ont.
Lines: 14

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.