Lower Bounding the Number of Straight-Edge Triangulations of Planar Point Sets

McCabe, Paul

Lokale TagsFreigabegeschichteDetailsÜbersicht

Lower Bounding the Number of Straight-Edge Triangulations of Planar Point Sets

McCabe, P. (2003). Lower Bounding the Number of Straight-Edge Triangulations of Planar Point Sets. Master Thesis, Universität des Saarlandes, Saarbrücken.

Item is Freigegeben

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:

Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-0027-F823-4 Versions-Permalink: https://hdl.handle.net/11858/00-001M-0000-0027-F824-2

Genre: Hochschulschrift

ausblenden:

Urheber:
McCabe, Paul^{1, 2}, Autor
Seidel, Raimund³, Ratgeber

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

Inhalt

einblenden:

ausblenden:

Schlagwörter: -

Zusammenfassung: We examine the number of triangulations that any set of n points in the plane must have, and prove that (i) any set of n points has at least 0.00037*2.2n triangulations, (ii) any set with three extreme points and n interior points has at least 0.112*2.569n triangulation, and (iii) any set with n interior points has at least 0.238 * 2.38n triangulation. The best previously known lower bound for the number of triangulations for n points in the plane is 0.0822 * 2.0129n. We also give a method of automatically extending known bounds for small point sets to general lower bounds.