eppstein@glacier.ics.uci.edu (David Eppstein) (11/27/90)
In article <17966@yunexus.YorkU.CA> s442215@nexus.YorkU.CA (Binhai Zhu) writes: > 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? No. If you could, you could find the nearest pair of points. But this is known to be impossible, by a reduction from the integer smallest gap problem. More specifically, suppose you have a collection of n integers. For each integer a_i, place a point at (i/n,a_i). The points end up sorted by x-coordinate, and the closest pair of points gives the closest pair of integers. But the closest integer problem has an Omega(n log n) lower bound [A.C. Yao, FOCS 1989, 308-313]. The question is more interesting when the points are given in two sorted orders, one per coordinate. Then the problem for the usual L_2 metric remains open, but for the L_1 (equivalently L_inf) metric the Voronoi diagram can be computed in O(n log log n) time [Chew & Fortune, 13th Symp. Math. Prog., Japan, 1988]. -- David Eppstein Info & Computer Science, UC Irvine eppstein@ics.uci.edu