Disjoint Empty Convex Pentagons in Planar Point Sets

Details Disjoint Empty Convex Pentagons in Planar Point Sets Disjoint Empty Convex Pentagons in Planar Point Sets

2011-08-19

arxiv.org/abs/1108.3895v1

Mathematics

Combinatorics

23 pages, 28 figures

Scientific paper

Harborth [{\it Elemente der Mathematik}, Vol. 33 (5), 116--118, 1978] proved that every set of 10 points in the plane, no three on a line, contains an empty convex pentagon. From this it follows that the number of disjoint empty convex pentagons in any set of $n$ points in the plane is least $\lfloor\frac{n}{10}\rfloor$. In this paper we prove that every set of 19 points in the plane, no three on a line, contains two disjoint empty convex pentagons. We also show that any set of $2m+9$ points in the plane, where $m$ is a positive integer, can be subdivided into three disjoint convex regions, two of which contains $m$ points each, and another contains a set of 9 points containing an empty convex pentagon. Combining these two results, we obtain non-trivial lower bounds on the number of disjoint empty convex pentagons in planar points sets. We show that the number of disjoint empty convex pentagons in any set of $n$ points in the plane, no three on a line, is at least $\lfloor\frac{5n}{47}\rfloor$. This bound has been further improved to $\frac{3n-1}{28}$ for infinitely many $n$.

Affiliated with

Also associated with

No associations

Rating

Disjoint Empty Convex Pentagons in 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 Disjoint Empty Convex Pentagons in Planar Point Sets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Disjoint Empty Convex Pentagons in Planar Point Sets will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-107918