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

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

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

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

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

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

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

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