The Research Of Foliations On Surfaces And Birkhoff Interpolation

Computational conformal geometry is a frontier interdiscipline which combines computer science and pure mathematics.It translates the concepts and theorems of modern geometry and classical geometry into computer algorithms in order to serve engineering practices.In return,computer algorithms not only help promote and spread the mathematics,but also draw the distance between mathematics and engi-neering applications closer.Holomorphic quadratic differential is an important concept in conformal geometry.It's the key to the study of Teichmiiller space and has direct connection with foliations on surfaces.The horizontal and vertical trajectories of a holomorphic quadratic differential are exactly the foliations on the surface.Because holomorphic quadratic differential is hard to understand,few people can feel its beau-tv and it's impossible to use it in the field of engineering.This paper for the first time proposes an algorithm to construct and visualize the foliations on the surface by using graph-valued harmonic map.The algorithm can also compute the holomorphic quadratic differential,because the graph-valued harmonic map can induce one.The algorithm takes loops on the surface and positive value parameters as input to control the topology and geometry of the output foliations and Strebel differential.This paper visualizes all kinds of foliations,and we can for the first time actually see the concept and be able to apply them in the engineering field.This paper proves the equiva-lent relation among three concept:colorable quad-mesh,finite measured foliation and Strebel differential which offers the rigorous theory foundation for the hexahedral mesh generation and proposes the automatically hexahedral meshing algorithm.This work also introduces a novel surface registration algorithm based on foliation theory which can handle surfaces with complicated topologies and large non-isometric deformations.In the end,this paper provides a criterion to determine whether an n-variable Birkhoff interpolation problem has unique minimal monomial basis,which means it owns the same minimal monomial basis w.r.t.arbitrary monomial order.Thus,for problems in this case,we can easily get the minimal monomial basis with little computation cost w.r.t.arbitrary monomial order by using our fast B-Lex algorithm.Foliations and Strebel differentials.The foliation can decompose the n di-mensional manifold into n-1 dimensional manifold,and it has local tensor product structure.Fig.3(a)shows the concept of foliation.Intuitively,a surface foliation de-composes the surface into a family of non-intersecting loops.Each loop is called a leaf,and three leaves meet at the singularities(red nodes on the red curves in Fig.3(a)).? 3 The foliation and Strebel differential on a genus 2 surface.We use graph-valued harmonic map to obtain the foliation on surfaces.We input a set of loops {?1,?2,?3}(orange curves in Fig.3(a)),and associate them with height parameters {h1,h2,h3}.These loops decompose the surface into two pants(genus 0 surface with three boundaries).Then we can define a graph,as shown in Fig.3(b),each pant corresponds a node,each loop corresponds an edge,the length of the edge is assigned with the height parameter;Suppose one loop connects two pants,then the arc of loop connects the nodes of the pants.Gromov and Schoen[20]defined the hyperbolic property of the graph,and proved the existence and uniqueness of the graph-valued harmonic map.We compute the graph-valued harmonic map by using non-linear heat flow to obtain the foliations on the surfaces.As shown in Fig.3,the preimage of the nodes of the graph in(b)are the red curves shown in(a);the preimages of points on the arc are the foliations.The leaves of the foliation on the surface could be infinite spirals or finite loops.The foliation consisted of finite loops is called finite measured foliation which is exactly what our algorithm outputs.The Hubbard-Masure theory[25]proved the equivalent.relation between foliation and holomorphic quadratic differential,for any foliation,like the one in Fig.3(a),there exists a holomorphic quadratic differential as shown in Fig.3(c)whose horizontal trajectories are exactly the given foliation.The holomorphic quadratic differential which can induce finite measured foliation is Strebel Differential.We use the Hodge star operator to obtain the Strebel differential from foliation.Hexahedral Mesh Generation.This work proves that the following three concepts are equivalent:{Colorable Quad-Mesh}(?){Finite Measured Foliation}(?){Strebel Differe.ntial}.which is called the trinity relation.as summarized in the main theorem:Theorem 0.0.2(Trinity)Suppose S is a closed Riemann surface with genus greater than one.Given.an colorable Q.there is a finite measured foliation(FQ,?Q)induced by Q,and there exits a unique Strebel different ?,such that the horizontal finite measured foliation.induced by ?,(F?,??)is equivalent to(FQ,?Q).Inversely,given a Strebel differential ?,it is associated with.a finite measured foliation(F?,??),and induces a colorable quadrilateral mesh Q.This theoretic framework allows us to use the Strebel differentials to construct colorable quad-meshes,then extend to hexahedral meshes of the interior.The Strebel differentials can be constructed by variational method directly.This gives us a practi-cal way to generate all possible colorable quad-meshes on a surface,and an automatic method for hexahedral mesh generation.The algorithm pipeline is as follows:the input surface is a genus g>1 closed surface,the enclosed volume is a handle body:1)the user inputs a set of disjoint,simple loops on a high genus surface,and specifies a height parameter for each loop;2)a unique Strebel differential is computed with the combi-natorial type and the heights prescribed by the user's input;3)the Strebel differential decomposes the surface into cylinders,and generates a colorable quadrilateral mesh of the surface;4)the surface cylindrical decomposition is extended inward to produce a solid cylindrical decomposition of the volume;5)each topological solid cylinder is liomeomorphically mapped onto a canonical solid cylinder;6)the hexahedral meshing is generated for each volumetric cylinder and then glued together to form a globally consistent hex-mesh.? 4 Registration of genus 4 surfaces.Surface registration via foliation.This work introduces a novel surface regis-tration method based on foliation.A foliation decomposes the surface into a family of closed loops,such that the decomposition has local tensor product structure.By pro-jecting each loop to a point,the surface is collapsed into a graph.Two homeomorphic surfaces with consistent foliations can be registered by first matching their foliation graphs,then matching the corresponding leaves.Fig.4 shows our registration algorithmic pipeline.Given two genus g surfaces,we automatically compute 3g-3 cutting loops on the surface,which divide each surface into 2g-2 pairs of pants(genus 0 surface with 3 boundaries),this process is called the pants decomposition.Then we construct the corresponding pants decomposition graph,where each node represents a pair of pants,each arc represents a cutting loop.The consistent pants decompositions induce the same graph.We assign the arc lengths of the graph,compute the harmonic map from each surface to the graph.The harmonic mappings produce consistent foliations.Each point on the graph corresponds to a unique leaf on the source foliation,and a leaf on the target foliation.This gives the correspondence between the leaves,fur-thermore,the correspondences between the singularities and the cylinders.As shown in Fig.4,the corresponding cylinders are rendered using the same color.By further adjusting the mapping between each pair of leaves,we can achieve a global diffeomor-phism between the surfaces.Birkhoff interpolation.This work provides a criterion to determine whether an n-variable Birkhoff interpolation problem has unique minimal monomial basis,which means it owns the same minimal monomial basis w.r.t.arbitrary monomial order.Thus,for problems in this case,we can easily get the minimal monomial basis with little computation cost w.r.t.arbitrary monomial order by using our fast B-Lex algorithm.