<p>I like your approach! When you mention your optimization I think a good way to go about it is by rotating the hexagonal grid and translating it till you find the least amount of circles that cover the region. You don't need to rotate 360 since the pattern is symmetric so just 360/6.</p>

<p>I've been working on this problem for a while and have just published a paper that contains code to solve this problem! It uses genetic algorithms and BFGS optimization. You can find a link to the paper here: <a href="https://arxiv.org/abs/2003.04839" rel="nofollow noreferrer">https://arxiv.org/abs/2003.04839</a></p>
Cover polygons with the minimum number of circles of a given diameter
<p><strong>The following problem:</strong>
Given is an arbitrary polygon. It shall be covered 100% with the minimum number of circles of a given radius.</p>

<p><strong>Note:</strong>
1) Naturally the circles have to overlap.
2) I try to solve the problem for ARBITRARY polygons. But also solutions for CONVEX polygons are appreciated.
3) As far as Im informed, this problem is NP-hard ( <a href="https://stackoverflow.com/questions/4282003/an-algorithm-to-find-the-minimum-size-set-cover-for-the-set-cover-problem">an algorithm to find the minimum size set cover for the Set-cover problem</a> )
Choose: U = polygon and S1...Sk = circles with arbitrary centers.</p>

<p><strong>My solution:</strong>
Ive already read some papers and tried a few things on my own. The most promising idea that I came up with was in fact one already indicated in <a href="https://stackoverflow.com/questions/1404944/covering-an-arbitrary-area-with-circles-of-equal-radius">Covering an arbitrary area with circles of equal radius</a>.</p>

<p>So I guess it’s best I quickly try to describe my own idea and then refine my questions.</p>

<p>The picture gives you already a pretty good idea of what I do</p>

<p><img src="https://i.stack.imgur.com/D58Yc.jpg" alt="enter image description here"></p>

<p><strong>IDEA and Problem Formulation</strong> 
1.  I approximate the circles with their corresponding hexagons and tessellate the whole R2, i.e. an sufficiently large area; keyword hexagonally closest packaging. (cyan … tessellation, red dotted, centers of the cyan hexagons)
2.  I put the polygon somewhere in the middle of this tessellated area and compute the number of hexagons that are needed to cover the polygon.</p>

<p>In the following Im trying to minimize N, which is number ofhexagons needed to cover the polygon, by moving the polygon around step by step, after each step “counting” N.</p>

<p><strong>Solving the problem:</strong>
So that’s when it gets difficult (for me). I don’t know any optimizers that solve this problem properly, since they all terminate after moving the polygon around a bit and not observing any change.</p>

<p><strong>My solution is the following:</strong>
First note that this is a periodic problem:
1.  The polygon can be moved in horizontal direction x with a period of 3*r (side length = radius r) of the hexagon.
2.  The polygon can be moved in vertical direction y with a period of r^2+r^2-2*r<em>r</em>cos(2/3*pi) of the hexagon.
3.  The polygon can be rotated phi with a period of 2/3*pi.</p>

<p>That means, one has to search a finite area of possible solutions to find the optimal solution.
So what I do is, I choose a stepsize for (x,y,phi) and simply brute force compute all possible solutions, picking out the optimum.</p>

<p><strong>Refining my questions</strong>
1)  Is the problem formulated intelligently? Right now im working on an algorithm that only tessellates a very small area, so that as little hexagons as possible have to be computed.
2)  Is there a more intelligent optimizer to solve the problem?
3)  FINALLY: I also have difficulties finding appropriate literature, since I don’t guess I don’t know the right keywords to look for. So if anybody can provide me with literature, it would also be appreciated a lot.</p>

<p>Actually I could go on about other things ive tried but I think no one of u guys wants to spend the whole afternoon just reading my question.</p>

<p>Thx in advance to everybody who takes the time to think about it.</p>

<p>mat</p>

<p>PS i implement my algorithms in matlab</p>