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

Дас и Джозеф [9] следующим образом обобщили утверждение теоремы 1 (см. рис 1). Пусть G – плоский граф с множеством вершин S, а a – вещественное число, 0 < a < л/2. Для любого ребра e графа G обозначим за A\ и Ai два равнобедренных треугольника с основанием e и углом при основании a. Ребро e удовлетворяет свойству a-ромба, если по меньшей мере один из треугольников A\ и Л 2 не содержит внутри точек множества S. Плоский граф G удовлетворяет свойству a-ромба, если каждое ребро e графа G удовлетворяет этому свойству. Для вещественного числа d > 1 граф G удовлетворяет свойству d-хорошего многоугольника, если для каждой грани f графа G и для каждых двух вершин p и q на границе f, таких, что соединяющий их отрезок прямой полностью находится в f, длина пути между p и q вдоль границы f не превышает d|pq|. Дас и Джозеф [9] доказали, что любой плоский граф, удовлетворяющий одновременно свойству a-ромба и свойству d-хорошего многоугольника, является t-остовом для некоторого вещественного числа t, которое зависит только от a и d. Значение t было несколько улучшено Ли [13]:

Планарные геометрические остовы, рис. 1