Home Introduction Algorithm Implementation References

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.