Search for dissertations about: "greedy triangulation"

Found 2 swedish dissertations containing the words greedy triangulation.

2. 1. Progress in Hierarchical Clustering & Minimum Weight Triangulation

   Author : Drago Krznaric; Institutionen för datavetenskap; []
   Keywords : NATURVETENSKAP; NATURAL SCIENCES; computer technology; Systems engineering; minimum spanning tree; complete linkage; hierarchical clustering; minimum weight triangulation; greedy triangulation; Data- och systemvetenskap;

   Abstract : In this thesis we study efficient computational methods for geometrical problems of practical importance and theoretical interest. The problems that we consider are primarily complete linkage clustering, minimum spanning trees, and approximating minimum weight triangulation. Below is a list of the main results proved in the thesis. READ MORE

4. 2. New results about the approximation behavior of the greedy triangulation

   Author : Christos Levcopoulos; Linköpings universitet; []
   Keywords : NATURVETENSKAP; NATURAL SCIENCES;

   Abstract : In this paper it is shown that there is some constant c, such that for any polygon, with or without holes, with w concave vertices, the length of any greedy triangulation of the polygon is not longer than c x (w + 1) times the length of a minimum weight triangulation of the polygon (under the assumption that no three vertices lie on the same line). A low approximation constant is proved for interesting classes of polygons. READ MORE