Re: Problem: Smallest sphere including all 3D points
- To: mathgroup at smc.vnet.net
- Subject: [mg16508] Re: [mg16471] Problem: Smallest sphere including all 3D points
- From: Robert Pratt <rpratt at math.unc.edu>
- Date: Tue, 16 Mar 1999 03:59:54 -0500
- Sender: owner-wri-mathgroup at wolfram.com
A quick-and-dirty approach yields a crude approximate solution. Let M be the "diameter" of the set (the largest distance between any pair of points in the set). Let P1 and P2 be any two points with distance(P1,P2)=M. Then every point is contained in the intersection of the two solid spheres of radius M centered at P1 and P2, respectively. A little algebra shows that a sphere of radius Sqrt[3]M/2, centered at the midpoint of the line segment joining P1 and P2, contains that intersection and hence contains all the points in the set. Since Sqrt[3]M/2 < M, this approach is (slightly) better than simply taking a sphere of radius M centered at P1. Rob Pratt Department of Mathematics The University of North Carolina at Chapel Hill CB# 3250, 331 Phillips Hall Chapel Hill, NC 27599-3250 rpratt at math.unc.edu http://www.math.unc.edu/Grads/rpratt/ On Sat, 13 Mar 1999, Barthelet, Luc wrote: > I was just asked by a friend how to find the smallest sphere that > would include all points from a set of 3D points. > It feels like finding a 3D convex hull and then finding the best sphere (??) > I would appreciate any complete solution or best set of pointers... > > Thank you, > > Luc Barthelet > General manager, Maxis > http://www.simcity.com <http://www.simcity.com> (we are > #1!)