3
$\begingroup$

I have $n$ points $(x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n)$ all located in the unit square $[0,1] \times [0,1]$. I am trying to compute the largest distance from a point in the unit square to the closest $(x_i,y_i)$. Is there some sort of formula for this quantity in terms of the $x_i,y_i$?

Thanks.

1 Answers 1

1

There is certainly a formula for this:

$\max_{(x,y)\in[0,1]\times[0,1]}\min_i\; d((x,y),(x_i,y_i))\;.$

But I suspect that what you're actually interested in is an algorithm for computing the value of that formula :-). I think your best bet will be to compute the Delaunay triangulation, take the maximum of the radii of the circumcircles, and compare that with the maximum on the boundary of the square, which I think you can get by intersecting the bisectors of the exterior Delaunay edges with the boundary and considering the corners of the square separately.

  • 0
    @Sorry, but I don't think anything much simpler will do. You can see that you need to look at each neighbourhood in detail by considering the case where the points form a regular lattice -- then you can slightly displace any one of them and thereby change where the maximal minimal distance occurs. But computing the Delaunay triangulation isn't that terrible, and I'm sure there's lots of free code out there that does it.2011-03-10