Counting Triangulations of Planar Point Sets

Details Counting Triangulations of Planar Point Sets Counting Triangulations of Planar Point Sets

2009-11-17

arxiv.org/abs/0911.3352v2

Computer Science

Discrete Mathematics

Scientific paper

We study the maximal number of triangulations that a planar set of $n$ points can have, and show that it is at most $30^n$. This new bound is achieved by a careful optimization of the charging scheme of Sharir and Welzl (2006), which has led to the previous best upper bound of $43^n$ for the problem. Moreover, this new bound is useful for bounding the number of other types of planar (i.e., crossing-free) straight-line graphs on a given point set. Specifically, we derive new upper bounds for the number of planar graphs ($o(239.4^n)$), spanning cycles ($O(70.21^n)$), and spanning trees ($160^n$).

Affiliated with

Also associated with

No associations

Rating

Counting Triangulations of Planar Point Sets does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Counting Triangulations of Planar Point Sets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Counting Triangulations of Planar Point Sets will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-650974