An optimal parallel algorithm using exclusive read/writes for the rectilinear Voronoi diagram

AbstractWe present the first optimal parallel algorithm to compute the Voronoi diagram in the rectilinear (L1, Manhattan) metric. The algorithm constructs the Voronoi diagram of n points on the plane under the rectilinear metric on an EREW PRAM with n/log n processors in O(log2n) time. The processor-time product of O(n log n) is optimal and improves the previous best by a factor of order log n. Some new techniques are developed that should have applicability to many geometric problems under the rectilinear metric and, possibly, other Lp metrics