On multiple coverings and packings problems in a two-dimensional non-Euclidean space

The article is devoted to the study of two significant problems of computational geometry. The first one is the multiple circle covering problem for a closed bounded set in a two-dimensional metric space, and the second one is the multiple circle packing problem. In the first case, the objective is to minimize the radius of the circles, in the second one is to maximize it. In both cases, the number of circles k is given. The considered metric is generally non-Euclidean. The source of such a statement is tasks from transport logistics, where the distance between objects is necessary to be replaced with a minimum time to travel between them. And optimum is not always achieved with straight line moving due to the terrain or urban features. We propose computational algorithms to solve these problems. They include the joint use of an optical-geometric approach based on the principles of Fermat and Huygens and the $K$-means method. The key step is to construct a generalized $k$-order Voronoi diagram. Each Voronoi cell with a fixed set of $n$ centroids includes points, which are closer to some $k$ centroids than to the remaining $n-k$. The cells can intersect each other. Computational experiments are carried out.