Revisiting Hyperbolic Voronoi Diagrams from Theoretical, Applied and Generalized Viewpoints
Revisiting Hyperbolic Voronoi Diagrams from Theoretical, Applied and Generalized Viewpoints
复制标题
DOI：
10.1109/isvd.2010.13
复制
发表时间：
2010-06
期刊：
影响因子：
--
通讯作者：
T. Tanuma;H. Imai;Sonoko Moriyama
中科院分区：
文献类型：
--
作者：
T. Tanuma;H. Imai;Sonoko Moriyama
Onishi 等人自 1990 年代中期以来一直在研究双曲空间中的 Voronoi 图（简称双曲 Voronoi 图）以及信息几何散度方面的 Voronoi 图。本文从背景理论、新应用和几何扩展三个角度重新审视双曲 Voronoi 图。首先，从统计估计和信息几何的角度来看，在正态分布的参数空间中，双曲Voronoi图是由Fisher度量导出的，而散度图是由双平面结构上的Kullback-Leibler散度给出的。我们证明双曲 Voronoi 图通过类似于对偶平坦空间中两个平坦坐标之一的线性化而变得平坦，并且它是某些幂图的一部分。这为尼尔森和诺克最近在双曲克莱因模型（完全不同的线性化模型）上获得的结果提供了另一个证明。鉴于线性化具有信息几何解释，我们的结果很有趣。其次，从新应用的角度，讨论双曲Voronoi图与双曲平面上的贪婪嵌入之间的关系。克莱因伯格证明了在双曲平面上贪婪路由总是可能的。我们指出，先前关于贪婪嵌入的研究结果使用了任何树都可以轻松实现为双曲 Delaunay 图的属性。最后，我们概括了双曲 Voronoi 图的位点。具体来说，我们考虑上半平面测地线段的 Voronoi 图，并为其提出一种算法。
Voronoi diagram in the hyperbolic space, hyperbolic Voronoi diagrams for short, as well as that with respect to information-geometric divergences has been investigated since mid 1990’s by Onishi et al. This paper revisits the hyperbolic Voronoi diagram from three standpoints, background theory, new applications, and geometric extensions. First, viewed from statistical estimation and information geometry, in the parametric space of normal distributions, the hyperbolic Voronoi diagram is induced by the Fisher metric while the divergence diagram is given by the Kullback-Leibler divergence on a dually flat structure. We show that the hyperbolic Voronoi diagram becomes flat by a linearization similar to one of two flat coordinates in the dually flat space, and it is a part of some power diagram. This gives another proof for the result recently obtained by Nielsen and Nock on the hyperbolic Klein model, completely different linearized model. Our result is interesting in view of the linearization having information geometric interpretations. Second, from the viewpoint of new applications, we discuss the relation between the hyperbolic Voronoi diagram and the greedy embedding in the hyperbolic plane. Kleinberg proved that in the hyperbolic plane the greedy routing is always possible. We point out that results of previous studies about the greedy embedding use a property that any tree is realized as a hyperbolic Delaunay graph easily. Finally, we generalize sites of hyperbolic Voronoi diagrams. Specifically, we consider Voronoi diagrams of geodesic segments in the upper half-plane and propose an algorithm for them.