Теория и практика параллельных вычислений
Деление сети с использованием кривых Пеано
Одним из недостатков предыдущих графических методов является то, что при каждой бисекции эти методы учитывают только одну размерность. Таким образом, схемы, учитывающие больше размерностей, могут обеспечить лучшее разбиение.
Один из таких методов упорядочивает элементы в соответствии с позициями центров их масс вдоль кривых Пеано. Кривые Пеано – это кривые, полностью заполняющие области больших размерностей (например, квадрат или куб). Применение таких кривых обеспечивает близость точек фигуры, которые соответствуют точкам, близким на кривой. После получения списка элементов сети, упорядоченного в зависимости от расположения на кривой, достаточно разделить список на необходимое число частей в соответствии с установленным порядком. Получаемый в результате такого подхода метод носит в литературе наименование алгоритма деления сети с использованием кривых Пеано (the space-filling curve technique). Подробнее о методе можно прочитать в работах [[56], [58], [61]].
Рис. 10.14. Пример разделения сети на 3 части с использованием кривых Пеано
