Граф полу-Яо
Граф k -полу-Яо ( k -SYG ) набора из n объектов P представляет собой граф геометрической близости, который был впервые описан для представления кинетической структуры данных для обслуживания всех ближайших соседей движущихся объектов. [1] Он назван в честь своего родства с графом Яо , названным в честь Эндрю Яо .
Строительство
[ редактировать ]k . -SYG строится следующим образом Пространство вокруг каждой точки p в P разделено на набор многогранных конусов с углом раскрытия , то есть угол каждой пары лучей внутри многогранного конуса, исходящего из вершины, не превышает , а затем p соединяется с k точками P в каждом из многогранных конусов, проекции которых на ось конуса минимальны.
Характеристики
[ редактировать ]- k - SYG, где k = 1, известен как тета-граф и представляет собой объединение двух триангуляций Делоне . [2]
- Для небольшого и соответствующую ось конуса, k -SYG дает суперграф графа k -ближайших соседей ( k -NNG ). [3] [4] Например, в 2D, если мы разделим плоскость вокруг каждой точки на шесть клиньев с равными углами и выберем оси конуса по направлениям биссектрис конуса, мы получим k -SYG как суперграф для k -NNG.
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Рахмати, Захед (2014). Простые и быстрые кинетические структуры данных (PDF) (Диссертация). Университет Виктории.
- ^ Боничон, Н.; Гавой, К.; Ханусс, Н.; Ильчинкас, Д. (2010). «Связи между тета-графами, триангуляциями Делоне и ортогональными поверхностями». Концепции теории графов в информатике . стр. 266–278.
- ^ Рахмати, З.; Абам, Массачусетс; Кинг, В .; Уайтсайдс, С. ; Зарей, А. (2015). «Простой и быстрый метод решения проблем кинетической близости» . Вычислительная геометрия . 48 (4): 342–359. arXiv : 1311.2032 . дои : 10.1016/j.comgeo.2014.12.002 .
- ^ Рахмати, З.; Абам, Массачусетс; Кинг, В .; Уайтсайдс, С. (2019). «Кинетический граф К -Полу-Яо и его приложения». Вычислительная геометрия . 77 : 10–26. arXiv : 1412.5697 . дои : 10.1016/j.comgeo.2015.11.001 .