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.
