Path: utzoo!mnetor!uunet!husc6!mailrus!ames!elroy!cit-vax!cit-vlsi!flaig From: flaig@cit-vlsi.Caltech.Edu (Charles M. Flaig) Newsgroups: comp.graphics Subject: Re: Algorithm wanted: Circle enclosing points Message-ID: <6026@cit-vax.Caltech.Edu> Date: 5 Apr 88 20:31:48 GMT References: <496@etn-rad.UUCP> <494@eos.UUCP> Sender: news@cit-vax.Caltech.Edu Reply-To: flaig@cit-vlsi.UUCP (Charles M. Flaig) Organization: California Institute of Technology Lines: 33 In article <494@eos.UUCP> jbm@eos.UUCP (Jeffrey Mulligan) writes: >In article 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?"