Re: question
scot@flume.cs.dartmouth.edu
Thu, 23 Jan 1997 17:12:08 -0500 (EST)
Anne Huffer asks:
> If I have a finite set of points, how do I construct a circle that encloses
> all of them? I was thinking of the convex hull and then selecting one point
> on the hull at random. Then finding the distances from the other points on
> the hull find the three that are furthest apart. After that constructing
> the perpendicular bisectors of two of the lines joining the three points
> and using the intersection of these as the center of the circle and the
> distance to one of the points as the radius. Can I select "any" point - I
> don't think so. If not how do I find the ones to construct the circle?
If you want ANY circle that encloses all of the points you can pick any point,
find the furthest site from that point, and use that distance as your
radius. If you want a smallest circle to enclose all of the points,
the Farthest Point Voronoi Diagram solves that problem. The smallest
circle will either be centered at the midpoint of a diameter of the set
or else at one of the Voronoi points where three regions in the FPVD
meet.
I seem to remember talking about this at DREI. Is it in the class notes?
Implementing this might be a bit of work for a high school student, though.
Scot Drysdale