Pokrycie prostego wielokąta okręgami

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

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.

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