ephrem@oakhill.UUCP (Ephrem Chemaly) (03/14/90)
Does anyone know of an algorithm/method to find the smallest circle (center,radius) that includes n points in space. Also of less interest is the smallest ellipse that includes all the points. I would like to have algorithms, code, references, etc. Thanks in advance Ephrem A. Chemaly oakhill!soleil!ephrem@cs.utexas.edu (512)891-2760 MOTOROLA Inc. 6501 W. William Cannon Dr. MS OE28 Austin, TX 78735 U.S.A.
novick@svax.cs.cornell.edu (Mark B. Novick) (03/15/90)
If you are concerned with the 2-d case, take a look at Preparata and Shamos' book Computational Geometry. They call the problem the smallest enclosing circle problem, and give efficient algorithms to solve it. Some of them are based on Voronoi diagram techniques. The asymptotically fastest algorithm they give runs in theta(n) time, where n is the number of points.
bohannon@vanhalen.rutgers.edu (Philip Bohannon) (03/15/90)
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.
avr@romeo.cs.duke.edu (A. V. Ramesh) (03/22/90)
In article <Mar.14.18.11.32.1990.2269@vanhalen.rutgers.edu>, 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.
halldors@paul.rutgers.edu (Magnus M Halldorsson) (03/22/90)
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
mahajan@fornax.UUCP (Sanjeev Mahajan) (03/22/90)
In article <18376@duke.cs.duke.edu>, avr@romeo.cs.duke.edu (A. V. Ramesh) writes: > In article <Mar.14.18.11.32.1990.2269@vanhalen.rutgers.edu>, bohannon@vanhalen.rutgers.edu (Philip Bohannon) writes: There is an O(nlog n) algorithm for the problem, any standard computational geometry reference should have this algorithm. Sanjeev
darrenv@microsoft.UUCP (Darren VENGROFF) (03/23/90)
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]reino@cs.eur.nl (Reino de Boer) (03/23/90)
halldors@paul.rutgers.edu (Magnus M Halldorsson) writes: >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. Please correct me if I'm wrong, but aren't (-1,-1) and (0,2) the points we're looking for? Reino -- Reino R. A. de Boer "We want to build the right product right, right?" Erasmus University Rotterdam ( Informatica ) e-mail: reino@cs.eur.nl
sartin@hplabsz.HPL.HP.COM (Rob Sartin) (03/23/90)
In article <18376@duke.cs.duke.edu> avr@romeo.cs.duke.edu (A. V. Ramesh) writes: >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) I don't think that's correct. D could be equal to the distance between P1 and P2 of all other points are contained within the circle with center halfway between P1 and P2 and radius distance(P1, P2). D could be as large as 2 * distance(P1, P2) if there exists P3 with distance(P1,P2) = distance (P2, P3) = distance(P1, P3)/2 (i.e. P3 on the line defined by P1, P2 at distance distance(P1, P2) on the opposite side of P2 from P1). So: distance(P1, P2) <= D <= 2 * distance(P1, P2) where P1 and P2 are the points with greatest separation. I'm not sure how this observation helps in the solution of the problem. I haven't even thought about that. Rob Sartin uucp: hplabs!sartin "Some may say that I have gone astray. internet: sartin@hplabs.hp.com How would they know? They never follow."
jagversm@praxis.cs.ruu.nl (Koen Versmissen) (03/23/90)
In article <1990Mar22.195123.2849@cs.eur.nl> reino@cs.eur.nl (Reino de Boer) writes: >halldors@paul.rutgers.edu (Magnus M Halldorsson) writes: >>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. >Please correct me if I'm wrong, but aren't (-1,-1) and (0,2) the points >we're looking for? No. If the four points are to form an (almost) perfect square, the third one should clearly be (-1, 1) instead of (-1,-1), so we _are_ looking for (0,0) and (0,2). ------------------------------------------------------------------------------ Koen Versmissen Rijksuniversiteit Utrecht (jagversm@praxis.cs.ruu.nl) The Netherlands
john_kolen@toto.cis.ohio-state.edu (03/24/90)
In article <5021@hplabsz.HPL.HP.COM> sartin@hplabs.hp.com writes: >In article <18376@duke.cs.duke.edu> avr@romeo.cs.duke.edu (A. V. Ramesh) writes: >>2. The bounds of the diameter of this circle are >> distance (P1,P2) < D < sqrt(3) distance(P1,P2) >I don't think that's correct. D could be equal to the distance between >P1 and P2 of all other points are contained within the circle with >center halfway between P1 and P2 and radius distance(P1, P2). D could >be as large as 2 * distance(P1, P2) if there exists P3 with >distance(P1,P2) = distance (P2, P3) = distance(P1, P3)/2 (i.e. P3 on >the line defined by P1, P2 at distance distance(P1, P2) on the opposite >side of P2 from P1). If this was true, then (P1,P3) would be the maximal pair, a contradiction. Given that (P1,P2) is the maximal pair, all points must lie in the intersections of the circles centered at P1 and P2 with radius distance(P1,P2). -- John Kolen (kolen-j@cis.ohio-state.edu)|computer science - n. A field of study Laboratory for AI Research |somewhere between numerology and The Ohio State Univeristy |astrology, lacking the formalism of the Columbus, Ohio 43210 (USA) |former and the popularity of the latter
PAPAI@kcgl1.eng.ohio-state.edu (Jonathan Papai) (03/27/90)
> 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)
aaron@grad2.cis.upenn.edu (Aaron Watters) (03/28/90)
>> 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.