The paper presents a parallel algorithm for location of $O(n)$ points in a subdivision induced by a Voronoi diagram in the plane. The technique is based on the chain method [10] for sequential location of multiple points in a planar subdivision. It runs in $O(\log^2n)$ time using $O(n)$ processors on a hypercube or cube-connected cycle. The algorithm leads to $O(\log^3n)$ time algorithm for the construction of Voronoi diagram of a set of $n$ points on a hypercube or cube-connected cycle with $O(n)$ processors, which improves a former result by A. Chow [4].