Optimal Algorithms for Covering a Rectangle with Identical Circles
Ritwick Ghoshal, Arjun Raj, P. Jayakumar · 2023
The optimization problem of covering a given geometrical region, such as a rectangle, with the minimum number of identical circles has been extensively studied in various disciplines. The paper introduces two quadratic time algorithms to solve two variants of the problem. The first algorithm computes the configurations or positions of the circles to cover the rectangle provided the circles cannot overlap. The second algorithm computes the same for the problem variant where the circles can overlap. The algorithms proved effective in handling diverse rectangle sizes and circle radii, efficiently solving the problem of covering a given rectangular region with the minimum number of identical circles and finding their positions. The empirical evaluation shows that the two algorithms compute the configuration of circles with minimum overlap or loss respectively.