Lloyd's algorithm

[foxyseta]

https://github.com/wo80/Triangle.NET/blob/48380f595243238fe5c131a7bdf5c47c21704335/src/Triangle/Smoothing/SimpleSmoother.cs#L84 I noticed that the loop for Lloyd's algorithm features a fixed number of iterations but doesn't consider any proper convergence criteria. Usually, iterative algorithms stop either when the maximum number of iterations are performed (in order to avoid divergence or very long execution times) or when convergence criteria are met (that is, when the current solution is considered "good enough"). If no convergence criteria are specified, then the algorithm always performs the fixed, maximum number of iterations $k$, even if the initial solution was already ideal/"good enough". In this scenario, the execution time is slowed down from $\Theta(1)$ to $\Theta(k \times f(n))$, assuming $f(n)$ is the cost for every iteration on an input of size $i$. Of course, even if the initial solution wasn't ideal/"good enough" already, checking the convergence criterium every time and abort as soon as possible may still save many iterations.

According to Wikipedia, when it comes down to Lloyd's algorithm, "One common termination criterion is to stop when the maximum distance moved by any site in an iteration falls below a preset threshold." This is perfectly in line with the usual, generic convergence criteria of checking whether the maximum norm of the error vector is below a constant, known threshold.

[wo80]

The mentioned stopping criterion "maximum distance moved by any site falls below a preset threshold" could be easily implemented in the Step method. Would you like to do a PR?

[foxyseta]

My pleasure! Feel free to close it or edit it in any way in case I messed anything up.