The k-Centre Selection Problem for Multidimensional Necklaces

This paper introduces the natural generalisation of necklaces to the multidimensional setting -- multidimensional necklaces. One-dimensional necklaces are known as cyclic words, two-dimensional necklaces correspond to toroidal codes, and necklaces of dimension three can represent periodic motives in crystals. Our central results are two approximation algorithms for the k-Centre selection problem, where the task is to find k uniformly spaced objects within a set of necklaces. We show that it is NP-hard to verify a solution to this problem even in the one dimensional setting. This strong negative result is complimented with two polynomial-time approximation algorithms. In one dimension we provide a 1 + f(k,N) approximation algorithm where f(k,N) = (log_q(k N))/(N-log_q(kN)) - (log^2_q(kN))/(2N(N-log_q(kN))). For two dimensions we give a 1 + g(k,N) approximation algorithm where g(k,N) = (log_q(k N))/(N-log_q(kN)) - (log^2_q(k))/(2N(N-log_q(kN))). In both cases N is the size of the necklaces and $q$ the size of the alphabet. Alongside our results for these new problems, we also provide the first polynomial time algorithms for counting, generating, ranking and unranking multidimensional necklaces.