An accurate and efficient algorithm for determining minimum circumscribed circles and spheres from discrete data points

作者：Feng Hsi Yung^*; Endrias Dawit H; Abu Taber M; Song Hao

来源：Computer-Aided Design, 2013, 45(2): 105-112.

DOI：10.1016/j.cad.2012.07.014

• Minimum circumscribed circle
• Minimum circumscribed sphere
• Combinatorial search
• Form error evaluation
• Minimax location problem

This paper presents a novel combinatorial search algorithm for determining minimum circumscribed (MC) circles and spheres from discrete data points. The presented algorithm is able to efficiently identify the essential subset of the input data points to construct the MC circle/sphere for the entire data set. The common issue of computational explosion for a large data set due to a greatly increased number of combinatorial searches is thus of no concern. The main feature of this work is the derivation of an innovative geometric property, named the Integrated Property (IP), for a unique three-point subset in 2D or a unique four-point subset in 3D. The significance is that the MC circle/sphere for the identified IP point subset is in fact the MC circle/sphere for the entire data set. As the unique IP point subset can always be found, the presented algorithm is guaranteed to yield exact MC circle/sphere solutions. A related data exchange scheme is formulated to efficiently identify the unique IP point subset from the input point set. The expected computational complexity of the search algorithm is quantified to be O(n log n) through a large number of computational test cases.

• 出版日期2013-2