I have a set of points in 3d space (they all lie on the same plane, so this can be treated as a somewhat-2d problem). I need to compute the center of the set of points. Previously, I attempted to scan through all the points and compute the average cog (assuming each point had the same mass). This, however, does not work, because the points are not evenly distributed throughout the cloud. Many times, a large grouping of the points might lie toward one end of the cloud. I have thought of using a bounding rectangle or ellipse (again, I really have a 2d problem here because all the points lie on the same plane in 3d space). Which one is faster? Is there a better way than what I am thinking? Speed is very important for me here. I am looking for something that will go at least O(nlogn) or better. Does anyone have any good links to sites which describe how to do the above algorithms? I''ve looked around, but haven''t found much. I have no problem finding Bounding Boxes or Bounding Ellipsoids, but that''s not what I''m looking for. Oh, and I don''t want the algorithm to use an axis aligned bound, since that will throw things off. Any help on this would be greatly appreciated.. Thanks, Merowe

Depends on what type of "center" point you want. The approach you implemented does give a good value for the mass center, but sounds like you want a geometric center, which is more like a median. The rectangle or ellipse approach will give you a geometric center.

I would think calculating the ellipse would be a bit easier, maybe faster, as long as you''re happy to choose an axis-aligned bounding rectangle (aka axis aligned bounding box in 3D). This wouldn''t give you the optimum center point, but it would be close. If you want an oriented bounding rectangle (OBB) or an oriented ellipse, there''s more work to do because you have to determine which axis on the plane in which the points reside determines the orientation of the rectangle, and it takes some processing to calculate the axis.

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.