2
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\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
    Commented Feb 1, 2013 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
    Commented Feb 1, 2013 at 7:02

1 Answer 1

Reset to default
2
$\begingroup$

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)

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .