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

On 26 fév, 21:28, Marc <mble...@xxxxxxxxx> wrote:
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

Hi again :),

Thanks a lot for you answer !

Would the pseudo-code look something like that (badly written : I am
no computer science guy ;) ):

P = <p0, p1...pN> vector containing N points defining a convex polygon
(obtained by Graham alg.)
The first 4 would be, say : 0, N/4, N/2, 3N/4 : they should be far fom
each other as my vector is ordered.

main
while(Not_All_In_circle)
select I points in P
look_for_their_circumscribed_circle
I = I+1
endwhile

look_for_their_circumscribed_circle
test all combinations (triplet and couple) of points untill the circle
they define is the circumscribed circle of your subset ?

If this is OK, isn't look_for_their_circumscribed_circle going to cost
a lot ?

Marc

I did not write all that properly :
I keep the already selected point, of course, and add the first one
outside the circle to my subset...
.

Relevant Pages