Computational Geometry

Department of Computer Science

Sphere Fitting in High Dimensions

A problem from shape fitting is finding the sphere which has the least sum of squares fit to a set of points. Most current algorithms for this use an iterative process, with randomized restarting.

In [2] and [3], we presented two geometric transformations and their derived algorithms (one of which is depicted in the picture) for high dimensions, which are not based on iterative techniques. Our algorithms are developed from some of the 2-dimensional ideas in [1], and have favorable time complexities in high dimensions.

Figure

The Riemann algorithm in R ^{ 3 }. A. The data points in red. B. The points transformed onto the hypersphere with lines connecting the original and transformed points. C. The points (with dimension 4 shown as color) on a 4-sphere. D. The weighted normal found. E. The final least sum of squares fit sphere found by the algorithm.

Related Papers

[1]

"Particle tracks fitted on the Riemann sphere", A. Strandlie, J. Wroldsen, R. Frühwirth, and B. Lillekjendlie. Comp. Phys. Comm, 131 pp. 95-108, 2000

"A review of fast circle and helix fitting", A. Strandlie, J. Wroldsen, R. Frühwirth, and B. Lillekjendlie. ACAT 2002, Moscow, Russia pdf presentation.[2]

"Transformations and Algorithms for Least Sum of Squares Hypersphere Fitting", M. Burr, A. Cheng, R. Coleman, and D. Souvaine, CCCG 04, Concordia Montreal, Canada ps file.[3]

"An Intuitive Approach to Measuring Protein Surface Curvature", R. Coleman, M. Burr, A. Cheng, A. C. Cheng and D. Souvaine,Proteins: Structure, Function, and Bioinformatics, 61:4, 2005, pp. 1068-1074.