Ссылки на диаграммы вороного самого большого пустого круга

Мне нужна ссылка, чтобы получить эту идею, которую я имею в виду:

Учитывая проблему с самым большим пустым кругом, я хочу определить, где разместить новые торговые центры.

Моя проблема: если у меня есть карта, разделенная надвое морем, моя диаграмма Вороного проходит по точкам без учета географического предела (т.е. если кто-то живет в левой части карты, этот человек не захочет пересекать море, чтобы пойти в торговый центр)

Есть ли возможность или ссылки, чтобы справиться с этим?

Кстати, я читал алгоритм Fortune перед


person Naty Bizz    schedule 24.05.2013    source источник
comment
Разве карты — по вашему определению — не пересекаются? Вороной/Фортуна предполагает идеальную декартову плоскость, которой у вас нет.   -  person msw    schedule 24.05.2013
comment
Аккуратно разорвите карту на две части по линии, проходящей через море — теперь решите свою задачу дважды.   -  person High Performance Mark    schedule 24.05.2013


Ответы (1)


Мне кажется, вы хотели бы наложить ограничения на положение центра C вашего самого большого пустого круга (LEC).

Реферат: ТУССЕН, Годфрид Т. Вычисление самых больших пустых кругов с ограничениями местоположения. Международный журнал компьютерных и информационных наук, 1983, 12.5: 347-358, говорится:

В частности, показано, что если центр C должен лежать в произвольном выпуклом n-угольнике, алгоритм O (n log n) все еще может быть получен.

Также: CHEW, Л. Пол; ДРИСДЕЙЛ, шотландец. Поиск самых больших пустых кругов с ограничениями местоположения. 1986. говорит:

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

person Alessandro Jacopson    schedule 19.06.2013