On Efficient Approximation of the Maximum Distance to A Point Over an Intersection of Balls

In this paper we study the NP-Hard problem of maximizing the distance over an intersection of balls to a given point. We expand the results found in {funcos1}, where the authors characterize the farthest in an intersection of balls Q to the given point C₀ by constructing some intersection of halfspaces. In this paper, by slightly modifying the technique found in literature, we characterize the farthest in an intersection of balls Q with another intersection of balls Q₁. As such, going backwards, we are naturally able to find the given intersection of balls Q as the max indicator intersection of balls of another one Q₋₁. By repeating the process, we find a sequence of intersection of balls (Qᵢ)i ∈ Z, which has Q as an element, namely Q₀ and show that Q-∞ = B(C₀,R₀) where R₀ is the maximum distance from C₀ to a point in Q. As a final application of the proposed theory we give a polynomial algorithm for computing the maximum distance under an oracle which returns the volume of an intersection of balls, showing that the later is NP-Hard. Finally, we present a randomized method %of polynomial complexity which allows an approximation of the maximum distance.