Exact algorithms for circles on the sphere

Abstract

We develop exact algorithms for geometric operations on general circles and circular arcs on the sphere, using integer homogeneous coordinates. The algorithms include testing a point against a circle, computing the intersection of two circles, and ordering three arcs out of the same point. These operations allow robust manipulation of maps on the sphere, providing a reliable framework for GIS, robotics, and other geometric applications.