Let A and B be two sets of points, each consisting of n points, all lying in unit square S. I am trying to find a efficient algorithm for finding the largest disk D such that:
(i) The center of D lie in S.
(ii) The interior of D is empty.
(iii) The boundary of D touches atleast one point from A and one point from B.
Im having a real problem with this question. Any hints will be usefull.
To complete Yves Daoust's partial solution, compute the Voronoi diagram (which is dual to the Delaunay triangulation) bounded by S. We can find an optimal circle center at some Voronoi vertex (i.e., a point in the interior of S where the nearest three points in A ∪ B are equidistant, or a point on the boundary of S where the nearest two points in A ∪ B are equidistant) where one of the nearest points is in A and another is in B.
Such a vertex is clearly feasible as a center. If we try to take any other center, then we can apply stark's observation. This center must be equidistant from a point in A and a point in B, so assuming that A ∩ B is empty (I really don't want to think about the degenerate cases; we can always perturb our way out), we can slide the center along the perpendicular bisector of AB until we hit either a third point or the boundary.