Какой тип алгоритма я могу использовать для поиска оптимального (минимальная площадь) покрытия ограниченной области плоскости XY с n дисками (x j ,y j , r j ) ?
Я нашел много исследований на дисках с фиксированным радиусом, но ничего о переменном радиусе.
n фиксирован, но диски могут быть размещены свободно (они не находятся в назначенных положениях, и их центры не обязательно должны находиться внутри региона).Область вообще не связана и не просто связана (может быть составлена из нескольких частей и может иметь отверстия).В моем конкретном случае определяется несколько замкнутых многоугольников (используется правило заполнения нечетно-четного).
Подводя итог:
Ввод:
Вывод:
- список
n дисков, описываемых центром x[i], y[i] и радиусом r[i], так что каждая точка области содержится как минимум в одном диске
Минимизация:
- площадь плоскости, охватываемая объединением дисков
Пример
В этом примере вход имел форму «A».Десять точек были помещены вручную, и были вычислены минимальные круги, охватывающие пересечение области с ячейками Вороного.
В настоящее время я изучаю подход, основанный на простом поиске центров x[i], y[i] и вычислении радиусов r[i] с помощью этого алгоритма (пространство поиска уменьшается на 10 n и всегда дает приемлемое решение).