Finding Convex Sets Among Points in the Plane

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>

Authors and Affiliations

1. Department of Mathematics, MIT, Cambridge, MA 02139, USA \{djk,lpachter\}@math.mit.edu, , , , , , US

   D. Kleitman & L. Pachter

Received January 1, 1997, and in revised form June 6, 1997.

Reprints and permissions