Path: utzoo!attcan!uunet!mcsun!inria!geocub!pelegrin
From: pelegrin@geocub.greco-prog.fr
Newsgroups: comp.graphics
Subject: Re: smallest sphere enclosing a set of
Message-ID: <1526@geocub.greco-prog.fr>
Date: 3 Dec 89 13:30:03 GMT
References: <28@<Nov> <207400043@s.cs.uiuc.edu>
Sender: news@geocub.greco-prog.fr
Reply-To: pelegrin@goofi.UUCP (Uncle Ben's)
Organization: ENSERB 351 Cours de la Liberation 33405 TALENCE tel 56 84 65 00
Lines: 66

>/* Written  9:18 pm  Nov 28, 1989 by rwang@caip.rutgers.edu in s.cs.uiuc.edu:comp.graphics */
>/* ---------- "smallest sphere enclosing a set of" ---------- */
>
>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
>/* End of text from s.cs.uiuc.edu:comp.graphics */

  This is a small algorithm, which has some weaknesses :

    Xmin = Ymin = Zmin = +infinite
    Xmax = Ymax = Zmax = -infinite
/* Compute the bounding volume */
    For each point in set {
      If Xpt < Xmin
        Xmin = Xpt
      If Ypt < Ymin
        Ymin = Ypt
      If Ypt < Ymin
        Ymin = Ypt
      If Xpt > Xmax
        Xmax = Xpt
      If Ypt > Ymax
        Ymax = Ypt
      If Zpt > Zmax
        Zmax = Zpt
    }
/* Compute the APPROXIMATE center */
    CX = Xmin + (Xmax - Xmin) / 2
    CY = Ymin + (Ymax - Ymin) / 2
    CZ = Zmin + (Zmax - Zmin) / 2
/* Now calculate the Minimum and Maximum diameters */
    Dmin = +infinite
    Dmax = -infinite
    if (Xmax - Xmin > Dmax)
      Dmax = Xmax - Xmin
    if (Ymax - Ymin > Dmax)
      Dmax = Ymax - Ymin
    if (Zmax - Zmin > Dmax)
      Dmax = Zmax - Zmin
    if (Xmax - Xmin < Dmin)
      Dmin = Xmax - Xmin
    if (Ymax - Ymin < Dmin)
      Dmin = Ymax - Ymin
    if (Zmax - Zmin < Dmin)
      Dmin = Zmax - Zmin
    Dmin = Dmin * sqrt (3)
    Dmax = Dmax * sqrt (3)
/* To follow, Compute by scattering of a better diameter */
/* You can first compute the distance of all points to   */
/* the center of the sphereto optimize the process       */
    for i = 1 to XX { /* Choose it */
      Dtmp = (Dmin + Dmax) /2
      if (all points within the sphere of diameter Dtmp)
        Dmax = Dtmp
      else
        Dmin = Dtmp
    }

Disclaimer : This is just an idea...

                      f.p.


Brought to you by Super Global Mega Corp .com