Geometric algorithms for finding a point in the intersection of balls (Q827997)

Do \(n\) balls in Euclidean \(m\)-space given by their centres and radii intersect? If so determine an intersection point. This task may be accomplished (after \(0(n^2)\) preprocessing) in 2-space in \(O(n^3)\) time by a naive method which checks intersection points of pairs of boundary circles, and in \(O(n^2\log n)\) time by a more involved method checking this intersection along the boundary circle of (possibly) each ball. In higher dimensions, the task may similarly be reduced to dimension \(m-1\), yielding a recursive method of \(O(n^{2m-4}(nm^2+m^3+n^2\log n))\).