English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Thesis

Counting Straight-Edge Tringulation of Planar Point Sets

MPS-Authors
/persons/resource/persons45269

Ray,  Saurabh
Algorithms and Complexity, MPI for Informatics, Max Planck Society;
International Max Planck Research School, MPI for Informatics, Max Planck Society;

External Ressource
No external resources are shared
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.