Finding Convex Sets Among Points in the Plane
| ISSN: |
1432-0444
|
|---|---|
| Source: |
Springer Online Journal Archives 1860-2000
|
| Topics: |
Computer Science
Mathematics
|
| Notes: |
Abstract. Let g(n) denote the least value such that any g(n) points in the plane in general position contain the vertices of a convex n -gon. In 1935, Erdős and Szekeres showed that g(n) exists, and they obtained the bounds $$2^{n-2}+1 \leq g(n) \leq {{2n-4} \choose {n-2}} +1. $$ Chung and Graham have recently improved the upper bound by 1; the first improvement since the original Erdős—Szekeres paper. We show that $$g(n) \leq {{2n-4} \choose {n-2}}+7-2n.$$ 〈lsiheader〉 〈onlinepub〉26 June, 1998 〈editor〉Editors-in-Chief: &lsilt;a href=../edboard.html#chiefs&lsigt;Jacob E. Goodman, Richard Pollack&lsilt;/a&lsigt; 〈pdfname〉19n3p405.pdf 〈pdfexist〉yes 〈htmlexist〉no 〈htmlfexist〉no 〈texexist〉yes 〈sectionname〉 〈/lsiheader〉
|
| Type of Medium: |
Electronic Resource
|
| URL: |