Page 121 - Geometric Modeling and Algebraic Geometry

122 T. Beck and J. Schicho
Z 2 Z 2 s
5 6 5 v 5 = v 6
Π
6 7
4 Π 2 4 v 7 = v 0 v 4
Π 1
(a 2 ,b 2 ) v 3
3 3 v 1 v 2 e 2
h 2
r
1 2 1 2
Fig. 7.2. General convex polygons

If the polygon has this shape we say it is smooth and an abstract smooth surface can
be constructed in pretty much the same way as above.
A general convex polygon will unfortunately not fulfill condition (7.2), see for
example Π 1 in figure 7.2. Here the pair of vectors attached to the edge 5 does not
span the entire lattice. However the situation can be fixed, when we consider instead
the polygon Π 2 , which was generated from Π 1 by “inserting” an additional edge.
To describe the following procedure precisely it is convenient to work with inner
normal vectors instead of edge direction vectors and introduce some further termi-
nology, see also figure 7.2 right. Let Π ⊂ R be the convex hull of a finite set of
2
lattice points in Z .
2
For any pair of relatively prime integers a, b,let c(a, b) ∈ Z be the minimal value
of ar + bs, where (r, s) ∈ Π. Then Π is a finite intersection of say n support half
planes

h i := {(r, s) ∈ R | a i r + b i s ≥ c i }
2
where the (a i ,b i ) are inward pointing normal vectors and c i := c(a i ,b i ). We assume
them to be cyclically arranged, i.e. a i−1 b i − a i b i−1 > 0 (setting a 0 := a n and
b 0 := b n ). We also give names to the edges and the vertices of intersection
e i := {(r, s) ∈ Π | a i r + b i s = c i } and v i := e i ∩ e i−1 .

Note that the set of half planes is not uniquely defined, there may be redundant half
planes where an edge meets Π in one vertex (in this case, some of the vertices v i will
coincide). Using the redundancy of this representation, we can enforce a condition
similar to (7.2), namely we may assume
a i−1 b i − a i b i−1 =1 for 1 ≤ i ≤ n. (7.3)

This condition holds for example for the polygon in figure 7.2 right because an ad-
ditional normal vector was introduced at the vertex v 5 = v 6 . If only two edges meet
in one vertex conditions (7.2) and (7.3) are easily shown to be the same. In the fol-
lowing we sketch an algorithm to ensure condition (7.3). This makes it more precise