This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics articles
The algorithms here are written incomprehensibly; as if by someone untrained in computer science, but attempting to say everything in as few words as possible. Trying to figure out what is going on with Megiddo's algorithm would be impossible from the current text. —Preceding unsigned comment added by 128.180.123.59 (talk) 17:39, 22 September 2010 (UTC)[reply]
Would you mind (me?) adding the msw (Matoušek, Sharir, Welzl) algorithm here to have a correct fast algorithm presented?Hippo.69 (talk) 16:02, 2 March 2019 (UTC)[reply]
I fail to see the point of describing, in detail, many non-optimal algorithms for this problem, and not even mentioning that it has long been known to be solved in linear time. I'm tempted to remove all the cruft and return to this version, which at least has the virtue of quickly getting to the point. —David Eppstein (talk) 16:54, 22 July 2009 (UTC)[reply]
I do not agree the term called "nonoptimal" algorithms. They all find optimal solutions. On the other hand, there is no guarantee that linear time (complexity) algorithms are faster than other non-linear time algorithms. For example, in linear programming, non polynomial algorithms run faster than polynomial algorithms. I was thinking to put some comparison results of some main approaches. —Preceding unsigned comment added by 128.227.216.170 (talk) 17:34, 11 August 2009 (UTC)[reply]
The linear algorithm does have one weakness which should be mentioned. If you put a lot of points in a near-perfect circular pattern, the runtime can increase at a much greater rate, as it has to adjust the circle far more frequently (and thus recurse more deeply) than with the same number of points in a more uniform or random distribution. 199.76.66.200 (talk) 18:39, 29 May 2015 (UTC)[reply]
Actually, never mind. It seems that the randomness is critical here. Creating points in a circle is only a problem if those points are all processed in the order they're created in. Shuffling the list prior to running the algorithm speeds up the runtime considerably. There is of course still a chance that it randomly picks the worst possible next candidate every time, but that's probably extremely unlikely. (Not impossible, though, so might still be worth mentioning as worst-case.) 199.76.66.200 (talk) 18:59, 29 May 2015 (UTC)[reply]
There are also non-random algorithms with linear worst-case time bounds. They are generally more complicated and less practical than the randomized ones, though. I believe the randomized linear time bounds are not just on the expected value of the time, but that they also hold with high probability. —David Eppstein (talk) 19:01, 29 May 2015 (UTC)[reply]
This is a special case of the 1-center problem, and that page doesn't have much on the other cases. Could we make this page a section on that one, or vice versa (add a "generalizations" section to this one)? siddharthist (talk) 23:37, 19 November 2017 (UTC)[reply]
Oppose merge, on the grounds that, if anything, a better target would be Bounding sphere, which is the n-dimensional generalization of the Smallest-circle problem and is itself a subset of the 1-center problem. I don't think that merging all 3 is necessary on the grounds that the Bounding sphere problem is independently notable from the more general case. Klbrain (talk) 15:56, 20 January 2019 (UTC)[reply]
Consider using this picture to document importance of understanding what the "trivial(R)" means... and feel free to delete all the chaos I was making for 3 years...
OK, if the question is what is wrong in the paper, the answer is the lemma 1, iii does not hold for P={1,2,3}, R={4} on the picture. The problem leading to assuming it is correct is that the set S in the paper is not parametrized by the current subset, so after we deduce that 4\in S_{0,1,2,3,4} and 1\in S_{1,2,3,4} and 3\in S_{1,2,3,4} we expect we have all 3 points of S_{1,2,3,4} while actually S_{1,2,3,4}={1,2,3}.
Oh no, problem is somewhere else. For all three points from {1,2,3} lemma 1 ii holds as b_md({1,2,3},{4}) does not exist.
And iii is true as well as b_md({1,2,3},{4}) does not exist. Hippo.69 (talk) 08:03, 18 December 2023 (UTC)[reply]
It seems to me the paper expects b_md(P-{p},R) exists whenever b_md(P,R) exists (top of page 363), but the statement is not there. May be "Note since b_md(P,{}) is always defined, in the whole computation initiated by MINDISK no call to B_MINDISK returns an undefined result.", unfortunately it is true as well. Just the result is not b_md({1,2,3,4}).
Oh, there are two algorithms on the same place ... one with "or |R|=3" and one without and the prrof is based on the algorithm without "or |R|=3". For that case B_MINDISK({1,2,3},{4}) correctly returns undefined (after all points from {1,2,3} are put to R the call b_md({},{1,2,3,4}) does so. So B_MINDISK({0,1,2,3},{4})) could return undefined while b_md({0,1,2,3},{4}) exists.
The algorithm with "or |R|=3" and without "D defined" is based on the statement this cannot happen.
Hippo.69 (talk) 08:24, 18 December 2023 (UTC)[reply]
As I have written few years ago, if the radius of enclosing circle cannot decrease during the run of the algorithm than point p in S_P is also in S_Q far all subsets Q of P containing p. With this assumption the Lemma 1 iii would hold. Hippo.69 (talk) 18:32, 17 December 2023 (UTC)[reply]
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. By starting with a base and recomputing the base to force diameter always grows.
(When implemented using array of points and sending just bounds of the array in the recurrence, the first 4 points should not be selected unless they are last.
Or equivalently when making random permutation of the array ... the first 4 places should not be permuted when the vertex is fixed (for example by x->0->1->2->3->x permutation).
Hippo.69 (talk) 12:26, 26 February 2019 (UTC)[reply]
OK, after a personal communcation with Emo Welzl I have to admit the interpretation of b_m({1,2,3},{4}) and b_m({},{1,2,4}) is disc with points {1,2,4} on its boudnary rather to undefined and disc on diameter {1,2}. That b_m(P,R) is not the smallest disc containing P provided R is on its boundary, but smallest disc going through points R and containing P. Sorry for all this confusion ... but telling me what is wrong on the counterexample would shorted it.
May be the sentence "let b_md(P, R) be the closed disk of smallest radius which contains all points in P with all points in R on its boundary" is a bit ambivalent.
But problem could be in my bad english as well.
Hippo.69 (talk) 15:34, 18 December 2023 (UTC)[reply]
@Hippo.69: I have removed your example because it appears to be unsourced WP:OR, but also because it is very unclear to exactly which version of the algorithm this is supposed to be a counterexample. The one in the article text, that adds points one at a time in a random order, maintaining as it does a set of added points? The one in the pseudocode that instead removes points randomly one at a time recursing on the remaining points? Some other version of the algorithm that (incorrectly) uses a random ordering of the points but then chooses the circle through the first three points instead of the minimum enclosing circle of those points? —David Eppstein (talk) 21:43, 26 February 2019 (UTC)[reply]
@David Eppstein:Counterexample for Welzl's minium enclosing circle algorithm It was counterexample to the algorithm to which the picture was attached (it shows situation when the algoritm returns "undefined"). So do you mean WP:OR forces me to write a publication that the original paper contained wrong algorithm, otherwise the counterexample could not be published on wiki? It seemed the counterexample is clear enough not to need supporting paper.
Oops, you are right it is not counterexample to the presented pseudocode. Presented pseudocode is much worse than I expected. There is missing case |R|=0: return "empty disk". Therefore the algorithm does not work when called with empty R.
Selection order ... means order in which points are chosen in the algorithm, (I have misread the stop condition in presented algorithm so I have not mentioned the selection of points when at most 3 points remain in $P\cup R$)
(when random choice happens to be exactly this, the algorithm adds points with Red colored names to the set R).
So would adding the last 3/2/1 points to the text in the picture solve the problem?
Hmmm, trying to understand the presented code ... does test "p is in undefined" return false?
In that case algorithm starts working. In my "counterexample" it would put A,B,C to R and than
it does not select D and returns black circle (even when it does not contain D), so when processing E,
it is satisfied with the black circle even when it does not contain D and only A,B are in R.
Than it sees F is outside the disk and fixes F. ...
So the presented algorithm returns incorrect subresults, but only in case there is surely vertex "on the stack" outside the disk. And in that case it would be recomputed.
So the incorrect version is the version ending recurrence when $P\cup R=3$, what was not the case of the presented algorithm and it differs from the version in Welzl's original paper as well.
Example of Welzl's algorithm run which returns wrong result
OK I have finished checking the failing run of my implementation of presented Welzl's algorithm corresponds to algorithm presented here. So even with the stop condition of 3 fixed points the algorithm neednot return correct results. It happend around in 1 of 5000 runs on 8 random points (uniform in unit square).
@David Eppstein: OK you have unrolled 2nd counterexample (I have planned to replace it anyways). I bet it was too big and with too complicated legend. I suggest third counterexample.
If you insist on making a publication, would an article in arxiv suffice or what is enough to be accepted?
BTW: I have decided to choose from 5 counterexamles the one best looking ... 5th was find at simulation number 153455 among simulations for 5 unifomly distributed points in a square (10 uniformly choosen coordinates).
Hippo.69 (talk) 15:53, 2 March 2019 (UTC)[reply]
Hmmm, rereading the presented algorithm it is unclear what
else if the points of R are cocircular:
return the circle they determine
else return undefined
mean.
I have rechecked the counterexample and the algorithm definitely returns the red circle.
But the comments are not perfect. After the blue 2 should be immediately yellow 0 and after the last
blue 3 should be immediately grey 0 and yellow 2 (as when 3 points are fixed there are no more choices made).
Hippo.69 (talk) 21:22, 2 March 2019 (UTC)[reply]
ArXiv is not a reliable source by Wikipedia's standards, so publication would be better. But really, what I want is clarity: a source that explains exactly which algorithm is being implemented (because as I said there are at least three choices: as described in the original paper, as described in the text of our article, or as described in the pseudocode of our article, all somewhat distinct), that provides source code (so one can verify that it is the algorithm not the implementation that is wrong) and that clearly describes a specific instance for which it goes wrong and exactly what goes wrong in that instance (rather than merely presenting an illegible tangle of circles and labeled points and expecting readers to be able to decode it). —David Eppstein (talk) 18:06, 2 March 2019 (UTC)[reply]
Example of Welzl's algorithm run which returns wrong result
Could you please try to trace the algorithm(s) according to the picture. If you need an explanation or exact coordinates, I am ready to help.Hippo.69 (talk) 21:22, 2 March 2019 (UTC)[reply]
I have told you, I find your picture cryptic and incomprehensible. If I do, I think it very likely that other Wikipedia readers will have the same reaction. —David Eppstein (talk) 21:35, 2 March 2019 (UTC)[reply]
When I am thinking about the counterexample now, let me phrase it in a rather compact form.
I am reffering to the algorithm b_mindisk from page 362 (363) of the Welzl's 1991 Smallest enclosing disks (...) paper. What is equivalently written here as algorithm Welzl (but it may be changed).
Suppose it was called with P={0,1,2,3,4} where points are on the picture. Else branch was invoked and suppose 4 was chosen as p. Let us suppose the recurrence returns correct minimal disk of points {0,1,2,3}, what is bounded by blue circle on diameter 0,2. (The algorithm returns it, and I do not think we disagree). This is why 4 is put to R (what is correct).
Suppose next choices will be 0, 1 and smallest disk for P={2,3}, R={4} is returned, what has the green border (going through points 2,3,4).
As 1 is outside, it will be put to R (that is problematic ... correct for {1,2,3,4}, but incorrect for {0,1,2,3,4}).
Suppose 3 was latter selected in P={2,3} R={1,4} call. Suppose minimal disk for P={2} and R={1,4} is returned what is the brown one (on diameter 1,2). 3 is outside so 3 is put to R.
Next call P={2} R={1,3,4} uses then branch so returns disk (enclosed by the red circle ... on diameter 3,4) not containing point 2. (definitely incorrect)
Point 0 is inside the disk so the disk with red border is returned to the original call and is returned as the final result.
BTW: move to front variant would put points 0 and 2 "front" so it would not "choose" 0 at the P={0,1,2,3} R={4} stage (as move to front is not implementation of the algorithm frompage 362(363)). Hippo.69 (talk) 09:04, 13 December 2023 (UTC)[reply]
@David Eppstein ... So you have stopped talking here and you just revert the changes in the article without any reasoning? Is it personal or is there a better reason? Hippo.69 (talk) 20:41, 14 December 2023 (UTC)[reply]
Proposal for the changes ... to be reviewed and grammar corrected ...
Hmmm, the labels presented should (except the mentioned mistakes) correspond to algorithm presented here (in the pseudocode with interpretation that undefined means "empty set"), but it seems to me corresponds to abstract algorithm presented in the paper from 1991. (The text almost corresponds to the pseudocode, (I have ignored the proclamation that points of R ("fixed points") must be on the circle's boundary (as this is not supported in pseudocode) I have interpreted set S just as description of points which the current circle should enclose. The introducing sentence ... the algorithm is recursive corresponds to the pseudocode. Yes, the "fix" step is described wrongly, S should be reset rather to maintained. I agree the description is partially ambivalent, talking about set S would much better match the implementation where recursion was removed. Anyways in the implementation where recursion is removed, if you empty set S during fix and add points in random order, the algorithm behaves equivalently and the picture is counterexmple to it "as well"). Would you mind me making small changes in the presented algorithm and its presentation to make it less ambivalent? (pier rewiew welcomed).Hippo.69 (talk) 00:05, 3 March 2019 (UTC)[reply]
algorithm welzl is[1]input: Finite sets P and R of points in the plane |R| ≤ 3.
output: Minimal disk with all points of R on the boundary and containing P.
ifP is empty or |R| = 3 thenreturn minimal disc containing all points of R on its boundary
choosep in P (randomly and uniformly)
D := welzl(P − {p}, R)
ifp is in DthenreturnDreturn welzl(P − {p}, R ∪ {p})
... but I can just blame myself by writing trivial(R) end interpretting it as minimal disc containing R rather the minimal disc containing R on its boundary. Hippo.69 (talk) 16:47, 18 December 2023 (UTC)[reply]
Welzl described the algorithm in a recursive form (page 362 B_MINDISK).
For size of input set at most 3, trivial algorithm is created. It outputs empty circle, circle with radius 0, circle on diameter made by arc of input points for input sizes 0, 1 and 2 respectively.
For input size 3 if the points are vertices of sharp triangle, the circumscribed circle is returned. Otherwise the circle on diameter on the triangle longest edge is returned.
For bigger sizes the algorithm uses solution of 1 smaller size where the ignored point p is chosen randomly and uniformly.
The returned circle D is checked and if it encloses p, it is returned as result.
Otherwise we know point p is on border of the result. We rerun the algorithm again, but we call it with the information p is on the result circle boundary.
Points which are known to be on the boundary are accumulated in the set R and they are excluded from the subset P from which random choices are made in the following calls.
The condition to use the trivial algorithm is |P|=0 or |R|=3, and the trivial algoritm is called for R.
Equivalent condition would be |R|=3 or |P|+|R|≤3, and call of the trivial algoritm for R in the case |R|=3
and for union of P and R otherwise.
This would prevent some recursive calls on bottom of the recursion.
algorithm welzl:[2]input: Finite sets P and R of points in the plane |R|≤ 3
output: Minimal disk enclosing P with R on the boundary
ifP is empty or |R| = 3:
return trivial(R)
choosep in P (randomly and uniformly)
D := welzl(P - { p }, R)
ifp is in D:
return D
return welzl(P - { p }, R ∪ { p })
Welzl indicated implementation without need of recursion.
Empty R and random permutation of P is used at start.
Sets on bottom of recursion correspond to prefixes in the permutation.
Trivial algorithm is called for R extended by prefix of P to size of 3,
and following points are checked they are enclosed by it's result D.
Whenever check fails on point p, p is added to R and removed from P,
and the prefix of the permutation up to p is reshufled.
To make this implementation equivalent to the recursive one, we should maintain stack of prefix lengths and if
longer prefix than the top would be inserted, last point from R should be removed and inserted to P, the top prefix on the stack should be removed at the same time. Therefore the prefix length on stack would be nondecreasing from its top down.
When |R|=3, the points upto prefix length on top position of the stack are not checked.
Typical implementation uses one list(array) of points of R ∪ P with R in it's start, remembering the size of R, therefore sizeR could be used as stack pointer and it's decrements while top prefix length was smaller than the current prefix length to be inserted does all required actions.
Welzl also proposes functionally different version of the algorithm using random permutation of points on input,
where the points are not reshufled when the point p is moved to front of the list.
The algorithm is again presented in the recursive form.
Example of Welzl's algorithm run which returns wrong result
Matoušek, Sharir, Welzl implicitly warned that the assumption point moved to R remains on enclosing circle's boundary for all subsets of
R ∪ P does not hold, and the required additional condition is the radius of the enclosing circle does not decrease.
They did not stay the Welzl's algorithm is wrong, they just warned that it's assumption does not hold.
They proposed tiny change to the algorithm forcing the radius of the enclosing circle does not decrease.
If p is not in enclosing circle D of R ∪ P - { p },
the radius r of enclosing circle of D must be smaller than radius r' of enclosing circle D' of R ∪ P.
But radius of an enclosing circle of any subset of R ∪ P - { p } is at most r,
so whenever r*>r is radius of an enclosing circle of a subset of R ∪ P, p must be in its boundary.
MSW algorithm choses 3 random points of P as initial base R and they find initial
D by running the trivial algorithm on them.
The presented recursive version of the algorithm is very simillar to Welzl's.
Point p of P is chosen in random order and algorithm for the set P - { p } is called.
If p is not enclosed by returned circle D, p replaces one of 3 points in the base
(R ∪ P does not change, and |R| remains 3),
such that the enclosing circle of the new base encloses the point removed from the base.
The result recursion is restarted with changed P, R.
algorithm msw:[3]input: Finite sets P and R of points in the plane |R|=3
output: Minimal disk enclosing P ∪ RifP is empty
return trivial(R)
choosep in P (randomly and uniformly)
D := msw(P - { p }, R)
ifp is in D:
return Dq = nonbase(R ∪ { p }) (Welzl's algorithm for 4 points could be used to find what would not be in R)
return msw(P - { p } ∪ { q }, R ∪ { p } - { q })
Use of base extended by one point is mentioned in the paper.
If we put p to the extended base replacing extension,
we could use Welzl's recurrence to rearrange the extended base to base and the extra point.
You can look at it as allowing temporary decrease of radius r which would be restored when the extended base is finished.
The move to front version of Welzl's algorithm works according to this schema except the randomization of choices.
This is why it returns correct results, on the contrary to the Welzl's original algorithm.
Move to front version of welzl without recursion and one list for R ∪ P in view of msw algorithm
could be simplified by not maintaining the size of R at all.
Experiments indicate the move to front version have performance slightly better (say 2% less checks p belongs to D)
than the rerandomized one (of msw).
Run of Megiddo's algorithm phase, discarding from point set A,B,...,U needless points E, T.
Megiddo's algorithm[4] is based on the technique called prune and search reducing size of the problem by removal of n/16 of unnecessary points.
That leads to the recurrence t(n)≤ t(15n/16)+cn giving t(n)=16cn.
The algorithm is rather complicated and it is reflected in big multiplicative constant.
The reduction needs to solve twice the simillar problem where center of the sought-after enclosing circle is constrained to lie on a given line.
The solution of the subproblem is either solution of unconstrained problem or it is used to determine the half-pollen where the unconstrained solution center is located.
The n/16 points to be discarded are found the following way:
Points Pi are arranged to pairs what defines n/2 lines pj as their bisectors.
Median pm of bisectors in order by their directions (oriented to the same half-pollen determined by bisector p1) is found and pairs from bisectors are made, such that in each pair one bisector has direction at most pm and the other at least pm
(direction p1 could be considered as - or + according our needs.)
Line q in the p1 direction is placed to go through an intersection Qx such that there is n/8 intersections in each half-pollen defined by the line (median position).
Constrained version of the enclosing problem is run on line q what determines half=pollen where the center is located.
Line q' in the pm direction going through an intersection Qx' such that there is n/16 intersections in each half of the half=pollen not containing the solution.
Constrained version of the enclosing problem is run on line q' what together with q determines quadrant, where the center is located.
We consider the points Qk in the quadrant not contained in a half-pollen containing solution.
One of the bisectors of pair defining Qk has the direction ensuring which of points Pi defining the bisector is closer to each point in the quadrant containing the center of the enclosing circle. This point could be discarded.
The constrained version of the algorithm is also solved by the prune and search technique, but reducing problem size by removal of n/4 points
leading to recurrence t(n)≤ t(3n/4)+cn giving t(n)=4cn.
The n/4 points to be discarder are found the following way:
Points Pi are arranged to pairs.
For each pair intersection Qj of its bisector with the constraining line q is found.
(If intersection does not exist we could remove one point from the pair immediately).
Median M of points Qj on the line q is found and in O(n) time is determined which halfline of q starting in M
contains the solution of the constrained problem.
We consider points Qj from the other half.
We know which of points Pi defining Qj is closer to the each point of the halfline containing center of the enclosing circle
of the constrained problem solution. This point could be discarded.
The halfplane where the unconstrained solution lies could be determined by
the points Pi on the boundary of the constrained circle solution.
notes to Megiddo's algorithm not included on the main page
As medians could be considered part as either half, the recursion would prune points even when the size is 4,
but it terminates instead as the center would be on a constraining line.
No special case for small sizes is needed except for trivial ones before the recursion is invoked.
The intersections Qj are not well defined if bisectors in the pair are paralel. So we should prevent such pairs. Mentioned constraints allow paralel bisectors only in direction of p1 or pm, so we should distribute bisectors of these directions carefully.
If there is more than n/4 parallel pi's, we should rearrange some pairs.
Let px defined by (Px1,Px2) and py defined by (Py1,Py2) be two bisectors in the most common direction, we can make new pairs (Px1,Py1), (Px2,Py2) and we either got bisectors with different directions, differing from the original one or all 4 points Px1,Px2,Py1,Py2 are colinear and we could discard the middle 2.
This reduces n or the number of bisectors in the most common direction by 2 and increases the number of bisectors in the second most common direction by at most 1.
When the number of bisectors in the originally most common direction drops to at most n/4, the number of bisectors in the second most common direction grows to at most n/4 (where n is the number of nondiscarded points).
When each bisector direction is presented at most n/4 times, we could recompute pm (new pm cannot be paralel to p1) and choose pairs such that there are no paralel bisectors in them and algorithm could continue as described. (For random inputs the probability this problem needs to be solved is very close to 0).
I could not find neither the alleged Welzl algorithm without recursion nor the "algirithm msw" in the ref cited, despite perusing the two pdf texts several times. I guess I am not as smart as used to be 10 years ago, or these are in some other texts (the pdfs I was reading appear to be conference papers and may be incomplete compared to the final ones I dont have access to). @David Eppstein:
I read it on page 7 "One permutation suffices" ... "change the view of our procedure" ... with the presented code below.Hippo.69 (talk) 07:45, 11 May 2019 (UTC)
OH, OK, I am reading too much between lines :( there is just preparation of the permutation and not the recurrence removal. Hippo.69 (talk) 07:53, 11 May 2019 (UTC)[reply]
- Can you please double-check? Otherwise it looks like a piece of OR; some statements are particularly dubious, but I wouldn't bother until the fundamental question of refs answered. - Altenmann>talk03:02, 1 April 2019 (UTC)[reply]
Oh and the reference the msw algorithm ... page 5 SUBEX_lp(H,C). ("A subexponential bound for linear programming")
And on page 14 Smallest enclosing ball 2nd paragraph (P,r) is an LP-type problem ... meaning the radius r of the disc returned should only increase. .... "the problem is not basis-regullar, so we have to apply the above transformation to validate our analysis" ... meaning without using candidate basis we cannot guarantee the results are correct (and very hidden between lines as Welzl is among the authors ... what was the case of the paper from 1991).
The authors never explicitly mentioned the Welzls algorithm is not correct and J. Matousek died just when I have found first counterexamples.
