Планарные геометрические остовы: различия между версиями

Плоские остовы применяются при решении задач поиска путей и маршрутизации в режиме онлайн, которые возникают, например, в географических информационных системах и сетях коммуникаций. В этих областях применения, как правило, среда в целом неизвестна, и маршрутизацию приходится осуществлять, зная только местонахождение источника, точку назначения и ближайших соседей текущей позиции. Бозе и Морин [4, 5] показали, что в рамках этой модели имеются эффективные стратегии маршрутизации для планарных графов, такие как триангуляция Делоне и графы, одновременно удовлетворяющие свойствам a-ромба и d-хорошего многоугольника. Эти стратегии являются конкурентными в том смысле, что длины рассчитанных путей не превышают произведения евклидова расстояния между источником и получателем на константный коэффициент. Кроме того, эти стратегии маршрутизации требуют ограниченного количества памяти.