Constructing Spherical Codes by Global Optimization Methods

Reference:

Kari J. Nurmela. Constructing spherical codes by global optimization methods. Research Report A32, Helsinki University of Technology, Department of Computer Science and Engineering, Digital Systems Laboratory, Espoo, Finland, February 1995.

Abstract:

In this work we search for spherical codes in three to five dimensions using different global optimization methods. In three dimensions the problem of finding optimal spherical codes is the Tammes problem, which asks, how to pack k circular caps on the surface of a sphere so that the diameter of the caps is as large as possible. The optimal codes are known only when k is small. The problem of spherical codes has close connections to sphere packings and kissing numbers. A variable repulsion-force based approximation of the packing problem is used. This method has been used previously in three dimensions and it is generalized into n dimensions in this work. The potential energy of the point configuration is minimized by using ordinary local optimization algorithms and stochastic global optimization algorithms. New methods that are used employ problem-specific heuristics with simulated annealing and tabu search. It is shown how to reduce the number of optimization variables by restricting the solutions to have certain symmetries. Three new 3-dimensional codes with 43, 77 and 80 code points are given. Most of the 4- and 5-dimensional codes in this work are better than the previously known codes.

Keywords:

spherical codes, spherical circle-packings, global optimization, stochastic optimization, combinatorial optimization.

Suggested BibTeX entry:

@techreport{HUT-TCS-A32,
    address = {Espoo, Finland},
    author = {Kari J. Nurmela},
    institution = {Helsinki University of Technology, Department of Computer Science and Engineering, Digital Systems Laboratory},
    month = {February},
    number = {A32},
    pages = {136},
    title = {Constructing Spherical Codes by Global Optimization Methods},
    type = {Research Report},
    year = {1995},
}