Research On Some Problem On Computational Geometry

Computational geometry is a vital sub-domain in the theoretical computer science domain, its research result has already gotten an extensive application in the computer graphics, the chemistry, the statistics, the pattern recognition, the geographic database and other many domains. How to provide valid algorithms and theories for various application, have been the direction that the domestic and international scholar study. This article discusses some basic problems on computational geometry as following:The first, this article proves the theory of "each polygon has three convex vertex at least", which expands the theory of "each polygon has a convex vertex at least".The second, this article pretreat the planar point set by deleting points gradually, which make the improved algorithm avoid the problem that extremity vertices being , and reduce points efficiently.The third, this article discusses the relation between the number of triangulation and diagonal basing on "Euler-Segner problem" It analyzing the number of triangulation when a polygon such as pentagon ,hexagon and heptagon reduce some diagonal, then put forward the concept "sub-upper limit" of the number of a polygon triangulation , and gives the calculation formula of "sub-upper limit".