Pokrycie prostego wielokąta okręgami

Załóżmy, że mam prosty wielokąt i liczbę całkowitą . Jakie są istniejące podejścia do znalezienia najmniejszego promienia takie, że mogę pokryć z okręgi o promieniu ? A może zostanie naprawiony i chcę zminimalizować ? $S$ $k$ $r$ $S$ $k$ $r$ $r$ $k$

cg.comp-geom planar-graphs set-cover

— użytkownik771871
źródło

Użyj algorytmu klastrowania k-centrum: patrz punkt 4.2 w http://goo.gl/pLiEO .

Algorytm aproksymacji 1 + eps można uzyskać za pomocą przesuwnych siatek.

Naturalne jest założenie, że problemem jest NP-Hard z powodu pracy Federa i Greene'a.

— Sariel Har-Peled
źródło

Właśnie to daje przesuwana siatka ...

— Sariel Har-Peled

Dziękuję za Twoją odpowiedź. Znam mniej więcej przesuwne siatki. W scenariuszu punktów zasadniczo opiera się na fakcie, że w każdej komórce siatki można optymalnie rozwiązać problem pokrycia, ponieważ każdy dysk zawiera dwa punkty na granicy, a liczba dysków do pokrycia komórki jest ograniczona. W ten sposób można rozwiązać brutalną siłę. Ale w ustawieniu wielokąta nie widzę optymalnego rozwiązania problemu w jednej komórce siatki. Czy mógłbyś podać kilka wskazówek na ten temat?

— 101011

Przesuwne siatki oznaczają, że wewnątrz komórki siatki rozmiar rozwiązania jest niewielki. Następnie musisz rozwiązać problem w każdej komórce siatki (zwykle dokładnie) za pomocą innego algorytmu. Oto alternatywny sposób myślenia o tym - bardzo gęsto próbkuj wielokąta, a następnie rozwiąż swój problem na próbce ... I tak, dokładne szczegóły, jak to zrobić, mogą być dość bolesne ... Załóżmy, że masz wielokąta z krawędziami n, a wiesz, że optymalnym rozwiązaniem jest rozmiar k. Czy wiesz, jak dokładnie rozwiązać problem w tym przypadku?

— Sariel Har-Peled

Jeszcze raz dziękuję. Po dłuższym zastanowieniu nadal nie wiem, jak optymalnie pokryć wielokąt dyskami k, nawet jeśli znam k. Fakt, że jest mało dyskretny, sprawia, że szew jest dla mnie naprawdę trudny. Jeśli chodzi o twoje podejście do pobierania próbek: czy po zakończeniu pobierania próbek chciałbyś następnie objąć tylko próbkę? Czy nie mamy więc problemu z marnowaniem dużej ilości dysków, aby wypełnić luki?

— 101011

N \times N

$N \times N$

N = O (k / ϵ)

$N=O(k/\epsilon)$

ϵ

$\epsilon$

Możesz również sprawdzić https://pdfs.semanticscholar.org/056b/67e975ab09fcbece8daa65710cef7d664763.pdf, podczas gdy artykuł opisuje metodę pokrycia trójkąta równobocznego, podejście jest ogólne i jest to, czego szukasz

— kauii8
źródło