We propose a novel accelerated exact $k$-means algorithm, which performs better than the current state-of-the-art low-dimensional algorithm in 18 of 22 experiments, running up to 3$\times$ faster. We also propose a general improvement of existing state-of-the-art accelerated exact $k$-means algorithms through better estimates of the →