Sub-logarithmic algorithms for the largest empty rectangle problem

The authors show that the largest empty rectangle problem can be solved by reducing it, in a natural way, to the all nearest smaller values problem. They provide two classes of algorithms: the first one assumes that the input points are available sorted by x (resp. y) coordinate. The authors algorithm corresponding to this case runs in O(log log n) time using n²/log log n processors in the common-CRCW-PRAM model. For unsorted input, they present algorithms that run in O(log n/log log n) time using n² log log n/log n processors in the common-CRCW-PRAM, or in O(log n) time using n²/log n processors in the EREW-PRAM model. No sub-logarithmic time parallel algorithms have been previously reported for this problem