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

Очевидно, что любое множество <math>S = \{ s_1, ..., s_n \} \;</math> содержит декомпозицию на значительно удаленные пары. Достаточно просто рассмотреть любые пары одноэлементных множеств <math>( \{ s_i \}, \{ s_j \}) \;</math>, где i < j. Вопрос заключается в том, существуют ли декомпозиции, состоящие из менее чем <math>O(n^2) \;</math> пар, и возможно ли их эффективно построить.