Geometric Algorithms for Finding a Point in the Intersection of Balls

Abstract

We consider a problem of finding a point in the intersection of n balls in the Euclidean space E^m. For the case m=2 we suggest two algorithms of the complexity O(n^2 logn) and O(n^3 ) operations, respectively. For the general case we suggest an exact polynomial recursive algorithm which uses the orthogonal transformation of the space E^m.