Xref: utzoo comp.theory:486 comp.sources.wanted:11065 sci.math:10367 sci.math.num-analysis:654 Path: utzoo!attcan!uunet!samsung!usc!rutgers!mcnc!duke!romeo!avr From: avr@romeo.cs.duke.edu (A. V. Ramesh) 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: <18376@duke.cs.duke.edu> Date: 21 Mar 90 21:47:05 GMT References: <3078@soleil.oakhill.UUCP> Sender: news@duke.cs.duke.edu Lines: 29 In article , bohannon@vanhalen.rutgers.edu (Philip Bohannon) writes: > Someone around here found a reference that claims to do it in On^2 > time. It looks like it might be simplex method type stuff. Do you > still need a reference? > -- > .sig? No, it's too hard to quit once you start. I gave this problem thought. Some of the conclusions that i drew which i feel are right are as follows : 1. There is a unique solution (in terms of radius/centre) 2. The bounds of the diameter of this circle are distance (P1,P2) < D < sqrt(3) distance(P1,P2) where P1 and P2 are the pair of points that are separated by a distance larger than any other given pair of points. (i.e. maximum apart) 3. At least two of the points lie on the circle. In general three of the n points will lie on the circle. When the former is the case, it is a question of finding the pair of points P1 and P2 and it can be done in n(n-1)/2 tries. In the latter case it can be done in n(n-1)(n-2)/6 times so it will be O(n^3) time. I haven't come up with better than that. 4. I think that the two points farthest apart must lie on the circle but i am not sure; if that is the case then this can be done in O(n^2) time.