mp1u+@andrew.cmu.edu (Michael Portuesi) (04/01/88)
I am looking for an efficient algorithm that, given a set of points, finds the
smallest circle enclosing them and its center. Pseudocode, actual code (C,
Pascal or Lisp preferable), or references to published material all would be
appreciated.
--M
Michael Portuesi / Carnegie Mellon University
ARPA/UUCP: mp1u+@andrew.cmu.edu BITNET: rainwalker@drycas
"Paradise is exactly like where you are right now...only much, much better"
--Laurie Anderson, "Language is a Virus"roy@phri.UUCP (Roy Smith) (04/01/88)
mp1u+@andrew.cmu.edu (Michael Portuesi) writes: > I am looking for an efficient algorithm that, given a set of points, finds > the smallest circle enclosing them and its center. Take a look at: %A R. Sedgewick %T Algorithms %D 1983 %I Addison-Wesley %C Reading, Mass. Chapter 25 (Finding the Convex Hull) is devoted to the problem of finding the smallest convex polygon which encloses a set of points (in a plane, which I assume is what you're talking about). Once you have that, it seems intuitively obvious (i.e. I havn't actually sat down to prove it) that you've at least narrowed the problem down a lot. For example, at least 2 of the verticies of the convex hull must lie on the circle (consider 3 points which form an equilateral triangle; all three lie on the circle). Hope this helps. -- Roy Smith, {allegra,cmcl2,philabs}!phri!roy System Administrator, Public Health Research Institute 455 First Avenue, New York, NY 10016
jru@etn-rad.UUCP (John Unekis) (04/03/88)
In article <wWIfSMy00Xo3A5u1dC@andrew.cmu.edu> mp1u+@andrew.cmu.edu (Michael Portuesi) writes: >I am looking for an efficient algorithm that, given a set of points, finds the >smallest circle enclosing them and its center. Pseudocode, actual code (C, ... Try finding the maximum and minimum x coordinates, then average to get the center x. Do the same for y coordinates to get the center for y. Then look at the distances to those four points {sqrt((x1-x2)2 +(y1-y2)2)} from the center x,y and take the largest distance as the radius. To: wlbr!jplgodo!mahendo!elroy!ames!ncar!gatech!udel!rochester!PT.CS.CMU.EDU!andrew.cmu.edu!mp1u+ Subject: Re: Algorithm wanted: Circle enclosing points Newsgroups: comp.graphics In-Reply-To: <wWIfSMy00Xo3A5u1dC@andrew.cmu.edu> Organization: Eaton Inc. IMSD, Westlake Village, CA Cc: Bcc: Try finding the maximum and minimum x coordinates, then average to get the center x. Do the same for y coordinates to get the center for y. Then look at the distances to those four points {sqrt((x1-x2)2 +(y1-y2)2)} from the center x,y and take the largest distance as the radius.
flip@pixar.UUCP (Flip Phillips) (04/04/88)
okay, off the top of my head, how about:
1: find the bounding box of the points
2: the center of the circle is the center of the bbox
3: the radius is any corner of the bounding box
this willget tham all for sure, if you want the smallest, circle you
could just chose the radius as the distance to the point farthest away.
mind you this is just off the top of my head, probably full of holes but an
idea none the less.
-- flip
--
Flip Phillips {sun | ucbvax}!pixar!flip
Pixar - Marin County, Californiaroy@phri.UUCP (Roy Smith) (04/04/88)
jru@etn-rad.UUCP (John Unekis) writes: > Try finding the maximum and minimum x coordinates, then average to get the > center x. Do the same for y [...] look at the distances to those four > points [...] from the center x,y and take the largest distance as the radius. It doesn't take much thought to show that this doesn't work. Take, for example, the 5 points (0,-2), (2,0), (0,2), (-2,0), and (1.9,1.9). The min and max x and y are -2 and 2, giving a center of (0,0) and a radius of 2. The fifth point, (1.9,1.9) does not fall within that circle. -- Roy Smith, {allegra,cmcl2,philabs}!phri!roy System Administrator, Public Health Research Institute 455 First Avenue, New York, NY 10016
rustcat@csli.STANFORD.EDU (Vallury Prabhakar) (04/04/88)
This is pretty trivial. Pick any point in the set as the centre. Compute the largest distance from the remaining points. That will give you the radius of the circle (after adding an appropriate factor for enclosure as opposed to lying on the circumference, of course). Question: Has anyone attempted to solve for curve intersections where the curves are represented in the parametric cubic form such as by Hermite cubics? If so, I'd like to hear about the equation solver that's used. The above method gives rise to a system of 2 non-linear equations in the 2 parametric unknowns. Given the restrictions on the parameters (0 <= u,v <= 1) and the fact that the number of intersection points cannot exceed two, I was wondering if there was some special technique of equation solving that could use these pieces of information. Thanks in advance for any suggestions. -- Vallury Prabhakar -- rustcat@cnc-sun.stanford.edu
juancho@dgp.toronto.edu (John Buchanan) (04/04/88)
In article <496@etn-rad.UUCP> jru@etn-rad.UUCP (John Unekis) writes: >In article <wWIfSMy00Xo3A5u1dC@andrew.cmu.edu> mp1u+@andrew.cmu.edu (Michael Portuesi) writes: >>I am looking for an efficient algorithm that, given a set of points, finds the >>smallest circle enclosing them and its center. Pseudocode, actual code (C, > ... > Try finding the maximum and minimum x coordinates, then average to get the > center x. Do the same for y coordinates to get the center for y. Then look > at the distances to those four points {sqrt((x1-x2)2 +(y1-y2)2)} from the > center x,y and take the largest distance as the radius. This will give you a circle that encloses the points but I think that a tighter circle can be found by looking at the furthest point which lies near the eigenvector that corresponds to the largest valued eigenvalue of the data. Right now I can not remember how to construct the matrix that is required to find the appropriate eigen[values|vectors]. Any good book on pattern recognition will have this.
spencer@tut.cis.ohio-state.edu (Stephen Spencer) (04/04/88)
Finding the center in x and in y by taking the average is OK, but then finding the distances of all points to the centerpoint using a square root each time could be costly. It would work just as well to NOT take the square root (i.e. just calculate (px-cx)*(px-cx) + (py-cy)*(py-cy) where px,py is a point and cx,cy is the center) when calculating the distances, and then finding the TRUE distance of the largest squared distance by using one square root. This would take (n-1) fewer square roots for n points in the set. -- Stephen Spencer, Graduate Student | The Computer Graphics Research Group | spencer@tut.cis.ohio-state.edu The Ohio State University | spencer@ogg.cgrg.ohio-state.edu 1501 Neil Avenue, Columbus OH 43210 | ICBM: 39'58" N, 83'03" W
jru@etn-rad.UUCP (John Unekis) (04/04/88)
In article <3229@phri.UUCP> roy@phri.UUCP (Roy Smith) writes: >jru@etn-rad.UUCP (John Unekis) writes: >> Try finding the maximum and minimum x coordinates, then average to get the .... >2. The fifth point, (1.9,1.9) does not fall within that circle. .... Oops. So much for that little inspiration. I suppose I should have tried it on more than 2 sets of points. Oh, well. Anyone have a working solution?
mrm@sceard.UUCP (M.R.Murphy) (04/05/88)
In article <3229@phri.UUCP> roy@phri.UUCP (Roy Smith) writes: <jru@etn-rad.UUCP (John Unekis) writes: <> Try finding the maximum and minimum x coordinates, then average to get the <> center x. Do the same for y [...] look at the distances to those four <> points [...] from the center x,y and take the largest distance as the radius. < < It doesn't take much thought to show that this doesn't work. Take, <for example, the 5 points (0,-2), (2,0), (0,2), (-2,0), and (1.9,1.9). The <min and max x and y are -2 and 2, giving a center of (0,0) and a radius of <2. The fifth point, (1.9,1.9) does not fall within that circle. <-- <Roy Smith, {allegra,cmcl2,philabs}!phri!roy <System Administrator, Public Health Research Institute <455 First Avenue, New York, NY 10016 The "center" probably isn't the right terminology. I think it's "centroid" and assuming equal weighting for all points, the centroid is at ((0+2+0+(-2)+1.9)/5,((-2)+0+2+0+1.9)/5). Then after one pass through the data to determine the centroid, you pass through again to find the largest distance from the centroid to any of the points. Using the centroid as the center of a circle, and the largest distance from the centroid to any of the points as the radius... Now the question for the mathematicians out there. Is that the smallest enclosing circle? -- Mike -- Mike Murphy Sceard Systems, Inc. 6353C El Camino Real Carlsbad, CA 92009 ARPA: sceard!mrm@nosc.MIL BITNET: MURPHY@UCLACH UUCP: ucsd!sceard!mrm INTERNET: mrm%sceard.UUCP@ucsd.ucsd.edu
naughton@sun.soe.clarkson.edu (Patrick Naughton) (04/05/88)
From article <3297@csli.STANFORD.EDU>, by rustcat@csli.STANFORD.EDU (Vallury Prabhakar): > This is pretty trivial. Pick any point in the set as the centre. Compute > the largest distance from the remaining points. That will give you the > radius of the circle (after adding an appropriate factor for enclosure as > opposed to lying on the circumference, of course). > > -- Vallury Prabhakar > -- rustcat@cnc-sun.stanford.edu You've got to be kidding... I mean really... just try a "trivial" case on your idea... Like *ANY* two points... It is obvious that the enclosing circle here would have a radius of 1/2 the distance between the two with the center at the midpoint of the line connecting them... Not, as you suggest, centered at either of them and a radius of the distance between them. I think you missed the point that the original poster was looking for the smallest enclosing circle, not an arbitrary enclosing circle. -Patrick ___________________________________________ | | | Internet: naughton@sun.soe.clarkson.edu | | BITNET: naughton@CLUTX.BITNET | | uucp: {rpics, gould}!clutx!naughton | |___________________________________________|
flip@pixar.UUCP (Flip Phillips) (04/05/88)
In article <1695@pixar.UUCP> flip@pixar.UUCP (Flip Phillips) writes: [...] >this willget tham all for sure, if you want the smallest, circle you >could just chose the radius as the distance to the point farthest away. > >mind you this is just off the top of my head, probably full of holes but an >idea none the less. ahh yes, off the top of my head... This isn't the SMALLEST circle, as was pointed out by a mail reply I got [ i forgot from who, apologies, apologies ]. so like, find the convex hull, youve got the small set of points needed to find a triangle which describes that circle... cheers -- flip -- Flip Phillips {sun | ucbvax}!pixar!flip Pixar - Marin County, California
jbm@eos.UUCP (Jeffrey Mulligan) (04/05/88)
In article <wWIfSMy00Xo3A5u1dC@andrew.cmu.edu> mp1u+@andrew.cmu.edu (Michael Portuesi) writes: >I am looking for an efficient algorithm that, given a set of points, finds the >smallest circle enclosing them and its center. Pseudocode, actual code (C, A number of people have proposed solutions involving picking a center, (by averaging?) and then getting the radius as the distance to the most distant point. A key observation is that for the *smallest* circle, there will be three points which lie on the circle. Think about it: if the circle encloses all the points and only contains two of the points, then you can shrink the radius (while staying on the two points) until the circle contains another point. This suggests an algorithm which, although expensive (especially for large N), is guaranteed to give the correct solution: 1) Make a list of all triples of points (there are N choose 3 of them). 2) Treating each triple of points as the vertices of a triangle, compute the radius of the circumscribing circle. 3) The largest circumcircle is the desired result. There are probably ways to get tricky and speed this up; for example, if a point can be determined to lie within a triangle already on the list (in step 1) then all triangles containing that point can be discarded. It is unclear whether the cost of this test will be less than the cost of computing some extra circumcircles. -- Jeff Mulligan (jbm@ames-aurora.arpa) NASA/Ames Research Ctr., Mail Stop 239-3, Moffet Field CA, 94035 (415) 694-5150
naughton@sun.soe.clarkson.edu (Patrick Naughton) (04/05/88)
From article <494@eos.UUCP>, by jbm@eos.UUCP (Jeffrey Mulligan): > A number of people have proposed solutions involving picking a center, > (by averaging?) and then getting the radius as the distance to the > most distant point. A key observation is that for the *smallest* circle, > there will be three points which lie on the circle. Think about it: It may be "A key observation", but it is an incorrect one. > if the circle encloses all the points and only contains two of the points, > then you can shrink the radius (while staying on the two points) until > the circle contains another point. This suggests an algorithm which, > although expensive (especially for large N), is guaranteed to give the > correct solution: > > 1) Make a list of all triples of points (there are N choose 3 of them). > > 2) Treating each triple of points as the vertices of a triangle, > compute the radius of the circumscribing circle. > > 3) The largest circumcircle is the desired result. > > Jeff Mulligan (jbm@ames-aurora.arpa) > NASA/Ames Research Ctr., Mail Stop 239-3, Moffet Field CA, 94035 > (415) 694-5150 Again, this fails to find the *smallest* circle that encloses the points... Picture three points arranged in a straight line. The algorithm above would tell us that a circle of infinite radius is the smallest possible circle which will enclose these three points. Sorry for giving nothing but negative replies here but, I don't know the solution and would like to see something other than off the cuff guesses. -Patrick ___________________________________________ | | | Internet: naughton@sun.soe.clarkson.edu | | BITNET: naughton@CLUTX.BITNET | | uucp: {rpics, gould}!clutx!naughton | |___________________________________________|
garry@batcomputer.tn.cornell.edu (Garry Wiegand) (04/05/88)
In a recent article jbm@eos.UUCP (Jeffrey Mulligan) wrote: >... A key observation is that for the *smallest* circle, >there will be three points which lie on the circle... A simple counterexample for you: consider a set of three points that lie approximately in a straight line. (I'd be willing to postulate that at least *two* points are on the edge, assuming the point set is not degenerate.) --- Exhaustive search for this problem is probably O(n^3). I conjecture that the two points which are *farthest apart* will lie on the smallest circle. Finding the two points farthest apart is at most O(n^2) (anybody know for sure?), after which finding the smallest circle is probably O(n). It does seem like it ought to be easier, but I can't see it. (We can make a little more speed in the common cases by looking only at points lying on the convex hull. Finding the convex hull is O(n log n) - I think.) Ever helpfully :-), garry wiegand (garry@oak.cadif.cornell.edu - ARPA) (garry@crnlthry - BITNET)
naughton@sun.soe.clarkson.edu (Patrick Naughton) (04/05/88)
From article <821@sceard.UUCP>, by mrm@sceard.UUCP (M.R.Murphy): Status: R -> The "center" probably isn't the right terminology. I think it's "centroid" -> and assuming equal weighting for all points, the centroid is at -> ((0+2+0+(-2)+1.9)/5,((-2)+0+2+0+1.9)/5). Then after one pass through the data -> to determine the centroid, you pass through again to find the largest -> distance from the centroid to any of the points. -> Using the centroid as the center of a circle, and the largest distance from -> the centroid to any of the points as the radius... -> Now the question for the mathematicians out there. Is that the smallest -> enclosing circle? -> -- Mike -> -- -> Mike Murphy Sceard Systems, Inc. 6353C El Camino Real Carlsbad, CA 92009 -> ARPA: sceard!mrm@nosc.MIL BITNET: MURPHY@UCLACH -> UUCP: ucsd!sceard!mrm INTERNET: mrm%sceard.UUCP@ucsd.ucsd.edu Wow, another wrong *guess*. Maybe we should start a new group called comp.graphics.algorithm.guesswork. The circle described here is centered at (0.95,0.95) with a radius of 1.414214, which is obviously much too large. (draw it on graph paper...) This is getting fun... -Patrick ___________________________________________ | | | Internet: naughton@sun.soe.clarkson.edu | | BITNET: naughton@CLUTX.BITNET | | uucp: {rpics, gould}!clutx!naughton | |___________________________________________|
guy@SHERLOCK.PC.CS.CMU.EDU (Guy Jacobson) (04/05/88)
This is an old and very basic problem in computational geometry (and operations research) first posed by Sylvester in 1857 [J. J. Sylvester, `` A Question in the Geometry of Situation'', _Quart._J._Math._ 1 (1857)]. The problem has received much attention over the years. In 1982, Megiddo showed how to solve the problem in linear time, improving on the previous n log n bound of Hoey and Shamos [N. Megiddo, ``Linear-time Algorithms for Linear Programming in R^3 and Related Problems'', in Proc. 23rd. FOCS (1982), pp. 329-338]. TRUE FACT: The smallest circle enclosing all the points is a circle with two of the points as a diameter (if some such circle encloses all the other points), or the circumscribing circle of three (or more, in degenerate cases) of the points. Think of a circularly constrained hoop shrinking in from infinity to convince yourself of this. The naive algorithm generates all pairs of points (as potential diameters) and checks if all the other points are inside the circle with those pairs as diameters. If such pairs exist, the one with smallest diameter defines the smallest enclosing circle. If no pair forms the diameter of an enclosing circle, then all triples are checked; again the triple whose circumscribing circle encloses all the points with smallest diameter defines the desired circle (this HAS To succeed, from the TRUE FACT above). This algorithm takes n^4 time as presented. Hoey and Shamos's algorithm uses the farthest-point Voronoi diagram, and was the first algorithm proved to run in o(n^3) time. Megiddo's algorithm is too complex to be included here. It proceeds to make a series of passes through the points, discarding those that cannot possibly be on the boundary of the desired circle. In each pass, it is guaranteed to discard at least a fixed fraction (1/16) of the points from consideration; this proves the linear time bound. -- Guy
david@geac.UUCP (David Haynes) (04/05/88)
In article <3229@phri.UUCP: roy@phri.UUCP (Roy Smith) writes: :jru@etn-rad.UUCP (John Unekis) writes: :: Try finding the maximum and minimum x coordinates, then average to get the :: center x. Do the same for y [...] look at the distances to those four :: points [...] from the center x,y and take the largest distance as the radius. : : It doesn't take much thought to show that this doesn't work. Take, :for example, the 5 points (0,-2), (2,0), (0,2), (-2,0), and (1.9,1.9). The :min and max x and y are -2 and 2, giving a center of (0,0) and a radius of :2. The fifth point, (1.9,1.9) does not fall within that circle. :-- :Roy Smith, {allegra,cmcl2,philabs}!phri!roy I am sorry, but since when does a square of length 2 have a *longest* radius of 2? How about sqrt(8) => ~2.8 so that (1.9, 1.9) does fall within it. This is *a* solution but not the optimal solution. (Since the example above only needs a radius of sqrt(7.22)) I would normalize the points to a zero origin and then discover the maximum of sqrt((x^2)+(y^2)), then map the system back to its origin. (in one equation of course!) -david- -- -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- David Haynes Just another road Geac Computers International Inc. kill on the highway UUCP: uunet!mnetor!geac!david -or- david@geac.UUCP of life.
jru@etn-rad.UUCP (John Unekis) (04/06/88)
In article <494@eos.UUCP> jbm@eos.UUCP (Jeffrey Mulligan) writes: >In article <wWIfSMy00Xo3A5u1dC@andrew.cmu.edu> mp1u+@andrew.cmu.edu (Michael Portuesi) writes: >>I am looking for an efficient algorithm that, given a set of points, finds the >>smallest circle enclosing them and its center. Pseudocode, actual code (C, > >A number of people have proposed solutions involving picking a center, >(by averaging?) and then getting the radius as the distance to the >most distant point. A key observation is that for the *smallest* circle, >there will be three points which lie on the circle. Think about it: >if the circle encloses all the points and only contains two of the points, >then you can shrink the radius (while staying on the two points) until >the circle contains another point. This suggests an algorithm which, ... There is an obvious fallacy here. take the set of points {(-7.07,7.07),(0,10),(7.07,7.07)} A circle that had three points along the edge would have a center at (0,0) and a radius of 10. However a circle with center at (0,7.07) and radius 7.07 contains all three points and has a smaller radius with only two points on the circle. I beleive that in general you can shrink a circle which has only one point from the set on the circumference until it has two, but to get a third point on the circumference may require the circle to GROW, not shrink. Note that my original solution doesn't give the smallest radius either, so we are still waiting for a correct solution.
jbm@eos.UUCP (Jeffrey Mulligan) (04/06/88)
Thanks to Guy Jacobson for posting a complete reference to this apparently well-studied problem. In light of this, I don't know whether there is much point in correcting my previous erroneous solution, From article <494@eos.UUCP>, by jbm@eos.UUCP (Jeffrey Mulligan): > 1) Make a list of all triples of points (there are N choose 3 of them). > > 2) Treating each triple of points as the vertices of a triangle, 2a) If the triangle is right or acute: > compute the radius of the circumscribing circle. 2b) if the triangle is obtuse, the circle's diameter is the side opposite the obtuse angle. > > 3) The largest circumcircle is the desired result. > s/circumcircle/circle Guess I really put my foot in it after that posting about naive answers... -- Jeff Mulligan (jbm@ames-aurora.arpa) NASA/Ames Research Ctr., Mail Stop 239-3, Moffet Field CA, 94035 (415) 694-5150
jbm@eos.UUCP (Jeffrey Mulligan) (04/06/88)
From article <4306@batcomputer.tn.cornell.edu>, by garry@batcomputer.tn.cornell.edu (Garry Wiegand): > Exhaustive search for this problem is probably O(n^3). I conjecture > that the two points which are *farthest apart* will lie on the smallest > circle. counterexample: If the desired circle is contains 3 points at the vertices of an equilateral triangle, there can be pairs of interior points whose distance approaches the diameter. -- Jeff Mulligan (jbm@ames-aurora.arpa) NASA/Ames Research Ctr., Mail Stop 239-3, Moffet Field CA, 94035 (415) 694-5150
flaig@cit-vlsi.Caltech.Edu (Charles M. Flaig) (04/06/88)
In article <494@eos.UUCP> jbm@eos.UUCP (Jeffrey Mulligan) writes: >In article <wWIfSMy00Xo3A5u1dC@andrew.cmu.edu> mp1u+@andrew.cmu.edu (Michael Portuesi) writes: >>I am looking for an efficient algorithm that, given a set of points, finds the >>smallest circle enclosing them and its center. Pseudocode, actual code (C, > >A number of people have proposed solutions involving picking a center, >(by averaging?) and then getting the radius as the distance to the >most distant point. A key observation is that for the *smallest* circle, >there will be three points which lie on the circle. Think about it: >if the circle encloses all the points and only contains two of the points, >then you can shrink the radius (while staying on the two points) until >the circle contains another point. This suggests an algorithm which, >although expensive (especially for large N), is guaranteed to give the >correct solution: ACK! No, think about it some more. :-) The *smallest* circle is only guaranteed to pass through two points. As in the following set of points: * * * * * Clearly the smallest circle will have the leftmost and rightmost points on its edge, with its center halfway between them. If you tried to put a 3rd point on the circle, it would be much larger, with its center several inches up (or down) the page. ______________________________________________________________________________ ___ , , ,;,;;;, / Y /| /| Charles Flaig ;/@-@\; | |/ __, ,__ |/ flaig@csvax.caltech.edu | ^ | | /^\ / | | | / /\ /\ \=/ \____/| \_/|_/\_/ \_/ \_\/_/_/_/ "What, you think they PAY me for this?"
crawfis@lll-lcc.aRpA (Roger A. Crawfis) (04/06/88)
In article <4306@batcomputer.tn.cornell.edu> garry@oak.cadif.cornell.edu writes: >In a recent article jbm@eos.UUCP (Jeffrey Mulligan) wrote: >>... A key observation is that for the *smallest* circle, >>there will be three points which lie on the circle... > >A simple counterexample for you: consider a set of three points >that lie approximately in a straight line. > ... > >(We can make a little more speed in the common cases by looking only > at points lying on the convex hull. Finding the convex hull is > O(n log n) - I think.) > True, but this is a degenerate case. By the way this is first postin, so if I do anything wrong, please flame and I will try to avoid future mistakes. Points: 1) The circle will circumscribe the convex hull. 2) Given a nondegenerate convex polygon (convex hull), at least three points of it will lie on the smallest circumscribing circle. 3) Finding the convex hull takes O(n log n) 4) Finding the triangle with the largest radius from the convex hull can take O(m**2 log m). 5) The set of points comprising the convex hull may be (or may not be) substaintally smaller than n. I like the centriod/farthest distance idea for large data sets and when finding the absolute smallest circle is not neccessary. However if the data consists of a large cluster and a single point out in the "boonies" then this can yield a circle twice the desired size. A proposed solution. I. Find the convex hull. oops-my I'm not sure my solution for the this works here. So I'll let others illustrate how. It's a well known problem. :(?. II. Throw away any duplicate points. III. Find the radius by looking at the set of all possible triangles in the convex hull. For a triangle with three sides of length a, b and c. abc R = ------------------------ 4*sqrt(s(s-a)(s-b)(s-c)) where s = .5 * (a+b+c) I know this is probably not the best (or completest) solution, but I thought I needed to defend the triangle and convex hull answers. Roger A. Crawfis
ksbooth@watcgl.waterloo.edu (Kelly Booth) (04/07/88)
In article <3229@phri.UUCP> roy@phri.UUCP (Roy Smith) writes: >jru@etn-rad.UUCP (John Unekis) writes: >> Try finding the maximum and minimum x coordinates, then average to get the >> center x. Do the same for y [...] look at the distances to those four >> points [...] from the center x,y and take the largest distance as the radius. > > It doesn't take much thought to show that this doesn't work. Take, >for example, the 5 points (0,-2), (2,0), (0,2), (-2,0), and (1.9,1.9). The >min and max x and y are -2 and 2, giving a center of (0,0) and a radius of >2. The fifth point, (1.9,1.9) does not fall within that circle. The algorithm that was posted is garbage. Assuming that the radius calculation is extended to take a maximum over ALL points (Roy Smith read the algorithm as taking the maximum over just max-min points, which is what I read it as, but gave the poster the benefit of the doubt and used the stronger condition), you still get the wrong answer. The algorithm computes a nice axis-oriented rectangular bounding box if you keep just the max and min values. The circle (with the extended radius calculation) is a bounding circle, but neither the center or the radius is guaranteed to be "good" in the sense of minimality. Morals: 1. Purported solutions posted to the net should be stated in an algorithmic form not open to misinterpretation (this is, after all, a group for people with some minimal familiarity with computing) so they can be translated to a program directly. 2. Solutions that do not include a reference to the literature or a proof of correctness are often (in this group almost always) wrong in trivial or major ways. 3. Easy problems such as these hardly ever have naive, slick solutions. If they did, what person of any intelligence would post a request for a solution to the net? Slick solutions sometimes do exist, but they usually require some insight, a detailed (sometimes messy) proof of correctness, and almost always benefit from citations of previous work that has been vetted in the literature.
jk3k+@andrew.cmu.edu (Joe Keane) (04/09/88)
In article <4306@batcomputer.tn.cornell.edu>, garry@batcomputer.tn.cornell.edu (Garry Wiegand) writes: > I conjecture that the two points which are *farthest apart* will lie on the > smallest circle. 'Fraid not. Suppose A=(0,-2), B=(1,3), X=(-1,-2), Y=(3,0), and Z=(-1,3). Then A and B are farthest apart but the smallest circle is XYZ. -1 0 1 2 3 3 Z B 2 1 0 Y -1 -2 X A --Joe
lmiller@venera.isi.edu (Larry Miller) (04/13/88)
In article <682@sun.soe.clarkson.edu> naughton@sun.soe.clarkson.edu (Patrick Naughton) writes: >From article <494@eos.UUCP>, by jbm@eos.UUCP (Jeffrey Mulligan): > Discussion on finding the smallest CIRCLE bounding a > set of points. O.K., boys and girls, here goes. (1) Find the convex hull. See: Sedgewick, Robert. "Algorithms." Addison-Wesley Publishing Co., 1983. Chap 25 (pp. 321-333). (2) Find the centroid of the points from the original set that are on the convex hull. (3) The centroid is the center; the distance to any of the points on the convex hull is the radius. [As expected, this won't work if the points are co-linear] Larry Miller lmiller@venera.isi.edu (no uucp) USC/ISI 213-822-1511 4676 Admiralty Way Marina del Rey, CA. 90292
lurch@vedge.UUCP (Lurch) (04/15/88)
> In article <wWIfSMy00Xo3A5u1dC@andrew.cmu.edu> mp1u+@andrew.cmu.edu (Michael Portuesi) writes: > >I am looking for an efficient algorithm that, given a set of points, finds the > >smallest circle enclosing them and its center. Pseudocode, actual code (C, > In article <494@eos.UUCP>, jbm@eos.UUCP (Jeffrey Mulligan) responds: > 1) Make a list of all triples of points (there are N choose 3 of them). > 2) Treating each triple of points as the vertices of a triangle, > compute the radius of the circumscribing circle. > 3) The largest circumcircle is the desired result. Seems to me that rather than use the set of all possible triplets, just using the points from the convex hull would speed this up greatly. Obviously, the three points Jeff M. refers to must lie on the hull. -- | "I gave you seven children woman...Now you want to give 'em back!" -BB King | +-----------------------------------------------------------------------------+ | Jeff Smith Visual Edge Software, Montreal, Quebec | | ....sun!decwrl!decvax!watmath!onfcanim!vedge!lurch |
markov@ruuinf.UUCP (dr.m.h. overmars) (04/15/88)
In article <5256@venera.isi.edu>, lmiller@venera.isi.edu (Larry Miller) gives
a solution to the smallest enclosing circle problem. I can't see why
this solution works (unless I misunderstand the notion of centroid).
You can alsways add points to a set that will lie on one side on the
convex hull without changing the bounding circle. But this must change the
centroid and, hence, the circle found.
Here are two simple, linear time solutions that do give enclosing
circles but not neccessarily minimal ones:
1) Find the bounding box (by determining minimal and maximal x- and y-values.
Take the middle as center and as radius the distance to a vertex. Normally
the circle found will be too large, but not that much too large.
2) Start with the minimal circle of three points (either the circle with
the three points on the boundary or with two on opposite sides). Now
one after the other add the points and every time compute the minimal
circle that encloses the previous found circle and the new point.
A O(n log n) solution has been given quite some time ago by Shamos, using
farthest-point Voronoi diagrams. One of the references is:
M.I. Shamos and D Hoey, Closest-point problems, Proc. 16th Annual IEEE
Symposium on Foundations of Computer Science (FOCS), 1975, pp. 151-162.
For some other heuristical solution to this problem and related ones see:
K.J. Supowit, Grid heuristics for some geometric covering problems, in:
F.P. Preparata (Ed.) Advances in Computing research, vol 1:
computational geometry, JAI press, 1983, pp. 215-234.
I hope this answers all the questions about the problem.
Mark Overmars.limes@sun.uucp (Greg Limes) (04/26/88)
In article <EWLWd2y00XcSQ1=kwX@andrew.cmu.edu> jk3k+@andrew.cmu.edu (Joe Keane) writes: >In article <4306@batcomputer.tn.cornell.edu>, garry@batcomputer.tn.cornell.edu >(Garry Wiegand) writes: >> I conjecture that the two points which are *farthest apart* will lie on the >> smallest circle. > >'Fraid not. Suppose A=(0,-2), B=(1,3), X=(-1,-2), Y=(3,0), and Z=(-1,3). Then >A and B are farthest apart but the smallest circle is XYZ. > Waitaminnit, the intuition kicks in for half a second and ... is it true that *one* of these two points will be on the smallest circle? and is finding this pair efficient enough to be used to prune out some of the trash while examining triplits? -- Greg Limes [limes@sun.com] frames to /dev/fb