Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!uunet!munnari.oz.au!murtoa.cs.mu.oz.au!ditmela!pleiades!dbrmelb!davidp From: davidp@dbrmelb.dbrhi.oz (David Paterson) Newsgroups: comp.graphics Subject: Re: smallest sphere enclosing a set of points Message-ID: <664@dbrmelb.dbrhi.oz> Date: 3 Dec 89 21:53:08 GMT References: Organization: CSIRO, Div. Building Constr. and Eng'ing, Melb., Australia Lines: 111 In article , rwang@caip.rutgers.edu (Ruye Wang) writes: > > I need the solution for the following problem: > find the smallest sphere that encloses a set of given points, in both > 2-D and 3-D (or even n-D, if you like). > > I though it was a easy problem. But then I realized that it was not > that easy, at least to me. > > If anyone knows the answer, would you please email it to me? Thank you > very much! Here are two solution methods. A slow one that works in n-D and a fast one that works in 2-D and possibly 3-D. FIRST METHOD (Very slow) For all sets of n+1 points Find the smallest n-sphere containing these n+1 points End for Find the largest of these n-spheres Stop The smallest n-sphere containing n+1 points is found iteratively (from the smallest n-1 sphere containing n points) as follows: For all sets of n points Find the smallest (n-1)-sphere containing these points End for Find the largest of these (n-1)-spheres Consider an n-sphere with the same centre and radius If the excluded point lies within this n-sphere then The required n-sphere is this n-sphere Else The required n-sphere is the n-sphere touching all n+1 points End if Return The smallest 1-sphere containing 2 points (call these P1 and P2) has centre (P1+P2)/2 and radius |P1-P2|/2. To find an n-sphere touching n+1 points requires the simultaneous solution of n+1 quadratic equations. This can be solved by Newton's method. SECOND METHOD (very fast) EXAMPLE IN 2-DIMENSIONS **1-D Part** For all sets of 2 points (call these P1,P2) Find the smallest circle containing these two points End for Find the largest of these circles **2-D Part** For all points outside this circle (call this P3) If no such points Stop Find the circle touching P1,P2 & P3 End for Find the largest of these circles 10 For all points outside this circle (call this P4) If no such points Stop Find the smallest circle containing P3 & P4 Find which of P1,P2 is outside this circle (call this P5) Find the circle touching P3,P4 & P5 End for Find the largest of these circles Set P1 <-- P5; P2 <-- P3; P3 <-- P4 Go to 10 EXAMPLE IN 3-DIMENSIONS **1-D Part** For all sets of two points (call these P1,P2) Find the smallest sphere containing these two points End for Find the largest of these spheres **2-D Part** For all points outside this sphere (call this P3) If no such points Stop Find the smallest sphere containing P1,P2 & P3 End for Find the largest of these spheres **3-D Part** For all points outside this sphere (call this P4) If no such points Stop Find the sphere touching P1,P2,P3 & P4 End for Find the largest of these spheres 10 For all points outside this sphere (call this P5) If no such points Stop Find which of P1,P2,P3 is furthest from P5 (call this P6) Find the smallest sphere containing P4,P5 & P6 Find which of P1,P2,P3 is outside this sphere (call this P7) Find the sphere touching P4,P5,P6 & P7 End for Find the largest of these spheres Set P1 <-- P6; P2 <-- P7; P3 <-- P4; P4 <-- P5 Go to 10 Note: I know that the 2-D example above always gives the correct answer but I can't be 100% sure that the 3-D example does. ------------------------------------------------------------------- David Paterson CSIRO B,C&E Highett Victoria 3190 There are many people out there who have more money than sense. Few of them are rich. ------------------------------------------------------------------ Brought to you by Super Global Mega Corp .com