Empty circle query algorithm

Question

I'm trying to come up with an algorithm that will do the following:

If a set of points is given, find for a query point the largest circle (with the query point as its center) that does not contain any points from the set.

So far I've thought of using a Voronoi diagram to find the areas (cells) that contain the points closest to a site point of the set, and then use the edge list from Voronoi to construct a trapezodial decomposition. From the decomposition I will be able to find which cell the query point lies in, and then the radius of the circle will be the distance from the query point to the point (site) of that cell. I think that the storage needed to create something like this is linear, since the Voronoi needs O(n) storage, and creating the trapezodial decomposition from the Voronoi can also be done with O(n) storage.

*Edit: Query time must be O(logn), which means I can't iterate through all of the points of the set one at a time.

Does this sound right, or am I missing something here?

Also, if anyone has some references that I could look at regarding this algorithm please let me know. Thanks :)

Answer 1

This question seems to be asking for the distance from the query point to the closest point to it in the set, so one way to answer it would be to find that closest point. One reasonably standard way of doing this would be with a http://en.wikipedia.org/wiki/K-d_tree, and this question in general is covered in http://en.wikipedia.org/wiki/Nearest_neighbour_search

Answer 2

That sounds overly complex. I don't even know what a Voroni diagram is, but assuming your points are all in a 2D plane (which seems to be the case since you mention a circle not a sphere) this is quite trivial:

Iterate through all the points and find the point which is closest to the query point. This distance is just Pythagorean's theorem sqrt((point_x - query_x)^2 + (point_y - query_y)^2). The smallest distance is the radius of the circle.