Introduction

Covering a rectangle with the minimum number of equal-radius circles is a geometric optimization problem, but there is an important caveat: the exact optimum is not something you should assume has a simple closed-form formula for every rectangle size. In practice, the useful answers are either a guaranteed covering construction or a search procedure that improves candidate layouts. The main distinction is between a mathematically exact optimum and a practical covering strategy that is easy to compute and implement.

Start with the Geometry

Suppose the rectangle has width W, height H, and each circle has radius r. A circle covers every point within distance r of its center. To cover the rectangle, every point in the rectangle must lie inside at least one circle.

A tempting but wrong shortcut is to divide rectangle area by circle area:

1import math
2
3W = 10
4H = 4
5r = 1
6
7lower_bound = math.ceil((W * H) / (math.pi * r * r))
8print(lower_bound)

This gives only a lower bound. It does not tell you how many circles are actually needed, because circles overlap and edge effects matter.

Guaranteed Square-Grid Covering

A simple constructive method comes from the square that fits inside a circle. A circle of radius r contains an axis-aligned square of side length sqrt(2) * r.

So one guaranteed way to cover the rectangle is:

1. tile the rectangle with squares of side sqrt(2) * r
2. place one circle at the center of each square

Then every point of each square is inside its circle.

1import math
2
3def square_grid_cover_count(width, height, radius):
4    step = math.sqrt(2) * radius
5    cols = math.ceil(width / step)
6    rows = math.ceil(height / step)
7    return rows * cols
8
9print(square_grid_cover_count(10, 4, 1))

This construction is easy and correct, but not always minimal.

Hexagonal Layout Is Usually Better

For covering the plane efficiently, staggered rows often outperform a plain square grid. A practical hex-like layout uses:

• horizontal spacing near sqrt(3) * r
• vertical spacing near 1.5 * r

The idea is to offset alternate rows so each row fits into the gaps of the previous one.

1import math
2
3def hex_cover_centers(width, height, radius):
4    dx = math.sqrt(3) * radius
5    dy = 1.5 * radius
6    centers = []
7    y = radius
8    row = 0
9
10    while y <= height + radius:
11        x_offset = radius if row % 2 == 0 else radius + dx / 2
12        x = x_offset
13        while x <= width + radius:
14            centers.append((x, y))
15            x += dx
16        y += dy
17        row += 1
18
19    return centers
20
21print(len(hex_cover_centers(10, 4, 1)))

This is a useful heuristic construction, especially when the rectangle is large relative to the circle size. But again, “useful” is not the same as “proven minimal for every dimension.”

Lower Bounds and Exact Search

If you truly need the minimum, you need more than one formula. A common workflow is:

1. compute a lower bound
2. build a valid covering with some heuristic
3. try to reduce the circle count with search or optimization

For small instances, you can discretize candidate center locations and search combinatorially. For larger instances, that becomes expensive quickly.

A rough lower bound is:

1import math
2
3def area_lower_bound(width, height, radius):
4    return math.ceil((width * height) / (math.pi * radius * radius))

But because edge and overlap effects are significant, the real answer may be substantially larger than this lower bound.

Validate Coverage Numerically

Whatever layout you choose, you should verify it. One pragmatic method is to sample points on a fine grid and confirm every sample point lies within at least one circle.

1import math
2
3def is_covered(width, height, radius, centers, step=0.1):
4    y = 0.0
5    while y <= height:
6        x = 0.0
7        while x <= width:
8            if not any((cx - x) ** 2 + (cy - y) ** 2 <= radius ** 2 for cx, cy in centers):
9                return False
10            x += step
11        y += step
12    return True

This is not a formal proof at arbitrary resolution, but it is a useful engineering check when experimenting with layouts.

A Practical Strategy

If you are solving a real application such as sensor placement or sprinkler coverage, a good practical approach is:

1. start from a hex-like pattern
2. test whether it covers the rectangle
3. adjust boundary rows and columns
4. compare against a square-grid upper bound

That usually gets you to a strong solution faster than chasing an exact symbolic answer that may not exist in simple form.

Special Cases

Some special cases are easy:

• if 2r >= diagonal of rectangle, one circle is enough
• if 2r >= H, then the problem reduces to covering the width with overlapping intervals

Example:

1import math
2
3def one_circle_enough(width, height, radius):
4    return 2 * radius >= math.sqrt(width * width + height * height)

Checking simple cases first can simplify the rest of the algorithm.

Common Pitfalls

The biggest mistake is assuming that dividing area by circle area gives the answer. Another is confusing packing with covering; covering allows overlap and has different geometry. Developers also often mistake a convenient grid construction for a proven minimum. Finally, if you test a layout numerically, a coarse sampling grid can miss uncovered boundary regions and give false confidence.

Summary

• Exact minimum circle covering of a rectangle is not generally a one-line formula problem.
• A square-grid construction gives a simple guaranteed upper bound.
• A staggered hex-like layout is often a better practical covering pattern.
• Area-based calculations provide lower bounds, not exact answers.
• If minimum really matters, combine bounds, candidate constructions, and explicit coverage validation.