A366544 - OEIS

%I #49 Jan 22 2024 12:49:44

%S 1,1,1,1,2,3,3,3,2,2,3,5,8,6,5,3,4,7,10,21,21

%N a(n) is a lower bound for the number of distinct stable centroidal Voronoi tessellations (CVTs) of a square with n generators (seeds).

%C Stable CVTs are local minimizers of the CVT function (see first paper).

%C There are other CVTs which are saddle points.

%C Lloyd's process converges only to stable CVTs.

%C An efficient two-step semi-manual algorithm is used to recognize identical patterns and a fast code for the Lloyd's process.

%D Lin Lu, F. Sun, and H. Pan, Global optimization Centroidal Voronoi Tessellation with Monte Carlo Approach, 2012 IEEECS Log Number TVCG-2011-03-0067.

%H Denis Ivanov, <a href="https://github.com/lesobrod/CVT">Code, explanations and results</a> (github).

%H J. C. Hateley, H. Wei, and L. Chen, <a href="https://doi.org/10.1007/s10915-014-9894-1">Fast Methods for Computing Centroidal Voronoi Tessellations</a>, J. Sci. Comput., 63, pp. 185-212, 2015.

%H Yang Liu, Wenping Wang, Bruno Lévy, Feng Sun, Dong-Ming Yan, Lin Lu, and Chenglei Yang, <a href="https://doi.org/10.1145/1559755.1559758">On centroidal Voronoi tessellation—Energy smoothness and fast computation</a>, ACM Transactions on Graphics, Volume 28, Issue 4, Article No. 101, pp. 1-17, 2009.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Centroidal_Voronoi_tessellation">Centroidal Voronoi tessellation </a> (unfortunately, article is a stub and contains inaccuracies).

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Lloyd%27s_algorithm">Lloyd's algorithm</a>.

%e As initialization, clustering centers for a large number of points in the square are used. For every set of centers, Lloyd's algorithm is iterated and all variants symmetric with respect to rotations and reflections are removed.

%Y Cf. A363822 (disk).

%K nonn,hard,more

%O 0,5

%A _Denis Ivanov_, Oct 12 2023