Bedecken eines einfachen Polygons mit Kreisen

10

Angenommen, ich habe ein einfaches Polygon und eine ganze Zahl . Welche Ansätze gibt es, um den kleinsten Radius so zu finden, dass ich mit Kreisen mit dem Radius abdecken kann ? Wie wäre es, wenn fest ist und ich minimieren möchte ?Sr S k r r kkrSkrrk

cg.comp-geom planar-graphs set-cover user771871
quelle

Antworten:

11

Verwenden Sie den k-Center-Clustering-Algorithmus: siehe Abschnitt 4.2 unter http://goo.gl/pLiEO .

Man kann einen 1 + eps-Näherungsalgorithmus unter Verwendung von Gleitgittern erhalten.

Es ist natürlich anzunehmen, dass das Problem aufgrund der Arbeit von Feder und Greene NP-schwer ist.

Sariel Har-Peled
quelle
1
Das gibt Ihnen das
Gleitgitter
Vielen Dank für Ihre Antwort. Ich bin mehr oder weniger mit Gleitgittern vertraut. Im Punkteszenario beruht es entscheidend auf der Tatsache, dass in jeder Zelle des Gitters das Abdeckungsproblem optimal gelöst werden kann, da jede Platte zwei Punkte an ihrer Grenze enthält und die Anzahl der Platten, die die Zelle abdecken sollen, begrenzt ist. So kann man es rohe Gewalt lösen. Bei der Einstellung eines Polygons sehe ich jedoch nicht, wie das Problem in einer Gitterzelle optimal gelöst werden kann. Würde es Ihnen etwas ausmachen, einige Hinweise dazu zu geben?
101011
Gleitgitter bedeuten, dass die Lösungsgröße innerhalb der Gitterzelle klein ist. Dann müssen Sie das Problem in jeder Gitterzelle (normalerweise genau) mit einem anderen Algorithmus lösen. Hier ist eine alternative Möglichkeit, darüber nachzudenken: Probieren Sie das Polygon sehr dicht aus und lösen Sie dann Ihr Problem in der Stichprobe ... Und ja, genaue Details dazu können ziemlich schmerzhaft sein ... Nehmen wir also an, Sie haben eine Polygon mit n Kanten, und Sie wissen, dass die optimale Lösung die Größe k hat. Wissen Sie, wie Sie das Problem in diesem Fall genau lösen können?
Sariel Har-Peled
Danke nochmal. Nach einigem Nachdenken weiß ich immer noch nicht, wie ich das Polygon mit k Scheiben optimal abdecken soll, selbst wenn ich k kenne. Die Tatsache, dass es wenig diskrete Natur gibt, macht es mir wirklich schwer zu nähen. Was Ihren Stichprobenansatz betrifft: Möchten Sie nach der Stichprobe nur den Teil der Stichprobe abdecken? Stoßen wir dann nicht auf das Problem, viele Festplatten zu verschwenden, um die Lücken zu füllen?
101011
1
Betrachten Sie das Quadrat. Decken Sie es mit einem Gitter für . Es ist leicht einzusehen, dass jedes k Scheiben beweisen , dass deckt alle diese Punkte, würde den ganzen Platz abzudecken , nachdem Sie jede Scheibe durch Erweitern Bruchteil seines Radius. Triangulieren Sie das Polygon und bilden Sie für jedes Dreieck ein Gitter wie oben (dies erfordert einige Sorgfalt, ist aber nicht besonders schwierig). Sie erhalten dann die gleiche Garantie, wenn Sie die Vereinigung all dieser Punktmengen übernehmen. Dies ähnelt der Coreset-Konstruktion für das k-Center-Clustering. N = O ( k / ϵ ) ϵN×NN=O(k/ϵ)ϵ
Sariel Har-Peled