I am looking for a reasonably efficient algorithm (and likely associated data structure) to accomplish the following in a reasonably low dimension (d<10; generally d=2 or 3):
Given a set of (potentially-overlapping!) spheres and a fixed bounding box, I wish to be able to:
- Query for the point within said bounding box that is farthest from any sphere.
- If there are multiple such points, an arbitrary choice is fine.
- A point within a sphere is at zero distance (that is, these are balls not hollow spheres.)
- If every point is within at least one sphere, erroring out here, or at 2.1., or returning an arbitrary point, are all fine.
- Ideally I am looking for an exact (up to numerical error) solution; a convergent approximation with error bounds is workable.
- Add new spheres to the set.
- If every point is now within at least one sphere, erroring out here or at 1.3. is fine.
Doing some initial preprocessing is fine.
(Note that the spheres can overlap, and can have varying radii.)
(Fixed bounding box, fixed bounding sphere, or simply an implicit convex hull. Any are workable, whichever is easiest.)
At a first glance this is deceptively similar to the Largest Empty Sphere problem (for which you can accomplish the above with a Veronoi diagram and some processing), however the change from "points to avoid" to "spheres to avoid" stops this from working and I haven't been able to figure out a straightforward extension.
Another approach that seems to work is to just repeatedly run the Largest Empty Sphere problem, starting with points to avoid at the center point of every sphere and each iteration adding the closest point across all spheres to the resulting current solution to the set of points to avoid, however this is expensive and doesn't have an obvious error bound.
Ditto, I look at this problem and go "this looks like the sort of thing you ought to be able to massage a BSP tree into doing", but most BSP algorithms I've seen tend more to be focused on nearest point, not farthest.