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

McCabe, Paul

Local TagsRelease HistoryDetailsSummary

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 Released

show all hide all

Basic

show hide

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

Genre: Thesis

Files

show Files

Locators

show

Creators

show

hide

Creators:
McCabe, Paul^{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: 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.

Details

show

hide

Language(s): eng - English

Dates: Accepted: 2003Date issued: 2003

Publication Status: Issued

Pages: -

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

Table of Contents: -

Rev. Type: -

Identifiers: BibTex Citekey: McCabe2003

Degree: Master

Event

show

Legal Case

show

Project information

show

Source

show