The subject of the project is related to a maximum facility location problem in three
dimensions. The goal is to find the largest circle that satisfies a set linear
restrictions on the sphere, that is inscribed in the convex polygon that represents the
intersection of a set of halfspaces determined by halfplanes through the center of the
sphere.
In [1] the optimal O(n) time algorithm is proposed to reduce
the problem of finding the largest circle to problem of finding the smallest circle spanning a set of n points. The
problem translates to finding the point on the halfsphere that minimize the maximum
distance to the points in the set given on the halfsphere. In other words, finding the
center of the minimum spherical cap that covers the set of n points.
In general case, when all the points lie in a sphere, the
problem has O(nlogn) complexity[1,2]. For the case in which
the points belong to a halfsphere the minimum covering cap problem can be solved in optimal
O(n) time in several ways. In [3] the solution is found as the
intersection of the halfsphere with the minimum spanning circle of the points. Another
option is to adapt to the halfsphere Megiddo's algorithm [4]. Finally, a linear
programming solution based on [1] can be used.
