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

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

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

Перенос фокуса на другой узел переносит его в центр диска, в то время как не интересующая нас порция дерева сжимается.

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

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

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

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

См. также

• Геометрия Лобачевского
• Двоичное замощение
• Визуализация информации
• Радиальное дерево — is also circular, but uses linear geometry.
• Дерево (структура данных)
• Дерево (теория графов)

Ссылки

• d3-hypertree — HTML5 Hyperbolic tree implementation, MIT licensed
• Hyperbolic Tree of life — Open source tree of life visualisation using Open Tree of Life data set
• The Green Tree of Life — Tree of life — University of California at Berkeley and Jepson Herbaria
• Tree of life Similar to the above, but with pictures
• RougeViz supports hyperbolic trees.