Delone Triangulations
We have already illustrated the utility of Voronoi diagrams with the application in Section 6.5 . In fact, the neighborhood relations of points to each other which are expressed in Voronoi diagrams are used in their dual form in many other applications.
- PDF / 420,451 Bytes
- 18 Pages / 439.37 x 666.142 pts Page_size
- 49 Downloads / 196 Views
Delone Triangulations
We have already illustrated the utility of Voronoi diagrams with the application in Section 6.5. In fact, the neighborhood relations of points to each other which are expressed in Voronoi diagrams are used in their dual form in many other applications. This leads to the concept of Delone subdivisions (of the convex hull) of a point set. We shall discuss an application of this in Chapter 11. As part of our study of Delone triangulations, we will explore the relation of convex hull algorithms to triangulation methods and to the computation of volumes.
7.1 Duality of Voronoi Diagrams Let S ⊆ Rn be finite such that S affinely spans the space Rn . By Theorem 6.12 we know that a Voronoi diagram VD(S) is generated by the vertical projection of the polyhedron P(S) = s∈S T (s)+ ⊆ Rn+1 to the first n coordinates. Here, T (s) denotes the tangent hyperplane of the standard paraboloid U at the point sU := (s, s2 )T , and T (s)+ denotes the upper half-space. By Theorem 6.14, aff S = Rn implies that P(S) has a vertex, i.e., it is pointed. Therefore, by Theorem 3.36, P(S) is projectively equivalent to a polytope. In the following we describe how to construct a polytope which is projectively equivalent to P(S). defined by the To do this, we examine the projective transformation π of Pn+1 R (n + 2) × (n + 2)-matrix ⎛ ⎞ 1 0 ... ... 0 1 ⎜ 0 2 0 . . . 0 0⎟ ⎜ ⎟ ⎜ .. .. .. ⎟ .. .. ⎜ . . . . .⎟ 0 ⎜ ⎟ ⎜ .. .. . . . . .. ⎟ . ⎜ . . . . 0 .⎟ ⎜ ⎟ ⎝ 0 0 . . . 0 2 0⎠ −1 0 . . . . . . 0 1 As we have previously done, we regard Rn+1 as a subset of Pn+1 R via the embedding ι introduced in Section 2.1. M. Joswig, T. Theobald, Polyhedral and Algebraic Methods in Computational Geometry, Universitext, DOI 10.1007/978-1-4471-4817-3_7, © Springer-Verlag London 2013
99
100
7
Delone Triangulations
Fig. 7.1 An illustration of the standard parabola and of the map π inducing the stereographic projection
Lemma 7.1 The projective transformation π maps the standard paraboloid U ⊆ Rn+1 to the unit sphere Sn ⊆ Rn+1 . The only point on Sn which is not contained in the image of U under π is the north pole (1 : 0 : · · · : 0 : 1)T . The tangential hyperplane [1 : 0 : · · · : 0 : 1] at the north pole is the image of the ideal hyperplane under π . Proof For a point s ∈ Rn we have
T
T π 1 : s1 : · · · : sn : s = 1 + s2 : 2s1 : · · · : 2sn : s2 − 1 , and also 1 + s2 > 0. The square of the norm of the (affine) image point is
1 + s2 : 2s1 : · · · : 2sn : s2 − 1 T 2 2
=
4s12 + · · · + 4sn2 + (s2 − 1) (1 + s2 )
2
= 1. This implies that π(s) lies on the unit sphere. Since π induces a stereographic projection from Rn to Sn \ {(1 : 0 : · · · : 0 : 1)T }, we can show that (1 : 0 : · · · : 0 : 1)T is the only point on Sn that is not contained in the image of π . To do this, it suffices to study the case n = 1. The affine point
2s s2 − 1 T π(sU ) = , 1 + s2 1 + s2 is the intersection point of the unit circle and the connecting line of (s, 0)T with the north pole (0, 1)T ; see Fig. 7.1. The last statement, i.e., t
Data Loading...
