Buy Dideo Subscription
Hyperbolic Voronoi diagrams: Computed in Klein model as a clipped affine diagram and then rendered in other common models of hyperbolic geometry. We also visualize the k-order hyperbolic Voronoi diagram and navigate inside the hyperbolic space using hyperbolic translations and rotations. Video is part of the video programme of the 30th Annual Symposium on Computational Geometry (SoCG 2014) http://www.dais.is.tohoku.ac.jp/~socg2014/#video See http://arxiv.org/abs/0903.3287 ---- Here is the narration: Script for the video (version 3, last updated March 2014) Visualizing hyperbolic Voronoi diagrams ACM Symposium on Computational Geometry (SoCG), video track By Frank Nielsen and Richard Nock Slide: Visualizing Hyperbolic Voronoi diagrams Visualizing the hyperbolic Voronoi diagrams by Frank Nielsen and Richard Nock Slide: Hyperbolic geometry In hyperbolic geometry, there exist infinitely many lines passing through a given point and not intersecting another prescribed line.. Several models satisfying the axioms of hyperbolic geometry have been built within Euclidean geometry. In Klein model, the hyperbolic lines are straight Euclidean line segments clipped to the unit disk. Slide; Visualizing geodesics and bisectors Let us show the line segment passing through two points and its Voronoi bisector in the hyperbolic plane. In the Klein model, the blue hyperbolic segment is a Euclidean segment, and the red Voronoi bisector is a Euclidean line clipped with the limit circle. In the Poincare disk model, the segment and the bisector are arcs of circles perpendicular to the limit circle, Slide : Conformal versus non-conformal A conformal model preserves angles : That is, Euclidean angles measured in the model coincide with the hyperbolic angles. The hyperbolic bisector is perpendicular to the hyperbolic line segment. This is checked in the Poincare conformal model. Klein model is not conformal but well-suited for computation . Slide: Models of hyperbolic spaces Hyperbolic geometry is an abstract geometry fulfilling the axioms of hyperbolic geometry. There exist several models of the hyperbolic plane described as Riemannian manifolds embedded in 2D or 3D Euclidean space. Klein model is used for computing geometric structures and Poincare model for visualization. Other models have also their own merits. Slide: hyperbolic Voronoi diagram Since the Klein bisector is affine, the hyperbolic Voronoi diagram is affine in Klein model. Thus the hyperbolic Voronoi diagram can be computed equivalently as a power diagram clipped to the limit circle. Here is the hyperbolic Voronoi diagram of 50 sites in Klein model. It is equivalent to a clipped power diagram also called a weighted Voronoi diagram. In the power diagram, some cells may contain several weighted point generators, and some are empty. The Klein Voronoi diagram can be rendered in the Poincare conformal disk model. This is an overlay of the non-conformal Klein disk with the Poincare conformal disk models. This is the diagram rendered in the Poincare conformal upper plane model. Slide: Navigation Navigating interactively in the hyperbolic plane. In the Poincare disk, the orientation preserving isometries are described by Moebius transformations. We can perform a hyperbolic translation by applying such Moebius transformations. Here we choose a few positions inside the disk and perform a recentering using a hyperbolic translation. We now perform hyperbolic rotations. The k-order hyperbolic Voronoi diagrams This is the first order diagram. When we click at some position, its shows the closest neighbour in red. Since the Klein hyperbolic Voronoi diagram is affine, its k-order is also affine. Let us increase the order, k of the diagram. The last order is called the farthest Voronoi diagram. Slide: Visualizing simultaneously 5 standard models in 3D We visualize the hyperbolic Voronoi diagram in the 5 common models of hyperbolic geometry by embedding them altogether in 3D Euclidean space. All models except Klein are conformal. First in blue, is the Klein diagram located at z=1 plane. Then in red is the diagram rendered in the Poincare disk located at z=0 plane. In orange is the hemisphere model with bisectors supported by vertical hyperplanes. In purple is the diagram rendered on the hyperboloid upper sheet. Bisectors are hyperbola. This model is useful for manipulating isometries in high dimensions. Last in green, we visualize the diagram in Poincare upper plane.
