Counting Straight-Edge Tringulation of Planar Point Sets

Ray, Saurabh

Local TagsRelease HistoryDetailsSummary

Counting Straight-Edge Tringulation of Planar Point Sets

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

Item is Released

show all hide all

Basic

show hide

Item Permalink: https://hdl.handle.net/11858/00-001M-0000-0027-D757-D Version Permalink: https://hdl.handle.net/11858/00-001M-0000-0027-D758-B

Genre: Thesis

Files

show Files

Locators

show

Creators

show

hide

Creators:
Ray, Saurabh^{1, 2}, Author
Seidel, Raimund³, Advisor

Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019
2International Max Planck Research School, MPI for Informatics, Max Planck Society, Campus E1 4, 66123 Saarbrücken, DE, ou_1116551
3External Organizations, ou_persistent22

Content

show

hide

Free keywords: -

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.

Details

show

hide

Language(s): eng - English

Dates: Accepted: 2005-07Date issued: 2005

Publication Status: Issued

Pages: -

Publishing info: Saarbrücken : Universität des Saarlandes

Table of Contents: -

Rev. Type: -

Identifiers: BibTex Citekey: Saurabh

Degree: Master

Event

show

Legal Case

show

Project information

show

Source

show