Parallel geometric algorithms on mesh-connected computers
Chang‐Sung Jeong, T. D. Lee · Fall joint computer conference · 1987
We show that a number of geometric problems can be solved on a \trn x \trn mesh connected computer(MCC) in 0(\trn) time, which is optimal to within a constant factor, since a nontrivial data movement on an MCC requires \gW(\trn) time. The problems studied here include multipoint location, planar point location, trapezoidal decomposition, intersection detection, intersection of two convex polygons, Voronoi diagram, the largest empty circle, the smallest enclosing circle, etc. The 0(\trn) algorithms for all of the above problems are based on the classical divide-and-conquer problem solving strategy.