-
Notifications
You must be signed in to change notification settings - Fork 315
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Is the enclosing circle algorithm correct? #84
Comments
Initial condition from Fischer’s thesis: Output of implementation: The algorithm verifies that every circle (in L) is contained inside the enclosing circle, so it should be correct in the sense that it returns an enclosing circle. If you can demonstrate that’s not the case with a specific input, please let me know! I would be very surprised. Whether or not that enclosing circle is the minimum enclosing circle, that is harder to prove and beyond my capacity. I’m not really sure what else to do with this issue so I’m closing it, but please contribute if you can make it better. Thanks, Robin! |
Sure, that’s probably best. I suspect it’s fine, actually – I just don’t completely understand why. I’ll let you know if I find a concrete problem! |
If you learn and can teach me that would be most excellent. Cheers! |
I now pretty much believe that this algorithm is correct – which is interesting, since that is counter to the prevailing wisdom in the academy. If I’m right, correctness doesn’t depend on the order elements are chosen in. It’s possible for a recursive call to If I can pin down the remaining details of the proof, would you be interested in co-authoring a short paper? I think this would be of some interest to the computational geometry people, and it’s a joint effort in that you developed the algorithm and implicitly conjectured its correctness. |
That would be amazing! I would love to. |
If I understand this correctly, the following change would cause the algorithm to throw an error (but it doesn’t, or at least I can’t get it to by throwing random inputs at it… although those inputs were non-overlapping circles, which might be a factor): switch (B.length) {
case 0: break;
case 1: circle = enclose1(B[0]); break;
case 2: circle = enclose2(B[0], B[1]); break;
case 3: circle = enclose3(B[0], B[1], B[2]); break;
default: throw new Error;
} If switch (B.length) {
case 0: break;
case 1: circle = enclose1(B[0]); break;
case 2: circle = enclose2(B[0], B[1]); break;
case 3: circle = enclose3(B[0], B[1], B[2]); break;
default: return;
} But if your theory is correct we should definitely look for an input that can reproduce this case so that we can understand what’s happening. I added a test script in 98f0f6a, but a few thoughts:
|
Ah yes. This is a really interesting question, and I have no idea what the answer is. I’ve mainly been analysing the algorithm without the move-to-front optimisation, because it’s easier to keep track of what’s where. (I think the algorithm gives the right answer whatever order you use, even if it’s like Welzl’s unoptimised version where you pick the circle randomly at each step.) Like you I’ve noticed that these cases are hard to reproduce when move-to-front is in effect. So there’s another question here: does move-to-front actually prevent these cases from occurring at all? Without move-to-front it isn’t hard to find a case where a recursive call returns // Pretty-printers
function pp_circle(a) {
return a.name;
// return "(" + a.x + ", " + a.y + ", " + a.r + ")";
}
function pp_array(B) {
return B.map(pp_circle).join(",");
}
function pp_list(L) {
var s = [];
for (var node = L.head; node; node = node.next) {
s.push(node._);
}
return pp_array(s);
}
// Returns the smallest circle that contains circles L and intersects circles B.
function encloseN(L, B, level=0) {
console.log(" ".repeat(level) + "encloseN", pp_list(L), "[" + pp_array(B) + "]");
var circle,
l0 = null,
l1 = L.head,
l2,
p1;
switch (B.length) {
case 1: circle = enclose1(B[0]); break;
case 2: circle = enclose2(B[0], B[1]); break;
case 3: circle = enclose3(B[0], B[1], B[2]); break;
}
while (l1) {
p1 = l1._, l2 = l1.next;
if (!circle || !encloses(circle, p1)) {
// Temporarily truncate L before l1.
if (l0) l0.next = null;
else L.head = null;
B.push(p1);
circle = encloseN(L, B, level + 1);
B.pop();
// Reconnect the truncated list L.
if (l0) l0.next = l1;
else L.head = l1;
}
l0 = l1;
l1 = l2;
}
console.log(" ".repeat(level) + "returning", JSON.stringify(circle) || "undefined");
return circle;
} With this, if you define const a = {name: "a", x: 365, y: 90, r: 5},
b = {name: "b", x: 430, y: 90, r: 5},
c = {name: "c", x: 400, y: 150, r: 10},
d = {name: "d", x: 400, y: 100, r: 30},
D = {name: "D", x: 400, y: 500, r: 10}; and run
|
It returns the right answer even without the move-to-front heuristic? That is interesting. I was going to suggest that maybe the move-to-front heuristic does ensure correctness somehow. |
Yes. I suspected at first that move-to-front was making it work – as I said earlier in this thread – but now I think it works for any ordering. But now there is a separate question whether move-to-front has the further effect that no recursive call will ever return |
Yes, sorry, I forgot you mentioned that already! |
Update: I’m actively working on this in my sadly limited free time, and I’m hoping to have a (very) rough draft ready in the next week. |
Great! Whenever you’re ready and want to create a private repo and add me as a collaborator I’d be happy to take a look. |
Perfect! Yeah, that’s exactly what I am planning to do. |
@VladanMajerech Yes. This algorithm has been entirely replaced, because we realised it was wrong. We’re now using the MSW algorithm: see @mbostock’s write-up at https://beta.observablehq.com/@mbostock/miniball |
Actually in "A Subexponential Bound for Linear Programming" by Matousek, Sharir, Welzl. |
Reading back through this thread, it’s very misleading. Sorry! The discussion moved elsewhere (maybe to email?) after this thread was written, so reading this you’re only seeing the first part of the story. I no longer think it’s plausible that Welzl’s algorithm works in general to find the minimum enclosing circle; I seem to remember @mbostock even found an explicit counterexample. |
@VladanMajerech If you’re saying you can prove it’s correct with move-to-front and no shuffling, I would definitely be interested in reading that! I tried to prove that at one point (as mentioned in this thread), but I did not succeed. |
@robinhouston OK, You have encouraged me to continue in writing the article. I have not finished writing the proof, but I am almost sure I have it. ... sketch... Last 3 points define the circle (of radius My implementation differs, I use array and swap selected index with Move to front and reshufling affecting last You can see in the already presented picture of counterexample of original Welzl. The enclosing circle diameter was decreasing ... what allowed the fixed point to leave the boundary of the enclosing circle. |
@VladanMajerech In case it’s useful or interesting, there’s a very incomplete draft of a paper here that I started writing in 2017, and then stopped working on when it became clear that the MSW algorithm could be implemented more efficiently than Welzl’s algorithm, which meant it no longer seemed to have any practical significance. |
BTW: MSW is equivalent to not selecting from last |
I have updated the English wiki page. As my patch is equivalent to MSW, there is no reason to publish it as a paper 23 years after MSW corrected it. |
I have run repeated experiments with 1000 and 5000 random points and move to front (of all) without reshufling wins ... it saves about 3% reccurent calls compared to reshufling of n-4 points when we are fixing point with n remaining. |
So finally as David Epstein rejected my counterexample, I have reread the Welzl's original paper and I must say the algorithm is correct (actually only my argument it is incorrect was wrong). There is trick that when 3 points are fixed it returns circle determined by them even when they do not enclose the whole set. When the enclosing circle's diameter was decremented, there is surely point "on the stack" before the last fix outside the circle, so there would be less fixed vertices and the vertex will be outside the subresult, so the wrong solution would be rejected, the point fixed ... |
The algorithm is correct for a set of points, but not for a set of circles, I think. Which Wikipedia article is this? |
So finally I have rerun the tests with corrected implementation and it is still failing. |
I have some doubts about the correctness of the enclosing circle algorithm.
You’re using Welzl’s algorithm adapted for enclosing circles rather than points. It is known that this doesn’t work in general, as detailed in Chapter 5 of Kaspar Fischer’s thesis (2005). The fundamental problem is that the correctness proof (which works for an enclosing circle of a set of points) doesn’t carry over to enclosing differently-sized circles.
But you’re also using the move-to-front heuristic, and this makes matters a bit less certain. Fischer’s counterexample doesn’t appear to bite when move-to-front is in effect. (I have tried all permutations of his input circles, for example.)
So it’s possible that the algorithm is in fact correct, and that the move-to-front rule somehow prevents bad cases from happening. I don’t know. I do think the correctness or otherwise of this algorithm is an open question. (If there’s a proof of correctness out there I’d love to hear about it.)
The algorithm implemented in CGAL is provably correct, I believe.
The text was updated successfully, but these errors were encountered: