Xref: utzoo comp.theory:494 comp.sources.wanted:11081 sci.math:10386 sci.math.num-analysis:665 Path: utzoo!attcan!uunet!microsoft!darrenv From: darrenv@microsoft.UUCP (Darren VENGROFF) Newsgroups: comp.theory,comp.sources.wanted,sci.math,sci.math.num-analysis Subject: Re: Smallest circle around n points in space. Keywords: circle, distance, math, algorithms Message-ID: <53709@microsoft.UUCP> Date: 22 Mar 90 19:02:24 GMT References: <3078@soleil.oakhill.UUCP> <18376@duke.cs.duke.edu> Reply-To: darrenv@microsoft.UUCP (Darren VENGROFF) Organization: Microsoft Corp., Redmond WA Lines: 31 This problem can be solved in O(NlogN) time. An algorithm to do so is described in _Computational Geometry an Introduction_ by Preparata and Shamos on pp. 248-51. The basic idea is as follows: The smallest enclosing circle has at least two points of the original set on its boundary. If there are two points on the boundry then the circle is found be computing the diameter of the set (the two furthest points from each other), which can be done in O(NlogN) and then seeing if all of the other points in the set lie withing the circle which has these two points as the endpoints of a diameter. This takes O(N). If all points lie in this circle then we are done. If all the points do not lie in the circle we constructed, then construct a farthest point Voronoi diagram of the set. This takes O(NlogN). The diagram contains only O(N) points and one of these must be the center of the smallest enclosing circle. All we have to do is find the maximum over these points of the distance from the point to the three points in the original set that determine it. This clearly takes O(N). If you want more details on this algorithm your best bet is to refer to the source I mentioned above, which discusses the terminology more rigorously than I have space to here but doesn't describe the overall algorithm in much more detail than I just did, or refer to Shamos' Ph.D. thesis from the Yale Dept. of C.S. (1978). -- Darren Erik Vengroff [darrenv@microsoft.UUCP]