Finding the minimum number of disks of fixed radius needed to cover a set of points in the plane by MaxiMinMax approach
Stefan Panov, Svetlana Panova, Atanas Garbev · 2022
This work evaluates the problem of finding the minimum number of disks of fixed radius needed to cover a given set of points in the plane. Two main algorithms are considered. The first of these always searches for a disk location in the plane that covers as many as possible of the currently uncovered points. It is expected such approach will lead to а minimum number of disks. For a plane defined by Cartesian coordinates, we can use computational techniques to decide how good candidate for a disk center each its point is. When searching for the best solution, critical is the sequence in which we find the covering disks. The second algorithm iteratively looks for a location that covers the maximum number of special input points not covered so far. For the latter algorithm a variation of the МaxiМin rule is applied. Both approaches are comprehensively tested for different number of input points as well as different radii. For the overwhelming majority of tests, the second method shows better or equal results compared to the first one.