Path: utzoo!mnetor!uunet!husc6!uwvax!oddjob!ncar!ames!pasteur!ucbvax!ucsd!sdcsvax!ucsdhub!hp-sdd!hplabs!sdcrdcf!trwrb!aero!venera.isi.edu!lmiller
From: lmiller@venera.isi.edu (Larry Miller)
Newsgroups: comp.graphics
Subject: Re: Algorithm wanted: Circle enclosing points
Message-ID: <5256@venera.isi.edu>
Date: 12 Apr 88 19:09:48 GMT
References: <494@eos.UUCP> <682@sun.soe.clarkson.edu>
Reply-To: lmiller@venera.isi.edu.UUCP (Larry Miller)
Organization: Information Sciences Institute, Univ. of So. California
Lines: 23

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