3 added 527 characters in body

I believe you are looking for the radius of a largest empty ball among your point set, a quantity which goes under the name of dispersion. This plays a role in robotics algorithms, e.g., LaValle's book. Here is a survey which might lead to other relevant references:

G. Rote , R.F. Tichy, "Quasi-Monte-Carlo methods and the dispersion of point sequences," Mathematical and Computer Modelling, 1996. (link)

Addendum. In repsonse to Jeff's query, let me recommend another direction, a very recent (2012) paper by Dumitrescu and Jiang, "On the largest empty axis-parallel box amidst $n$ points" (PDF download):

Our algorithm finds an empty axis-aligned box [in $\mathbb{R}^d$] whose volume is at least $(1 \epsilon)$ of the maximum in [...] time"

where I have elided a complicated complexity expression. This paper's 28 citations may prove useful to you.

2 added 12 characters in body

I believe you are looking for the radius of a largest empty ball among your point set, a quantity which goes under the name of dispersion. This plays a role in robotics algorithms, e.g., LaValle's book. Here is a survey which might lead to other relevant references:

G. Rote , R.F. Tichy, "Quasi-Monte-Carlo methods and the dispersion of point sequences," Mathematical and Computer Modelling, 1996. (link)

1

I believe you are looking for the largest empty ball among your point set, a quantity which goes under the name of dispersion. This plays a role in robotics algorithms, e.g., LaValle's book. Here is a survey which might lead to other relevant references:

G. Rote , R.F. Tichy, "Quasi-Monte-Carlo methods and the dispersion of point sequences," Mathematical and Computer Modelling, 1996. (link)