0
$\begingroup$

I have come across the following lemma in several papers (for instance see lemma 2.2 in this) (and some authors state this the proof immediately follows from basic properties of the stereographic projection).

A plane graph $G$ is realizable as a Delaunay tessellation in the plane, with face $F$ as the unbounded face, if and only if the graph $G^{'}$ obtained by stellating face $F$ in $G$ is inscribable.

A graph is said to be inscribable if it is polyhedral (that is there is a set of point in $\mathbb{R}^3$ whose convex hull is combinatorially equal to the graph) and if there is a specific realization where the polyhedron is inscribed in a sphere (all points of polyhedron on a sphere).

Can someone provide a short proof or reference?

I know that if one parabolically lifts points, then the lower convex hull is combinatorically equal to the Delaunay tessellation - but I don't see why the above lemma is true, and why stellating a face is needed?

$\endgroup$

2 Answers 2

4
$\begingroup$

Take a Delaunay triangulation with graph $G$ in the plane, thought of as the boundary of the Poincaré half-space model of hyperbolic 3-space. The hyperbolic convex hull of the vertices of $G$ together with the point at $\infty$ will give a convex polyhedron in hyperbolic space whose 1-skeleton is $G’$.

enter image description here

The stellation comes from adding the point at $\infty$, which gets coned to the outer face boundary when the convex hull is taken. See:

Springborn, Boris, Ideal hyperbolic polyhedra and discrete uniformization, Discrete Comput. Geom. 64, No. 1, 63-108 (2020). ZBL1518.30015.

The reason that this works is that the Delaunay triangulation is obtained by taking polygonal faces corresponding to maximal circumcircles whose interiors are disjoint from the vertices. These correspond to hemispheres in the upper half-space, ie hyperbolic geodesic planes, and intersections between these hemispheres associated to adjacent faces give hyperbolic geodesics which project to lines of the graph $G$. This corresponds to the convex hull because that is the intersection of half-spaces containing the points.

enter image description here

Now convert to the Poincaré ball model of hyperbolic 3-space by stereographic projection, then to the Klein model, to see an inscribed polyhedron. Reverse this process to see the converse.

enter image description here

enter image description here

$\endgroup$
2
  • 1
    $\begingroup$ what tools/software did you use to make these visuals? $\endgroup$ Commented Oct 18, 2023 at 3:10
  • 2
    $\begingroup$ I found them via internet search. The first one is from the linked paper, the second from wikipedia (linked). $\endgroup$
    – Ian Agol
    Commented Oct 18, 2023 at 3:36
0
$\begingroup$

You can also get the lemma like this: Consider the construction where you lift the points to the paraboloid and take the upper convex hull. Imagine vertical faces attached to the boundary edges of this upper convex hull, going up to infinity. Now apply a projective transformation that maps the paraboloid to the unit sphere. You get an inscribed convex polyhedron.

In short: It's really just the convex hull construction from a different projective point of view.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .