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

-1

У меня есть замкнутый многоугольник, и я хотел бы полностью покрыть его набором K кругов разного радиуса, чтобы площадь, покрываемая кругами, но вне полигона минимальна. Это кажется идеальным кандидатом для линейного программирования. Кто-нибудь знает стандартную формулировку/алгоритм для этой проблемы?Покрытие многоугольника с кругами разного радиуса

источник

2015-07-20 Luca Fiaschi

Является ли ваш многоугольник выпуклым? Является ли 'K' заданным, фиксированным номером или числом, которое вы можете выбрать? И тот же вопрос для радиусов кругов? – WhatsUp

Многоугольник не может быть выпуклым, K фиксирован, а радиусы могут быть разными –

Каково точное значение 'K' в интересующем вас случае? Сложность сильно зависит от 'K'. – WhatsUp

-1

Вы можете взглянуть на Smallest-circle problem, что равнозначно вашей проблеме K = 1.

На приведенной выше странице Wiki сказано, что существует линейный алгоритм. Однако алгоритм, описанный в loc. соч. бумага Нимрода Мегиддо сложна.

Таким образом, я чувствую, что вы можете указать свою проблему с линейным программированием, но найти лучший алгоритм будет далеко не очевидным.

источник

2015-07-20 22:25:22 WhatsUp

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

ответ

Смежные вопросы