Sökning: "minimum weight triangulation"

Hittade 5 avhandlingar innehållade orden minimum weight triangulation.

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

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

    Sammanfattning : 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. LÄS MER

  3. 2. Fixed-Parameter Algorithms for Optimal Convex Partitions and Other Results

    Författare :Magdalene Grantson Borgelt; Data Vetenskap; []
    Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; control; Datalogi; numerical analysis; Convex Partition; Computer science; Triangulation; kontroll; system; numerisk analys; systems; Fixed-Parameter Algorithm; Spanning Tree;

    Sammanfattning : In this thesis I study two-dimensional geometric optimization problems for which it is difficult to find efficient, exact, deterministic algorithms. All known solutions to these problems require time that is exponential in the total size of the input. LÄS MER

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

    Författare :Christos Levcopoulos; Linköpings universitet; []
    Nyckelord :NATURVETENSKAP; NATURAL SCIENCES;

    Sammanfattning : 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. LÄS MER

  5. 4. Fixed parameter algorithms and other results for convex patitions

    Författare :Magdalene Grantson Borgelt; Data Vetenskap; []
    Nyckelord :NATURVETENSKAP; NATURAL SCIENCES;

    Sammanfattning : It is known that the minimum edge length convex partition MWCP of polygons with holes (an example of a PSLG) is NP-hard. Partitioning polygons with holes into the minimum number of convex polygons MNCP is also known to be NP-hard. LÄS MER

  7. 5. Approximation Algorithms for Geometric Networks

    Författare :Mattias Andersson; Data Vetenskap; []
    Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; NATURVETENSKAP; NATURAL SCIENCES; control; systems; numerical analysis; Computer science; Geometric Networks; Computational Geometry; Approximation Algorithms; Datalogi; numerisk analys; system; kontroll; Systems engineering; computer technology; Data- och systemvetenskap;

    Sammanfattning : The main contribution of this thesis is approximation algorithms for several computational geometry problems. The underlying structure for most of the problems studied is a geometric network. LÄS MER