Maximal covering of a point set by a system of circles via simulated annealing
Stefan M. Filipov, Stefan Panov, Fani N. Tomova, Vanya D. Kuzmanova · 2021 International Conference Automatics and Informatics (ICAI) · 2021
This work considers the problem of maximal covering of a set of points in the plane by a system of circles. The circles are allowed to swap their positions. The aim is to find a configuration of circles such that the number of points that are covered by at least one of the circles is maximum, hence the number of points that are not covered is minimum. Since the number of possible configurations is huge even for a relatively small number of circles, exhaustive search (brute force) algorithms are not tractable. Therefore, an optimization technique has to be employed. However, for this particular problem, optimization algorithms that always make steps in the direction of the decrees of the number of uncovered points may not work because, as we prove in the paper, local minima different from the global minimum exist. To solve the problem, the method of simulated annealing is applied. The method is suitable for this problem since it allows for steps that increase the number of uncovered points, thus the simulation does not get stuck in local minima but overcomes them.