Find the largest/maximal empty rectangle, i.e. with largest area, not containing given points.
coordinates of points to be avoided.
left and right resp. lower and upper constraints.
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.
rect the rectangle as a vector usable for
rect graphics function.
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.
HwB email: <firstname.lastname@example.org>
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.
Hmisc::largest.empty with a Fortran implementation of this code.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
N <- 100; set.seed(8237) x <- runif(N); y <- runif(N) R <- maxempty(x, y, c(0,1), c(0,1)) R # $area #  0.08238793 # $rect #  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)