Description Usage Arguments Details Value Note Author(s) References See Also Examples

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

1 |

`x, y` |
coordinates of points to be avoided. |

`ax, ay` |
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.

List with `area`

and `rect`

the rectangle as a vector usable for
the `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: <[email protected]>

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
# [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)
``` |

adagio documentation built on May 18, 2018, 1:08 a.m.

Embedding an R snippet on your website

Add the following code to your website.

For more information on customizing the embed code, read Embedding Snippets.