Гиперболическое дерево

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

Гиперболическое дерево (часто сокращается до гипердерево) — это метод визуализации информации и графов на основе геометрии Лобачевского.

Базовое гиперболическое дерево. Узлы в фокусе помещены в центре и им даётся больше места, в то время как узлы не в фокусе сжимаются ближе к краю.
Перенос фокуса на другой узел переносит его в центр диска, в то время как не интересующая нас порция дерева сжимается.

Представление иерархических данных в виде дерева страдает от роста визуального беспорядка, так как число узлов по уровням может расти экспоненциально. Для простого бинарного дерева максимальное число узлов на уровне n равно 2n, а для бо́льших деревьев число узлов растёт быстрее. Представление дерева как диаграммы связи узлов тогда требует экспоненциональное пространство для рисунка.

Один из подходов — использование гиперболического дерева, впервые предложенного Ламперингом, Рао и Пиролли[1]. Гиперболические деревья используют гиперболическое пространство, которое от природы имеет «больше пространства», чем евклидово пространство. Например, линейное увеличение радиуса окружности в евклидовом пространстве увеличивает его длину окружности линейно, в то время как длина той же окружности в гиперболическом пространстве будет расти экспоненциально. Использование этого свойства позволяет расположить дерево в гиперболическом пространстве в лаконичной манере — размещение узла достаточно далеко от его родителя даёт узлу почти то же количество пространства для расположения собственных детей, что и у его родителя.

Рисование гиперболического дерева обычно использует дисковую модель Пуанкаре гиперболической геометрии, хотя может быть использована также модель Кляйна — Белтрами. Обе модели располагают всю гиперболическую плоскость в единичном диске, что делает дерево видимым всё сразу. Единичный диск даёт образ плоскости как в линзе «рыбий глаз», выделяя узлы, находящиеся в фокусе, и показывая узлы вне фокуса ближе к краю диска. Обход гиперболического дерева требует преобразования Мёбиуса пространства, которые переносят новые узлы в фокус и переносят более высокие уровни иерархии из поля зрения.

Гиперболические деревья были запатентованы в США компанией Xerox[2].

См. также[править | править код]

Примечания[править | править код]

  1. Lamping, Rao, Pirolli, 1995, с. 401–408.
  2. Lamping; John O. & Rao; Ramana B., "Layout of node-link structures in space with negative curvature", US patent 5590250

Литература[править | править код]

Ссылки[править | править код]