DOC PREVIEW
Duke CPS 296.1 - Piecewise Linear Functions

This preview shows page 1-2 out of 6 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

116 V Morse FunctionsV.3 Piecewise Linear FunctionsIn practical situations we rarely (or perhaps never) have smooth functions.Instead, we use other functions to approximate smooth functions. In this sec-tion, we use insights gained into the smooth case as a guide in our attempt tounderstand the piecewise linear case.Lower star filtration. Let K be a simplicial complex with real values speci-fied at all vertices. Using linear extension over the simplices, we obtain a piece-wise linear (PL) function f : K → R. It is defined by f(x) =Pibi(x)f(ui),where the uiare the vertices of K and the bi(x) are the barycentric coordinatesof x; see Section III.1. To emphasize that f is linear on every simplex, we pre-fer the above notation over the more accurate f : || K || → R. It is convenientto assume that f is generic by which we mean that the vertices have distinctfunction values. We can then order the vertices by increasing function valueas f(u1) < f(u2) < . . . < f(un). For each 0 ≤ i ≤ n, we let Kibe the fullsubcomplex defined by the first i vertices. In other words, a simplex σ ∈ Kbelongs to Kiiff each vertex ujof σ satisfies j ≤ i. Recall that the star ofa vertex uiis the set of cofaces of uiin K. The lower star is the subset ofsimplices for which uiis the vertex with maximum function value,St−ui= {σ ∈ St ui| x ∈ σ ⇒ f (x) ≤ f(ui)}.By assumption of genericity, each simplex has a unique maximum vertex andthus belongs to a unique lower star. It follows that the lower stars partitionK. Furthermore, Kiis the union of the first i lower stars. This motivates us tocall the nested sequence of complexes ∅ = K0⊂ K1⊂ . . . ⊂ Kn= K the lowerstar filtration of f. It will be useful to notice that the Kiare representativeof the continuous family of sublevel sets. Specifically, for f(ui) ≤ t < f(ui+1)tFigure V.8: We retract || K ||tto Kiby shrinking the line segments decomposing thepartial simplices from the top downward.V.3 Piecewise Linear Functions 117the sublevel set || K ||t= f−1(−∞, t] has the same homotopy type as Ki. Toprove this consider each simplex with at least one vertex in Kiand at least onin K − Ki. Write this simplex as a union of line segments connecting pointson the maximal face in Kiwith points on the maximal face in K − Ki, asshown in Figure V.8. The sublevel set || K ||tcontains only a fraction of eachsuch line segment, namely the portion from the lower endpoint x in || Ki|| tothe upper endpoint y with f(y) = t. To get a deformation retraction we letyλ= λx + (1 − λ)y be the upper endpoint at time λ. Going from time λ = 0 toλ = 1 proves that the sublevel set for t and Kihave the same homotopy type.PL critical points. Let us study the change from one complex to the nextin the lower star filtration in more detail. Recall that the link of a vertex is theset of simplices in the closed star that do not belong to the star. Similarly, thelower link is the collection of simplices in the lower star that do not belong tothe lower star. Equivalently, it is the collection of simplices in the link whosevertices have smaller function value than ui,Lk−ui= {σ ∈ Lk ui| x ∈ σ ⇒ f(x) < f(ui)}.When we go from Ki−1to Kiwe attach the closed lower star of ui, gluing italong the lower link to the complex Ki−1. Assume now that K triangulates ad-manifold. This restricts the possibilities dramatically since every vertex staris an open d-ball and every vertex link is a (d − 1)-sphere. A few examples oflower stars and lower links in a 2-manifold are shown in Figure V.9. We classifyFigure V.9: From left to right: the lower star and lower link of a regular vertex, aminimum, a saddle, and a maximum.the vertices using the reduced Betti numbers of their lower links. Recall that˜β0is one less than β0, the number of components. The only exception to thisrule is the empty lower link for which we have˜β0= β0= 0 and˜β−1= 1.Table V.1 gives the reduced Betti numbers of the lower links in Figure V.9.We call uia PL regular vertex if its lower link is non-empty but homologicallytrivial and we call uia simple PL critical vertex of index p if its lower link has118 V Morse Functions˜β−1˜β0˜β1regular 0 0 0minimum 1 0 0saddle 0 1 0maximum 0 0 1Table V.1: Classification of the vertices in a PL function on a 2-manifold.the reduced homology of the (p − 1)-sphere. In other words, the only non-zeroreduced Betti number of a simple PL critical vertex of index p is˜βp−1= 1.Definition. A piecewise linear function f : K → R on a manifold is a PLMorse function if (i) each vertex is either PL regular or simple PL critical and(ii) the function values of the vertices are distinct.Unfolding. In contrast to the smooth case, PL Morse functions are not denseamong the class of all PL functions. Equivalently, a PL function on a manifoldmay require a substantial perturbation before it becomes PL Morse. As anexample consider the piecewise linear version of a monkey saddle displayed inFigure V.10. It is therefore not reasonable to assume a PL Morse functionunfoldFigure V.10: Left: a PL monkey saddle of a height function. The areas of pointslower than the center vertex are shaded. Right: the unfolding of the PL monkeysaddle into two simple saddles.as input, but we can sometimes alter the triangulation locally to make it intoa PL Morse function. In the 2-manifold case, a k-fold saddle is defined by˜β0= k. We can split it into k simple saddles by introducing k − 1 new verticesand assigning appropriate function values close to that of the original, k-foldsaddle; see Figure V.10 for the case k = 2. It is less clear how to unfoldpossibly complicated PL critical points for higher-dimensional manifolds; seeSection IX.8.V.3 Piecewise Linear Functions 119Alternating sum of indices. Let K be a triangulation of a d-manifold andf : K → R a PL Morse function. It is not difficult to prove that the alternatingsum of the simple PL critical points gives the Euler characteristic,χ(K) =Xu(−1)index(u).Since it is easy and instructive, we give an inductive proof of this equation.To go from Ki−1to Ki, we add the lower star of ui. By the Euler-Poincar´eTheorem, the Euler characteristic of the lower link L = Lk−uiisχ(L) = 1 +Xp≥0(−1)p−1˜βp−1(L),which is 1 if uiis PL regular and 1 + (−1)index(ui)−1if uiis PL critical. Eachj-simplex in the lower star corresponds to a (j − 1)-simplex in the lower link,except for the vertex uiitself. Adding the lower star


View Full Document

Duke CPS 296.1 - Piecewise Linear Functions

Documents in this Course
Lecture

Lecture

18 pages

Lecture

Lecture

6 pages

Lecture

Lecture

13 pages

Lecture

Lecture

5 pages

Load more
Download Piecewise Linear Functions
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Piecewise Linear Functions and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Piecewise Linear Functions 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?