Декомпозиция на значительно удаленные пары: различия между версиями

Для графа общего вида неизвестно, можно ли вычислить расстояния по кратчайшим путям между O(n log n) парами значительно быстрее, чем расстояния по кратчайшим путям между всеми парами. Для планарного графа можно ли вычислить расстояния по кратчайшим путям между O(n log n) парами за время <math>O(n \sqrt{n \; log \; n})</math>, используя сепараторы размера <math>O( \sqrt{n}) \;</math> [2]. Этот метод можно расширить на графы единичных дисков с ограниченной константой плотностью, поскольку такие графы удовлетворяют свойству [[Сепараторы в графах|сепараторов]], аналогичному свойству для планарных графов [13]. Что касается аппроксимации, Торуп [15] недавно предложил алгоритм для планарных графов, способный отвечать на запросы о <math>(1 + \varepsilon) \;</math>-кратчайшем расстоянии за время <math>O(1 / \varepsilon) \;</math> после выполнения предварительной обработки, требующей почти линейного времени. К сожалению, алгоритм Торупа использует сбалансированные сепараторы кратчайших путей в планарных графах, которые невозможно сходу распространить на графы единичных дисков. С другой стороны, известно, что существует планарный 2,42-остов для графа единичных дисков [11]. Применяя алгоритм Торупа к этому планарному остову, можно вычислить 2,42-аппроксимацию кратчайшего расстояния для O(n log n) пар за почти линейное время.