Algorithms for constructing optimal n-networks in metric spaces

Abstract

We study optimal approximations of sets in various metric spaces with sets of balls of equal radius. We consider an Euclidean plane, a sphere, and a plane with a special non-uniform metric. The main component in our constructions of coverings are optimal Chebyshev n-networks and their generalizations. We propose algorithms for constructing optimal coverings based on partitioning a given set into subsets and finding their Chebyshev centers in the Euclidean metric and their counterparts in non-Euclidean ones. Our results have both theoretical and practical value and can be used to solve problems arising in security, communication, and infrastructural logistics.