Complexity of the bisection method

作     者：Gutierrez, Claudio Gutierrez, Flavio Rivara, Maria-Cecilia 

作者机构：Univ Chile Dept Comp Sci Santiago Chile Univ Valparaiso Valparaiso Chile 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 (Theor Comput Sci)

年 卷 期：2007年第382卷第2期

页      面：131-138页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Proyecto Fondecyt  (1040713) 

主　　题：bisection method longest edge bisection triangulation 

摘      要：The bisection method is the consecutive bisection of a triangle by the median of the longest side. In this paper we prove a subexponential asymptotic upper bound for the number of similarity classes of triangles generated on a mesh obtained by iterative bisection. which previously was known only to be finite. The relevant parameter is gamma/sigma, where gamma is the biggest and a is the smallest angle of the triangle. We get this result by introducing a taxonomy of triangles that precisely captures the behaviour of the bisection method. We also prove that the number of directions on the plane given by the sides of the triangles generated is finite. Additionally, we give purely geometrical and intuitive proofs of classical results for the bisection method. (c) 2007 Elsevier B.V. All rights reserved.