From albanycs!leah:rsb584 Wed Apr 6 17:31:10 1988 Received: by albanycs.albany.edu (5.54/4.8) id AA28062; Wed, 6 Apr 88 11:55:28 EST Date: Wed, 6 Apr 88 12:55:21 EDT From: albanycs!leah:rsb584 (Raymond S Brand) Received: by leah.Albany.EDU (5.58/1.1) id AA02143; Wed, 6 Apr 88 12:55:21 EDT Message-Id: <8804061655.AA02143@leah.Albany.EDU> To: albanycs:beowulf!rsbx Subject: circle.txt >From roy@phri.UUCP Fri Apr 1 10:37:17 1988 Path: leah!uwmcsd1!bbn!rochester!cornell!uw-beaver!mit-eddie!husc6!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