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 Brought to you by Super Global Mega Corp .com