Hyperbolic Voronoi Diagrams Made Easy

摘要: We present a simple framework to compute hyperbolic Voronoi diagrams of finite point sets as affine diagrams.We prove that bisectors in Klein's non-conformal disk model are hyperplanes can be interpreted power Euclidean balls.Therefore our method simply consists computing an equivalent clipped diagram followed by mapping transformation depending on the selected representation space (e.g., Poincare conformal or upper-plane representations). discuss extensions this approach weighted and $k$-order diagrams, describe their dual triangulations.Finally, we consider two useful primitives for designing tailored user interfaces image catalog browsing application disk:(1) finding nearest neighbors, (2) smallest enclosing balls.