# Item

ITEM ACTIONSEXPORT

Released

Thesis

#### Counting Straight-Edge Tringulation of Planar Point Sets

##### Fulltext (public)

There are no public fulltexts stored in PuRe

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Ray, S. (2005). Counting Straight-Edge Tringulation of Planar Point Sets. Master Thesis, Universität des Saarlandes, Saarbrücken.

Cite as: http://hdl.handle.net/11858/00-001M-0000-0027-D757-D

##### Abstract

A triangulation of a finite set S of points in R2 is a maximal set of line
segments with disjoint interiors whose end points are in S. A set of points in
the plane can have many triangulations and it is known that a set of n points
always has more than (2.33n)[7] and fewer than 59n-(log(n)) [4]
triangulation. However, these bounds are not tight. Also, counting the
number of triangulation of a given a set of points efficiently remains an open
problem. The fastest method so far is based on the so called t-path method [5]
and it was the first algorithm having a running time sublinear on the number of
triangulations counted. In this thesis, we consider a slightly different
approach to counting the number of triangulations. Although we are unable to
prove any non-trivial result about our algorithm yet, empirical results show
that the running time of our algorithm for a set of n points is o(nlog2nT(n))
where T(n) is the number of triangulations counted, and in practice it performs
much better than the earlier algorithm.