computational geometry - center of a cluster of points and track shape -

i have plots of points this.

the tracks these points form can circle or ellipse. center of circular tracks in 2 images above different.

how can find center point of these tracks (circular/elliptical)? want find (x,y) coordinates center, not necessary has point that's in plotted data set. i.e., don't want medoid.

edit: also, is there anyway can find equation circle/ellipse envelopes majority of these points? in elliptical track, i've added ellipse envelopes points on track. values calculated trial , error. center calculated eye balling plot. how can programmatically?

smallest circle problem , here paper (pdf download available) on smallest ellipse problem. both have o(n) algorithms , should able provide formula circle , area can center. however, focus on enclosing of points. solve issue you'll need remove number of bounding points, should algorithms well. unfortunately, it's pretty qualifies enough solution.

a fast , simple randomized solution is:

1. randomly divide set of points k sets of n/k points each.
2. run smallest circle/ellipse algorithm each set
3. for each of k sets, pick @ least 1 no more m bounding points remove main point set.
4. return step 1, t times.
5. return result of circle/ellipse algorithm on remaining points.

the algorithm removes between k , mk bounding points every pass @ cost of o(n). purpose you'll want remove percentage of bounding points, 1-25% seems starting point. solution assumes k small compared n, otherwise you'll removing many points.

a slower better algorithm useful in case want repeated remove 1 or of bounding point smallest elipse, recalculate smallest ellipse, remove bounding points again.

you can having parent node bounding points (points stored set easy faster removal) of smallest enclosing ellipse of it's children. maximum number of bounding points should no more k (which i'm thinking 9 ellipse, compared 3 circle). removing point data structure @ o(k log n) requires recalculating smallest circle, o(k) each parent affected o(log n). removing m points data structure should o(mk log n). might want consider calculating area of ellipse every every removed point , removing every point cost of o(nk log n) until have 3 points left. analyze area data determine ellipse should used. simple result use ellipse has area closest average area of of ellipses created, may not seek. might slow, in case recommend single pass of faster algorithm.