Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I randomly scatter $N$ points on a bounded rectangular plane $P$ with dimensions $A \times B$. To be more specific, for $N$ iterations, I choose a real number $x \in [0, A]$ and a real number $y \in [0, B]$, and place my point at the coordinates $(x, y)$.

Let $R$ be the radius of some circle I place somewhere on the plane $P$ that encloses no points. What is the probability distribution for the maximum permissible size of $R$?

Note - I specified $P$ to be a rectangular plane but, please, let it be any shape you wish if you can answer my question.

share|improve this question
Is your circle supposed to be contained in $P$, or is it just the centre that must be in $P$ (in which case you're just maximizing the minimum distance to the chosen points)? In either case, it's very unlikely that you could get a useful closed form for general $N$. –  Robert Israel Feb 1 '13 at 6:38
@Robert Israel The circle (handle boundary points as you wish) should be contained in $P$. And you're probably right that there is unlikely to be a closed form expression. What if, however, we make $P$ a larger circle? –  ayas Feb 1 '13 at 7:02
add comment

1 Answer 1

up vote 2 down vote accepted

The largest empty ball in a point set is known in the literature as the dispersion; see, for example, this definition. This was explored a bit in a previous MO question, "Finding the most-isolated point in a high-dimensional cube." Here is a paper that explores dispersion. This could serve to forward-search in Google Scholar. Or you could hope that Günter Rote, who is now participating in MO, will comment directly:

Rote, Tichy. "Quasi-Monte-Carlo methods and the dispersion of point sequences" Mathematical and Computer Modelling 23 (1996), 9-23. (ACM link)

See also the recent paper on largest empty rectangles:

Dumitrescu, Jiang. "On the largest empty axis-parallel box amidst $n$ points." 2012. (PDF download)

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.