maxempty function

Maximally Empty Rectangle Problem

Find the largest/maximal empty rectangle, i.e. with largest area, not containing given points.

maxempty(x, y, ax = c(0, 1), ay = c(0, 1))

Arguments

• x, y: coordinates of points to be avoided.
• ax, ay: left and right resp. lower and upper constraints.

Details

Find the largest or maximal empty two-dimensional rectangle in a rectangular area. The edges of this rectangle have to be parallel to the edges of the enclosing rectangle (and parallel to the coordinate axes). `Empty' means that none of the points given are contained in the interior of the found rectangle.

Returns

List with area and rect the rectangle as a vector usable for the rect graphics function.

Note

The algorithm has a run-time of O(n^2) while there are run-times of O(n*log(n)) reported in the literature, utilizing a more complex data structure. I don't know of any comparable algorithms for the largest empty circle problem.

Author(s)

HwB email: hwborchers@googlemail.com

References

B. Chazelle, R. L. Drysdale, and D. T. Lee (1986). Computing the Largest Empty Rectangle. SIAM Journal of Computing, Vol. 15(1), pp. 300--315.

A. Naamad, D. T. Lee, and W.-L. Hsu (1984). On the Maximum Empty Rectangle Problem. Discrete Applied Mathematics, Vol. 8, pp. 267--277.

See Also

Hmisc::largest.empty with a Fortran implementation of this code.

Examples

N <- 100; set.seed(8237)
x <- runif(N); y <- runif(N)
R <- maxempty(x, y, c(0,1), c(0,1))
R
# $area
# [1] 0.08238793
# $rect
# [1] 0.7023670 0.1797339 0.8175771 0.8948442

## Not run:

plot(x, y, pch="+", xlim=c(0,1), ylim=c(0,1), col="darkgray",
      main = "Maximally empty rectangle")
rect(0, 0, 1, 1, border = "red", lwd = 1, lty = "dashed")
do.call(rect, as.list(R$rect))
grid()
## End(Not run)