Xref: utzoo comp.theory:489 comp.sources.wanted:11067 sci.math:10368 sci.math.num-analysis:655
Path: utzoo!attcan!uunet!samsung!usc!rutgers!aramis.rutgers.edu!paul.rutgers.edu!halldors
From: halldors@paul.rutgers.edu (Magnus M Halldorsson)
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: <Mar.21.18.06.37.1990.10806@paul.rutgers.edu>
Date: 21 Mar 90 23:06:38 GMT
References: <3078@soleil.oakhill.UUCP> <Mar.14.18.11.32.1990.2269@vanhalen.rutgers.edu> <18376@duke.cs.duke.edu>
Organization: Rutgers Univ., New Brunswick, N.J.
Lines: 22

In article <18376@duke.cs.duke.edu> avr@romeo.cs.duke.edu (A. V. Ramesh) writes:

> 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