Xref: utzoo comp.theory:525 comp.sources.wanted:11140 sci.math:10428 sci.math.num-analysis:673 Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!tut.cis.ohio-state.edu!quanta.eng.ohio-state.edu!kcgl1.eng.ohio-state.edu!PAPAI From: PAPAI@kcgl1.eng.ohio-state.edu (Jonathan Papai) Newsgroups: comp.theory,comp.sources.wanted,sci.math,sci.math.num-analysis Subject: Re: Smallest circle around n points in space. Message-ID: <4589@quanta.eng.ohio-state.edu> Date: 26 Mar 90 22:20:24 GMT References: <3078@soleil.oakhill.UUCP> <18376@duke.cs.duke.edu> Sender: news@quanta.eng.ohio-state.edu Organization: Ohio State University Lines: 23 > 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. /Let A and B be the farthest points, and d = dist(A,B). /Consider the circle C1 where A and B are opposite points. Then that /circle is contained in the circle C2 of points of distance d from A. /Thus we can find a point inside C2 but outside C1 that is closer to /B than to A. / /Better yet, think of the points in the plane: / (0,0), (1-epsilon,1), (-1,-1), (0,2) /These form an (almost) perfect square. The points of max distance are /(0,0) and (0,2), but there's no way you can fit them on an enclosing /circle. / /Interesting problem. / /Magnus oops. the points farthest apart are (0,2) and (-1,-1)