Re: Smalest enclosing circle
- To: mathgroup at smc.vnet.net
- Subject: [mg50146] Re: Smalest enclosing circle
- From: Steve Gray <stevebg at adelphia.net>
- Date: Tue, 17 Aug 2004 05:01:35 -0400 (EDT)
- References: <cfi8tm$4p6$1@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
On Fri, 13 Aug 2004 11:33:10 +0000 (UTC), Steve Gray <stevebg at adelphia.net> wrote: > Given n points in the plane, I want to find the smallest >enclosing circle. Does anyone have Mathematica code to do this? > I will be grateful for any tips. > >Steve Gray I want to thank everyone for their answers. For Dr. Bob: I was not immediately able to install Draw Graphics because of some ambiguities in the instructions and my own ignorance. The problem itself is nontrivial and there is no simple, correct solution which is also efficient. Do a Web search on "smallest enclosing circle" and similar phrases and you will find many leads. One claims there is a (complicated) linear time algorithm, but the more usual solution is n*log(n). I have not found a canned answer for Mathematica. Fortunately my requirements are very easy: a small number of points (not more than 20), and noncritical speed. The solution does not even have to be the absolute smallest circle. The one thing that really matters is that no points may be outside the circle. I wrote something very simple myself which solves the problem satisfactorily (but not elegantly). I posted the question thinking that surely there would be lots of ready solutions already coded. I'm sure that there are, but no one has come forth and publicized them. Steve Gray