Minimum placement of circles in polygon

Question

I have a variably sized 4 sided polygon in 2D space.

I can draw circles inside this polygon which have a fixed radius (500 meters).

I need to cover all the surface area of this polygon, using these fixed sized circles, however I want to draw the least amount of circles possible (require total surface area coverage with minimal number of total circles).

Here is a simple diagram for a square shape (this is made by hand, all circles should be the same size, I also do not think this is an optimal example, but unsure).

Can somebody help with an algorithm which would solve this problem?

Answer 1

Packing and covering problems are hard (as in "NP-hard", though I'm not exactly sure of that) and riddled with counter-intuitive results. There are algorithms (see this one, for instance) which are known to produce "not very bad" (but not necessarily optimal) solutions; if that suits you, go for it.

And if you have to do this just once, do it by hand.