Algorithm

 

Home Introduction Algorithm Implementation References

Given a convex polygon P=(P1,P2,...,Pn) on a halfsphere, consider the planes determined by the edges of the polygon and the center O of the sphere. Associate to each of these planes, which can be represented as planes tangent to the cone determined by the largest inscribed circle and the center of the sphere, its polar point Qi that is the intersection of the sphere with the external normal ray to the plane through the origin.

1.jpg (35650 bytes)

Any circle C on the half sphere defines a cone A that has a polar cone A* that intersects the sphere circle C is inscribed in the polygon P=(P1,P2,...,Pn) if the polar circle C* encloses points Q1,Q2,...,Qn. The relation between the aperture angles of cones a* = p - d allows to reduce the problem of finding the largest circle C inscribed in polygon P to the problem of finding the smallest circle C* containing Q1,Q2,...,Qn, that can be determined by the point belonging to the polyhedral region which minimizes the distance to the center of the halfsphere, considering the segment line that joins it to the center and intersecting it with the halfsphere.

Let us start looking at the two dimensional case. Consider n points Q1,Q2,...,Qn on a halfcircle.

2.jpg (20353 bytes)

The halfplanes defined by the lines through Q1,Q2,...,Qn tangent to the circle have an intersection point N, that represents a vertex of the polygonal region and minimizes the distance to the center of the circle. That is why the fact that points lie on a halfcircle are crucial. All the halfplanes are redundant except two of them corresponding to the first and the last point.  The center K of the minimum spanning arc of the points is the intersection of the segment line and the line through the points O and N, since the two triangles OQ1N and OQnN are congruent., the line ON bisects the minimum arc containing the points.

3.jpg (28615 bytes)

The three dimensional case is analogous. The polyhedral region is formed by the planes tangent to the halfsphere the points Q1,Q2,...,Qn ( polar to  P1,P2,...,Pn). The region is a pyramid because all the planes intersect in an unique point or vertex. The vertex of the pyramid is the same as the vertex of the tangent cone determined by the minimum spanning circle because the planes forming the pyramid are tangent to the sphere at the points belonging to the boundary of the minimum covering cap and these are tangent to the cone. Therefore, the center of the minimum spanning circle, the center of the sphere and the vertex of the polyhedral region, that minimizes the distance to the center of the sphere, lie on a line.

Thus the largest circle inscribed in a convex polygon given on a halfsphere can be found in optimal O(n) time.