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

Важнейшей нерешенной проблемой является разрыв между <math>\Omega(n) \;</math> и O(n log n) в количестве необходимых пар на плоскости. Кроме того, временная граница <math>(1 + \varepsilon) \;</math>-аппроксимации до сих пор близка к <math>\tilde{O} (n \sqrt{n})</math> из-за отсутствия эффективных способов вычисления <math>(1 + \varepsilon) \;</math>-приближенных расстояний по кратчайшим путям между O(n) парами точек. Любое улучшение алгоритма решения этой задачи немедленно приведет к улучшению всех алгоритмов <math>(1 + \varepsilon) \;</math>-аппроксимации, упоминавшихся выше.