"e-means wins by needing fewer passes over a huge dataset": the improvements of e-means are shown on datasets from 10k up to 10B points (you can try e-means against Lloyd at low problem sizes at https://e-means.github.io/playground.html) so I would not say huge datasets only. It depends on what you call huge obviously, and that's relative.
"It has the same objective and the same optimum, so at best it matches Lloyd." I strongly disagree with that. e-means has the same objective and the optimal clustering is set by the problem, but Lloyd doesn't find this optimal clustering in the vast majority of cases. Lloyd gets stuck in a local minimum, and what we find is that e-means reliably finds better clusterings than Lloyd in terms of MSE, but also other clustering metrics.
Regarding your usecase : I'd be curious to know what settings you used for e-means and a reproduction code. Don't hesitate to send me your code at swann@meta.com, I'm down to have a check because we're confident about e-means' performance against Lloyd.
Not impossible, just very expensive, because k-means is NP-hard, and finding the strictly optimal solution may require exponential time (or worse).
Edit: in fact you might end up going faster by moving the other way, set alpha = -0.1 and see what happens!
On the topic of these meshes, I'm currently exploring if we can come up with better meshing strategies in data-driven weather models (https://tcumulus.dev/blog/thesis/).