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.

  • $\begingroup$ 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$. $\endgroup$ – Robert Israel Feb 1 '13 at 6:38
  • $\begingroup$ @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? $\endgroup$ – ayas Feb 1 '13 at 7:02

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)


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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