Given a rectangle R (with its edges parallel to the coordinate axes) containing a set S = { s1,...,sn} of n points in the Euclidean plane, consider the problem of finding the largest area subrectangle r in R with sides parallel to the coordinate axes that contains no point of S. We present optimal parallel algorithms for solving this problem on one- and two-dimensional arrays of processors.

Additional Metadata
Persistent URL
Journal Journal of Parallel and Distributed Computing
Dehne, F. (1990). Computing the largest empty rectangle on One- and two-dimensional processor arrays. Journal of Parallel and Distributed Computing, 9(1), 63–68. doi:10.1016/0743-7315(90)90112-3