# Radar towers in a military field

The military field has rectangle shape with the dimension of 16 km to 12 km and recently there are some drone activities around the area and drones are not welcome to the military region!

Your commander gives you an order to put some small 2-km range radar towers in the region to detect and track these drones while they are flying in the field then it will be eliminated! So you cannot have any blind spot in the region, that means radars need to cover whole region to track the drone all the time.

What is the minimum number of radar towers you need to guarantee there is no blind spot in the region?

Notes:

• Radar tower has 2-km radius capacity, you may assume they are point for simplicity.
• Drones can be detected in spite of their height if they are in the horizontal range of the radar towers. In other words, this is 2-D question.
• Radars needed to be inside the military area for security.
• It's interesting that of the answers posted so far two say (roughly) "aha, I spotted the trick, you only need to cover the edge" and one says (roughly) "aha, really you only need to cover the edge, but I assume that's not the intention of the puzzle". If the latter is correct, then it might be worth editing the question to make it more explicit that you really do want the whole thing covered. Commented Oct 24, 2017 at 21:05
• @GarethMcCaughan you needto cover whole region, thats what i tried to mean by "no blind spot in the region"
– Oray
Commented Oct 25, 2017 at 4:51

(Now with coordinates.)

After more than a month of admiring the development of this puzzle’s poser’s solution of The farmer and the olive trees, I was ready to try a similar approach, and came up with...

The (northeast edges of) commas are at their circles’ centers.

Radar tower coordinates as text: (-6.83,4.37) (-4.20,4.67) (-1.33,4.53) (1.33,4.53) (4.20,4.67) (6.83,4.37) (-6.30,1.67) (-3.03,1.43) (0,1.07) (3.03,1.43) (6.30,1.67) (-7.60,-1.30) (-4.87,-1.60) (-1.70,-1.93) (1.70,-1.93) (4.87,-1.60) (7.60,-1.30) (-6.57,-4.63) (-3.40,-4.97) (0,-4.97) (3.40,-4.97) (6.57,-4.63)


This puzzle’s parameters also allow a perfectly fitting 5×5 (suboptimal) arrangement and other tantalizingly almost-perfect arrangements, one of which leads to a near-optimal 24-tower solution. These arrangements provide excellent clues, as the initial solution ensued from the near misses.

Initial solution.   More intriguing than the eventual solution.

Another 23-tower solution provided by Oray.   How this alternates (and warps) columns led to the present solution’s alternating (and warping) of rows.

• I thought for sure this must have been what you had in mind, @Oray. I haven't proven this works analytically, or tested it with a modeling program, but I have made some very slightly different sloppier variations that also seem to work, just barely. You might also like the other (analytically-provable) 24-tower solutions when their pictures are ready.
– humn
Commented Oct 25, 2017 at 12:24
• I have confirmed this answer is the right one. very brilliant one!
– Oray
Commented Oct 25, 2017 at 13:21
• Guess I only had one other 24-tower solution that worked after all, @Oray, now on display. This puzzle's innocent-looking parameters really pack a lot of tight adventure along the borders of solutions.
– humn
Commented Oct 25, 2017 at 14:56
• Thank you for adding that elegant refinement of 5x5 into 5-4-5-4-5, @Oray, this answer certainly was incomplete without it. Another delicate fit to reflect the puzzle's well-chosen parameters! Thank you also for taking the trouble to verify my solution.
– humn
Commented Oct 25, 2017 at 20:02
• Guess what, @Oray, your solution led to an improvement! The new solution has only one axis of symmetry but otherwise contains no precise regularity, so I constructed it with safe, though small, overlaps at triple junctions. I feel like I'm paralleling your adventure of solving The farmer and the olive trees.
– humn
Commented Oct 26, 2017 at 3:14

For the case the question also covers drones that appear from vacuum fluctuations:

I need 24 towers. In the image the hexagons have an edge length of 2 km, so that each of them is the territory of one of the towers.
Note: The biggest rectangle that would fit into the area in this constellation of towers would be $7 \cdot \sqrt{3} \, \text{km} \cdot 17 \, \text{km}$.

For those who might wonder whether the same arrangement needs less towers if the pattern is rotated by 90° with respect to the territory:

In this case there are many small pieces at the edges that need an extra tower. So it takes 26 towers (27 if I followed the pattern strictly and did not replace the two towers in the top right corner).

The question was extended, so that all towers must be inside the area:

Starting from the solution with 24 towers, to solve this, the military either has to expand its territory (with weapons) so that the short side of it is $7 \cdot \sqrt{3} \, \text{km}$. Then the upper towers are at the border of the territory.
If this military action is not so appreciated it is also possible to shift the towers lying outside to the border:

Now the towers on the top, left and bottom border are exactly on the border, but can still cover the whole area.

• Is that the same number if you tile with the hexagons (or field) rotated 90deg?
– user19641
Commented Oct 24, 2017 at 23:36
• You don't need vacuum fluctuations to explain the need to cover internal regions. It could be that they need to keep tracking the drone's position until they have time to shoot that drone down. Commented Oct 24, 2017 at 23:49
• could you mark tower locations?
– Oray
Commented Oct 25, 2017 at 5:36
• @oray I'd say it's fairly trivial they go in the center of each hexagon.. Commented Oct 25, 2017 at 6:53
• Also, question should probably include if all towers need to be built INSIDE the surveyed area. This image has towers outside the 'northern' edge of th rectangular area. Commented Oct 25, 2017 at 6:55

This question is equivalent to: how many radius-2 circles does it take to cover all of a 16x12 rectangle? Or, rescaling for convenience: how many radius-1 circles to cover all of an 8x6 rectangle?

(I remark that in practice it would probably be sufficient to put radar towers around the edge of the field, but never mind that.)

This is a problem to which no general solution is known. I'm not sure whether the optimal solution is known for this particular size, but here's a straw-man answer (I expect one can do better with a nearer-to-regular-hexagonal packing): suppose the field has (0,0)km at one corner and (16,12)km at the other, and then place towers at (0,2)+(4m,4n) and at (2,0)+(4m,4n). The total number of towers here is 5x3+4x4=15+16=31.

• yes, this is what is asked actually. :)
– Oray
Commented Oct 25, 2017 at 6:01

I believe you only need