Hacker News Reader

> While their approach is clever, it is not guaranteed to converge in a fixed number of iterations.

Are you sure about it? I struggle to find a case where the quadtree version of their algorithm would not converge.

I didn't mean to imply that there were cases where it would Never converge, just that the number of iterations is not a-priori fixed or predictable.

My intuition is that the worst case scenario would be a fractal-like curve with multiple solutions (imagine a snake-like polygon following a Hilbert pattern). In that case the algorithm would need to explore all of the smallest squares, that gives us a higher bound on the number of iterations. It will be far less in most cases.

Would the delaunay-based algorithm be faster in the worst case?

Reply on news.ycombinator.com