"I am currently engaged in optimizing the placement of sensors in an agricultural field, inspired by the problem outlined in the paper 'Approximation Algorithms for Robot Tours in Random Fields with Guaranteed Estimation Accuracy'.
The specific challenge I'm facing involves efficiently covering a convex polygon with circles of a constant radius $r$ (where the circle's area is always smaller than the polygon's). In my pursuit of a solution, I've encountered the algorithm proposed by Shai Gul in the paper 'Efficient covering of convex domains by congruent discs,' but its complexity poses implementation challenges.
Considering the NP-Hard nature of the problem, I am actively seeking alternative algorithms with worse approximations that may be more manageable for implementation.
Thank you in advance for any guidance or assistance.
Here is how I would attack this problem. First, ask yourself if the circles are to be overlapping, so as to leave no part of the polygon area uncovered, or just tangent to each other with uncovered deltoid spaces in between.
Then, find the centroid of the polygon and place a circle of the specified radius there. If the circles are to overlap, inscribe a regular hexagon in the circle, Otherwise, circumscribe the circle with the hexagon.
Now, build out a honeycomb with concentric rings of hexagons, so as to fill in the polygon. Finally, fill in the circles (inscribed are circumscribed) centered on each hexagon.