Parallel geometric algorithms on a mesh-connected computer (Q1825643)

The authors show that a number of geometric problems can be solved on a \(\sqrt{n}\times \sqrt{n}\)-mesh-connected computer (single instruction stream, multiple data stream) in O(\(\sqrt{n})\) time which is asymptotically optimal. The algorithms are based on the divide-and- conquer problem-solving strategy. Trapezoidal decomposition and planar point location problems are solved by a direct application of the multipoint location algorithm. The authors show that the Voronoi diagram can be computed in O(\(\sqrt{n})\) time. With the help of this result many other interesting algorithms for geometric problems has been obtained.