EXACT ALGORITHMS FOR CIRCLES ON THE SPHERE

Abstract

We describe exact representations and 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 tools support robust and efficient operations on maps overs the sphere, such as point location and map overlay, and provide a reliable framework for robotics, geographic information systems, and other geometric applications.