Path: utzoo!mnetor!uunet!yale!cmcl2!phri!roy From: roy@phri.UUCP (Roy Smith) Newsgroups: comp.graphics Subject: Re: Algorithm wanted: Circle enclosing points Message-ID: <3226@phri.UUCP> Date: 1 Apr 88 15:37:17 GMT References: Reply-To: roy@phri.UUCP (Roy Smith) Organization: Public Health Research Inst. (NY, NY) Lines: 24 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