Диаграмма Вороного в графе

Пусть граф с (положительно) взвешенными ребрами. Я хочу определить диаграмму Вороного для набора узлов / сайтов , чтобы связать с узлом подграф группы индуцированный всеми узлами строго ближе к чем к любому другому узлу в , измеряя длина пути по сумме весов на дугах. является «ы Вороной области . Например, зеленые узлы ниже находятся в $G$ $S$ $v \in S$ $R(v)$ $G$ $v$ $S$ $R(v)$ $v$ $R(v_1)$ и желтые узлы находятся в . Я хотел бы понять структуру диаграммы Вороного. Для начала, как выглядит диаграмма двух сайтов и , т. Е. Как выглядит двухсекторный биссектрис (синий в приведенном выше примере)? Я думаю о биссектрисе в качестве дополнения к в . Вот два конкретных вопроса: $R(v_2)$
введите описание изображения здесь
$v_1$ $v_2$ $B(v_1,v_2)$ $R(v_1) \cup R(v_2)$ $G$

Q1. Связан ли биссектриса двух сайтов в каком-то смысле?

Q2. Является ли выпуклым в том смысле, что он содержит кратчайший путь между любыми двумя узлами в ? $R(v)$ $R(v)$

Конечно, это было изучено ранее. Кто-нибудь может предоставить ссылки / указатели? Спасибо!

Приложение к комментарию Суреша:
введите описание изображения здесь

reference-request graph-theory cg.comp-geom Джозеф О'Рурк
источник

Для того, чтобы Q1 имел смысл, вам нужно какое-то чувство лица, верно? В противном случае «настоящий» биссектриса находится в середине ребер, и введение вершин непосредственно перед и после этой точки гарантирует, что биссектриса отключена. Может быть, если вы предполагаете, что график хордовый, вы можете что-то доказать. Что касается Q2: это неверно даже для геодезических в многоугольнике с отверстиями (или ландшафтами). Я предполагаю, что вам нужно предположить что-то довольно сильное на графике, чтобы получить нетривиальный ответ на оба вопроса.

Сариэль Хар-Пелед

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

Джозеф О'Рурк

ну, так что в обычной сфере ячейка вороной не может стать больше, чем полушарие, поэтому у вас нет этой проблемы. Но мой комментарий в целом был таким же, как и у Сариэля, в том, что вы просите выпуклость клеток вороного в потенциально родовом римановом многообразии, и это не должно быть правдой.

Суреш Венкат

S

$S$

S

$S$

K_{2, n}

$K_{2, n}$

Так что теперь я думаю, может быть, здесь есть интересный вопрос. Что, если основная метрика является многообразием (как предполагает Суреш). Теперь мы соединяем две точки тогда и только тогда, когда существует третья точка q, так что две другие точки являются двумя ближайшими соседями (представьте, что это своего рода комплекс свидетелей). Естественная гипотеза состояла бы в том, что, если многообразие удваивается, то всегда можно добавить O (1) точек так, что биссектриса связна. Хммм ...

Сариэль Хар-Пелед

Мелхорн, К .: Алгоритм более быстрого приближения для задачи Штейнера в графах. Письма Обработки Информации 27, 125–128 (1988)

Эрвиг, М .: График Вороного, диаграмма с приложениями. Сети 36 (3), 156–163 (2000)

обе ссылки скопированы с

Мэтью Т. Дикерсон, Майкл Т. Гудрич, Томас Д. Дикерсон, Ин Дэйзи Чжуо: круговые диаграммы Вороного и удвоение плотности в географических сетях. Труды по вычислительной науке 14: 211-238 (2011)

Дэвид Эппштейн
источник

Это займет некоторое копание, но на первый взгляд кажется, что многие структурные свойства диаграммы не были определены в этих статьях (возможно, потому что есть несколько свойств, которые следует отметить!).

Джозеф О'Рурк

на самом деле мало что известно; у нас есть другая лемма или две в sommer.jp/voronoi.htm

Кристиан Соммер

Диаграмма Вороного в графе

Ответы: