Re: algorithm to determine smallest circumscribed circle of an arbitrary convex polygon

On 26 fév, 21:03, Helmut Richter <hh...@xxxxxx> wrote:
On Tue, 26 Feb 2008, Marc wrote:
I am looking for an algorithm that would provide the smallest
circumscribed circle around an arbitrary convex polygon ?
If anyone has a clue, I'd be very interested !

It is easy to show that the solution is either

- the circumscribed circle of an acute-angled triangle from the original
vertices or

- the circle whose diameter consists of the line connecting two of the
original vertices

This gives rise to an algorithm to compute the smallest circumscribed
circle around 4 points. You can extend that algorithm to any number of
points:

Start with any subset of four points with their circumscribed circle (it
is smart to start with distant points but it is no use to spend time on
this step). Find a subset S of two or three of them that already define
the same circumscribed circle. If none of the original vertices is outside
that circle, you are done. If there is at least one vertex P outside the
circle, start over beginning with the set S u {P}. Each circle is larger
than the previous one, so the algorithm terminates.

Do not try to prove that vertices that were captured by one circle are
contained in all subsequent circles: it is not true. It is, however, true
that at the end all vertices are captured even though some of them might
have managed to escape temporarily.

I have also a full description with a proof but it is in German and I am
too lazy to translate. You should be able to reconstruct the idea from the
above.

--
Helmut Richter

Well, thanks a lot !! All that is not so easy for me !! :)

Marc
.

Relevant Pages