Path: utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!mailrus!cornell!uw-beaver!ubc-cs!cs!shermer
From: shermer@cs.sfu.ca (Tom Shermer)
Newsgroups: comp.graphics
Subject: Re: smallest sphere enclosing a set of points
Summary: Can be done in linear time
Message-ID: <160@fornax.cs.sfu.ca>
Date: 5 Dec 89 19:47:36 GMT
References: <Nov.28.22.18.43.1989.8200@caip.rutgers.edu> <5678@eos.UUCP>
Reply-To: shermer@alula.UUCP (Tom Shermer)
Organization: School of Computing Science, SFU, Burnaby, B.C. Canada
Lines: 44

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).
>

This problem can be solved in linear time (in any fixed dimension)
by the technique of prune-and-search (sometimes called ``Megiddo's
Technique''), either directly or by first converting the problem
to a linear program.  The most relevant reference (for 2d & 3d) is:

Linear-time Algorithms for Linear Programming in R^3 and Related Problems,
	Nimrod Megiddo, SIAM J. Comput, v. 12, No. 4, Nov 1983, pp. 759-776.


Other related references:

Linear time algorithms for two- and three- variable linear programs,
	M.E. Dyer, SIAM J. Comput, v. 13, 1984, 31-45.

On a multidimensional search technique and its application to the
Euclidean one-center problem,
	M. E. Dyer, Dept. Math and Stats TR, Teesside Polytechnic,
	Middlesbrough, Cleveland TS1 3BA, UK, 1984.

Linear programming in linear time when the dimension is fixed,
	N. Megiddo, JACM 31, 1984, 114-127

The weighted Euclidean 1-center problem,
	N. Megiddo, Mathematics of Operations Research 8, 1983, 498-504

On the Ball Spanned by Balls
	N. Megiddo, manuscript (this may have appeared in the literature
	by now)



				Tom Shermer
				School of Computing Science
				Simon Fraser University
				Burnaby, BC, Canada  V5A 1S6
				(604) 291-3601
				shermer@cs.sfu.ca