Name
Title | ||
|---|---|---|
An accurate and efficient algorithm for determining minimum circumscribed circles and spheres from discrete data points |
Abstract | ||
|---|---|---|
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(nlogn) through a large number of computational test cases. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1016/j.cad.2012.07.014 | Computer-Aided Design |
Keywords | Field | DocType |
mc circle,essential subset,large data,entire data,related data exchange scheme,ip point subset,unique ip point subset,minimum circumscribed circle,input data point,discrete data point,unique four-point subset,efficient algorithm,combinatorial search,minimax location problem | Data point,Discrete mathematics,Mathematical optimization,Search algorithm,Data exchange,Algorithm,SPHERES,Test case,Combinatorial search,1-center problem,Mathematics,Computational complexity theory | Journal |
Volume | Issue | ISSN |
45 | 2 | 0010-4485 |
Citations | PageRank | References |
2 | 0.45 | 5 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hsi-yung Feng | 1 | 152 | 15.49 |
| Dawit H. Endrias | 2 | 4 | 0.96 |
| M. Abu Taher | 3 | 2 | 0.45 |
| Hao Song | 4 | 2 | 0.45 |