Finding Largest Empty Circles with Location Constraints contains the following theorem relating to the Largest Empty Sphere problem in 2-dimensions:

Given a set S of n points and a k-gon P, the largest circle C such that the center of C is within P and such that no point of S lies within C must be a circle centered at either: (1) a Voronoi vertex of V(S), (2) a vertex of the k-gon P, or (3) an intersection point of P and V(S)

The paper then goes on to describe an algorithm to find the circle C.

Are there any algorithms which can solve the problem with more complex constraints? In particular, if the k-gon P is replaced by:

  1. The intersection of a circle and a convex polygon?
  2. The intersection of an annulus and a convex polygon?

Also, is it possible to extend these algorithms to work in 3-dimensions (where polygon/circle/annulus become polyhedron/cylinder/annular cylinder)?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.