On The Properties Of Pseudo-triangulations

Triangulation and pseudo-triangulation are important issues in the field of computational geometry, they are of comprehensive application value. Researches on triangulations are nearly perfect while researches on pseudo-triangulations (put forward by Pocchiola and Vegter^[1.2]) are not perfect at present.The main purpose of this paper is to discuss the upper and lower bound of pseudo n-gon pointed pseudo-triangulations. As pseudo-triangulations' theory and methods can be used for the problems of robot arm motion planning, kinetic collision detection, computer graphics, surface reconstruction, finite element mesh generation, guarding and so on, so the improvement of the range of pointed pseudo-triangulations has some practical value.In literature Pseudo-Triangulations-a Survey(Contemporary Mathematics, Oct, 2007),Rote, Santos and Streinu point out the range of pointed pseudo-triangulations of pseudo n-gon is [2^n-3,h(n-l)] (h(n) is Catalan number), but it is a little distensible forgeneral pseudo n-gon. Some improvement about the upper and lower bound that given by Rote and others is done in this paper after discussing some properties of pseudo n-gon seriously.First, we divide the pointed pseudo-triangulations of pseudo n-gon into two parts, namely, basic triangulations(A(k)) and special triangulations(B) by means of the dual graph isomorphic relation between convex n-gon and pseudo n-gon. After introducing the concept of restricted diagonal (we use k as the number of restricted diagonals) of pseudo n-gon. We get basic triangulations of pseudo n-gon by using Inclusion-Exclusion Principle. After analyzing and summarizing the properties of special triangulations of pseudo n-gon, then finding the shape of pseudo n-gon that makes special triangulations get its max.Second, this paper points out conditions that the basic triangulations and the special triangulations of pseudo n-gon change with k, and then according to every k, we improve the upper and lower bound given by Rote and others by using basic triangulations and special triangulations. When 0≤k≤[n/2], the range of pointedpseudo-triangulations is [A(k), h(n-l)] (here A(k)>2^n-3 ); when [n/2]≤k≤(?) , the range of pointed pseudo-triangulations are[2^n-3,A(k)+(?)B(m)] (here A(k)+(?)B(m) is not more than 0.67 times of h(n -1), obviously it is better than h(n -1) as upper bound).