An efficient VLSI architecture with applications to geometric problems (Q1124264)

The authors show that a multiprocessor with n processors and \(n^ 2\) memory elements (element \(m_{ij}\) accessible by processors {\#}i,j) can execute the basic operations of plane computational geometry (convex hull, intersection, etc.) for \(n^ 2\) points in \(O(n \log n)\) time. \{For numbers of points that are not square the count is not so advantageous and the switching and access time to the memory elements can be considerable.\}