Kreise, die ein Rechteck bedecken, wie kann man das überprüfen?

Dies mag für einige von Ihnen grundlegend sein, aber entschuldigen Sie meine Unerfahrenheit mit comp. Geometrie:

Gegeben eine Menge von Kreisen mit Zentren für und jeweils mit Radien . Auch ein Rechteck gegeben. Alle Objekte befinden sich in einer Ebene. So überprüfen Sie, ob jeder Punkt innerhalb des Rechtecks (einschließlich seiner Kanten) vollständig von den Kreisen bedeckt ist. Das heißt, jeder Punkt im Rechteck lag auf mindestens einem der Kreise. $n$ $(x_i, y_i)$ $1 \leq i \leq n$ $r$

Hat jemand Hinweise? Ich versuche gerade mit Voronoi-Diagrammen.

algorithms computational-geometry AJed
quelle

Eine mächtige Sache ist also

ϵ

$\epsilon$ -nets. Erstellen Sie ein

ϵ

$\epsilon$ Netz des Rechtecks und prüfen Sie, ob jedes Element im Netz auf einer Festplatte enthalten ist. Ich weiß nicht, was

ϵ

$\epsilon$ in diesem Fall sein soll, ich denke, es ist

r / 2

$r/2$ .

Chao Xu

Antworten:

Erstellen Sie in ein Voronoi-Diagramm auf den Plattenzentren . Schneiden Sie es mit dem Rechteck in Zeit. $n$ $O(n\log n)$ $O(n)$

Jetzt haben Sie eine Reihe konvexer Formen, sodass der am weitesten von der Mitte der Scheibe entfernte Punkt in der Zelle ein Scheitelpunkt auf der Zelle ist. Die Berechnung des am weitesten entfernten Punkts für jede Zelle kann in . Wenn es für alle innerhalb von , deckt der Satz von Datenträgern das Rechteck ab. $O(n)$ $r$

Ein -Algorithmus. $O(n \log n)$

Chao Xu
quelle

Ja, das ist richtig. Dies kann durch Widerspruch bewiesen werden.

AJed