User talk:Hippo.69

Welcome

Hello, Hippo.69, and welcome to Wikipedia. Thank you for your contributions. I hope you like the place and decide to stay. If you are stuck, and looking for help, please come to the New contributors' help page, where experienced Wikipedians can answer any queries you have! Or, you can just type {{helpme}} and your question on this page, and someone will show up shortly to answer. Here are a few good links for newcomers:

We hope you enjoy editing here and being a Wikipedian! By the way, you can sign your name on talk and vote pages using four tildes, like this: ~~~~. If you have any questions, see the help pages, add a question to the village pump or ask me on my talk page. Again, welcome! -- TRPoD aka The Red Pen of Doom 23:07, 8 December 2012 (UTC)[reply]

Minimal bounding circle problem

Hi Hippo.69, thanks for your extensive discussion on the Talk page of the Smallest-circle_problem problem, and your extra explanation on your User page here.

I am bit puzzled though, as to where/what actually would be a reliable pseudo- (or python) implementation of Welzl's algorithm, as I'm needing it for some research I'm doing. The pseudo-code on Wikipedia still looks wrong to me. When you stated that: "The Welzl's algorithm does not work in the form it is stated in the article and here. It was corrected by Matousek, Sharir, Welzl" - is that still the case, is that just due to the misunderstanding at the time of "trivial(R)" in the \card(R) = 3 case?

The specific counter-example to Welzl I believe I have, is suppose points A = (0, 3.9), B = (-1, 0), C = (1, 0) and D = (0, -0.9). Let's suppose that the excluded point was A, and so we have already processed {B, C, D} and the circle is centred at (0,0) and has radius 1, so B, C are on the boundary (and in R), D is an interior point to that circle, and A is outside it, to the above. Then we need to add A, but since {B, C} is our current R, we end up with at best some subset of {A, B, C}. But the bounding circle for the whole set is the circle of radius 2, centred at (0, 1.9), with A and D on the boundary, and B, C in the interior.

Thanks if you can provide any assistance to my understanding of it. Mozzy66 (talk) 04:50, 2 January 2024 (UTC)[reply]

The algorithm is correct when trivial means minimal circle having whole R on its boundary, so in the \card(R) = 3 case with trinagle having one angle biger than 90 degrees the circle is not the one on diameter of remaining two points having the last point inside, but biger circle circumscribed by all 3 points of the triangle. ... radiuses of such circles cannot decrease ...

msw algorithm uses as trivial minimal circle enclosing the base points so some care must be taken to force the diameter cannot decrease. It is not easy to find a small case when the problem appears ... and actually I am persuaded in implementation of welzl's algorithm in variant with one shuffle and move to front heiristics both versions of trivial algorithm would work well, because the move to front heuristics would esentionally convert it to msw algorithm.

The trivial using circumscribed circle is easier to implenment ... you just neednot do the cases ... central point is on intersection of axes of all R_i,R_{i+1}. And if there is not enough of such axes (|R|<3), line R_i,R_{i+1} is used as well ... and if there is no such line (|R|=1), the only point of R is used and if there is no such point (|R|=0) the disc is empty ... the radius is the distance of the first point from the center (unless the disc is empty).

To your example. The order of choice is A, (and independently on choices in the recursion) returning circle on diameter BC, therefore A is added o R.

Then the recursion is called again and it depends on the next choice. (I will omit C due to symetry with B)

Choice B: independently on choices in the recursion, disc on diameter AD is retuned and B is inside, so it is the final result.

Choice D: independently on choices in the recursion, disc circumscribed to ABC is returned and D is outside, so D is put to R and recursion is called again, by symmetry chosing B. The recurence returns disc on diameter AD and B is inside so it is the final result.

I am persuaded the minimal example where choice of trivial is important is an example with 5 points. You can see in your case there were no such problem.

Hippo.69 (talk) 08:10, 2 January 2024 (UTC)[reply]

I have used implementation of the presented algorithm (with wrong trivial) using global array containing points of R at the begin, then points of P and at the end points already selected. The arguments are just the indices Rend where R portions end and Pend where P portion ends. The selection is chosing uniformly random number between Rend and Pend and swapping the point with the last point in P section. Then the recurence is called with Pend boundary decremented.

When R..P portion is empty trivial(R) is used and we are returnig from the recurrence. (What effectively increases Pend, but we have to check the last point in P portion belongs to the current disc. If not, it should be swapped to the start of R..P portion and Rend increased. And the recurence is called again...

It is easy to get rid of one order of recurence by doing the cycle decreasing Pend instead till R..P portion is empty and doing another cycle increasing Pend and checking all points are inside the current disc. The recurence is called whenever the condition fails (after swapping the failing point to R).

Just note that when we return from the recurence the Rend is returned to its original value so new failure in increasing Pend loop swaps at the same position.

You can maintain maximal checked Pend for Rend=0, maximal checked Pend for Rend=1, Rend=2 (, and Rend=3). That would allow getting rid of the other level of recursion

... for current Rend if test fails for Pend, remember this Pend for given Rend, swap and increase Rend and start Pend decreasing loop and then Pend increasing loop, but in the Pend increasing loop you have to check Pend does not reach maximal reached Pend for Rend-1. If it happens, you should decrease Rend and continue the Pend increasing loop ...

You can consider the decreasing Pend loop as creating random permutation of points in P and the increasing Pend loop the condition checking... .

One shuffle variant makes random permutation of points in P at the beginning and does not swap in the Pend decreasing loop. (There is no Pend decreasing loop at all).

Move to front version almost corresponds to swapping to R, but it rotates R to insert to its start ... I do not think it is important diference. (One shuffle version does not specify the R maintainance so there is no simple correspondence to presented implementation)

Not swapping in Pend decrement loops in deeper levels of recursion means points moved to R recently cannot be chosen early what improves the performance ... (diameter of disc of last 4 points never decreases) (and corrects the problem when bad algorithm for trivial is chosen). Hippo.69 (talk) 08:49, 2 January 2024 (UTC)[reply]