Xref: utzoo comp.theory:535 comp.sources.wanted:11159 sci.math:10445 sci.math.num-analysis:679 Path: utzoo!attcan!uunet!samsung!zaphod.mps.ohio-state.edu!unix.cis.pitt.edu!dsinc!netnews.upenn.edu!grad2.cis.upenn.edu!aaron From: aaron@grad2.cis.upenn.edu (Aaron Watters) Newsgroups: comp.theory,comp.sources.wanted,sci.math,sci.math.num-analysis Subject: Re: Smallest circle around n points in space. Message-ID: <22381@netnews.upenn.edu> Date: 28 Mar 90 13:18:11 GMT References: <3078@soleil.oakhill.UUCP> <18376@duke.cs.duke.edu> <4589@quanta.eng.ohio-state.edu> Sender: news@netnews.upenn.edu Reply-To: aaron@grad2.cis.upenn.edu.UUCP (Aaron Watters) Organization: University of Pennsylvania Lines: 19 >> 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. > >/I think not. [His example follows]... In fact there is an example where niether of the two points at greatest distance from eachother lie on the smallest circle containing all the points. Consider {A,B,C} to be the vertices from an equilateral triangle. The smallest circle containing these points is X, the unique circle intersecting each of the points. Draw a diameter for X parallel to AB, and let D and E be its endpoints. Clearly from the set {A..E}, D and E are the two points at greatest distance from eachother. Further, we can move D and E towards the interior of X by a sufficiently small amount such that they remain the most distant points but X remains the smallest circle containing {A,B,C,D,E}. -aaron.