Círculos cobrindo um retangular, como verificá-lo?

Isso pode ser básico para alguns de vocês, mas desculpe minha inexperiência com comp. geometria:

Dado um conjunto de $n$ círculos com centros $(x_i, y_i)$ para $1 \leq i \leq n$ e cada um com raios $r$. Também é dado um retângulo. Todos os objetos estão em um avião. Como verificar se todos os pontos dentro do retângulo (incluindo suas arestas) estão totalmente cobertos pelos círculos. Ou seja, cada ponto do retângulo está em pelo menos um dos círculos.

Alguém tem dicas? Atualmente, estou tentando com diagramas de voronoi.

Crie um diagrama Voronoi no $n$ centros de disco em $O(n\log n)$Tempo. Intersectá-lo com o retângulo em$O(n)$ Tempo.

Agora você tem um conjunto de formas convexas, portanto, o ponto mais distante do centro do disco dentro da célula é um vértice na célula. Calcular o ponto mais distante de cada célula pode ser feito em$O(n)$Tempo. Se para todos eles, está dentro$r$, o conjunto de discos cobre o retângulo.

UMA $O(n \log n)$ algoritmo.