Apollonius tenth problem as a point location problem

Deok Soo Kim, Donguk Kim, Kokichi Sugihara, Joonghyun Ryu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

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.

Original languageEnglish
Title of host publicationComputational Science - ICCS 2001 - International Conference, 2001, Proceedings
EditorsVassil N. Alexandrov, Jack J. Dongarra, Benjoe A. Juliano, René S. Renner, C.J. Kenneth Tan
PublisherSpringer Verlag
Pages728-737
Number of pages10
ISBN (Print)3540422323, 9783540422327
DOIs
StatePublished - 2001 Jan 1
EventInternational Conference on Computational Science, ICCS 2001 - San Francisco, United States
Duration: 2001 May 282001 May 30

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2073
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

OtherInternational Conference on Computational Science, ICCS 2001
CountryUnited States
CitySan Francisco
Period01/05/2801/05/30

Fingerprint Dive into the research topics of 'Apollonius tenth problem as a point location problem'. Together they form a unique fingerprint.

  • Cite this

    Kim, D. S., Kim, D., Sugihara, K., & Ryu, J. (2001). Apollonius tenth problem as a point location problem. In V. N. Alexandrov, J. J. Dongarra, B. A. Juliano, R. S. Renner, & C. J. Kenneth Tan (Eds.), Computational Science - ICCS 2001 - International Conference, 2001, Proceedings (pp. 728-737). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2073). Springer Verlag. https://doi.org/10.1007/3-540-45545-0_84