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). I

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?