Let fd(n), n > d ≥ 2, be the smallest positive integer such that any set of fd(n) points, in general position in Rd , contains n points in convex position. Let hd(n, k), n > d ≥ 2 and k ≥ 0, denote the smallest number with the property that in any set of hd(n, k) points, in general position in Rd , there are n points in convex position whose convex hull contains at most k other points. Previous result of Valtr states that h4(n, 0) does not exist for all n ≥ 249. We show that h4(n, 0) does not exist for all n ≥ 137. We show that h3(8, k) ≤ f3(8) for all k ≥ 26, h4(10, k) ≤ f4(10) for all k ≥ 147 and h5(12, k) ≤ f5(12) for all k ≥ 999. Next, let fd(k, n) be the smallest number such that in every set of fd(k, n) points, in general position in Rd , there are n points whose convex hull has at least k vertices. We show that, for arbitrary integers n ≥ k ≥ d + 1, d ≥ 2, fd(k, n) ≥ (n − 1) (k − 1)/(cd logd−2 (n − 1)) , where cd > 0 is a constant dependent only on the dimension d. 1
| Identifer | oai:union.ndltd.org:nusl.cz/oai:invenio.nusl.cz:313203 |
| Date | January 2011 |
| Creators | Zajíc, Vítězslav |
| Contributors | Valtr, Pavel, Cibulka, Josef |
| Source Sets | Czech ETDs |
| Language | English |
| Detected Language | English |
| Type | info:eu-repo/semantics/masterThesis |
| Rights | info:eu-repo/semantics/restrictedAccess |
Page generated in 0.0018 seconds