Apollonius Tenth Problem as a Point Location Problem

摘要

Given a set of three circles in a plane, we want to find a circumcircle to these given circles called generators. This problem is well known as Apollonius Tenth Problem and is often encountered in geometric computations for CAD systems. This problem is also a core part of an algorithm to compute the Voronoi diagram of circles. We show that the problem can be reduced to a simple point-location problem among the regions bounded by two lines and two transformed circles. The transformed circles are produced from the generators via linear fractional transformations in a complex space. Then, some of the lines tangent to these transformed circles corresponds to the desired circumcircle to the generators. The presented algorithm is very simple yet fast. In addition, several degenerate cases are all incorporated into one single general framework.