Покрытие простого многоугольника с кругами

Предположим, у меня есть простой многоугольник и целое число k . Каковы некоторые существующие подходы для нахождения наименьшего радиуса ¨R таким образом, что я могу покрыть S с K окружностей радиуса г ? Как насчет, если г фиксирован, и я хочу минимизировать к ?$S$$k$$r$$S$$k$$r$$r$$k$

Используйте алгоритм кластеризации k-центра: см. Раздел 4.2 в http://goo.gl/pLiEO .

С помощью скользящих сеток можно получить алгоритм приближения 1 + eps.

Естественно предположить, что проблема NP-Hard из-за работы Федера и Грина.

Вы также можете проверить https://pdfs.semanticscholar.org/056b/67e975ab09fcbece8daa65710cef7d664763.pdf, в то время как в статье описывается метод покрытия равностороннего треугольника, этот подход является общим и является тем, что вы ищете для произвольного