Hyperbolic Voronoi Diagram: A Fast Method

oronoi diagrams have useful applications in various fields and are one of the mostfundamental concepts in computational geometry. Although Voronoi diagrams in the plane have beenstudied extensively, using different notions of sites and metrics, little is known for other geometricspaces. In this paper, we present a simple method to construct the Voronoi diagram of a set of pointsin the Poincare hyperbolic disk, which is a 2-dimensional manifold with negative curvature. Our trickis to define and use some well-formed geometric maps which take care of connection between theEuclidean plane and Poincare hyperbolic disk. Finally, we give a brief report of our implementation.

Keywords:

Computational geometry , Hyperbolic space , Geodesic , Voronoi diagrams