Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!wuarchive!brutus.cs.uiuc.edu!rpi!wrf
From: wrf@mab.ecse.rpi.edu (Wm Randolph Franklin)
Newsgroups: comp.graphics
Subject: Re: smallest sphere enclosing a set of points
Message-ID: <25755B9D.37D@rpi.edu>
Date: 30 Nov 89 16:55:55 GMT
References: <5678@eos.UUCP>
Organization: Rensselaer Polytechnic Institute, Troy NY
Lines: 17
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).
The smallest enclosing circle is a well known problem. It can be solved
with a farthest point Voronoi diagram, see Preparata & Shamos. In 2-D
the time is NlgN. In 3-D, I don't know the time, but it might be N^2
since the closest point VorD is that complex. (The farthest point VorD
might be simpler.)
--
Wm. Randolph Franklin
Internet: wrf@ecse.rpi.edu (or @cs.rpi.edu) Bitnet: Wrfrankl@Rpitsmts
Telephone: (518) 276-6077; Telex: 6716050 RPI TROU; Fax: (518) 276-6261
Paper: ECSE Dept., 6026 JEC, Rensselaer Polytechnic Inst, Troy NY, 12180