Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published March 1998 | Published
Journal Article Open

Finding Convex Sets Among Points in the Plane

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 ≤ g(n) ≤ (^(2n−4)_(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) ≤ (^(2n−4)_(n−2)) + 7 − 2n.

Additional Information

© 1998 Springer-Verlag. Received January 1, 1997, and in revised form June 6, 1997. We thank Géza Tóth and Pavel Valtr for contributing the lower bound construction. We also thank the referee for numerous helpful suggestions and comments.

Attached Files

Published - art_3A10.1007_2FPL00009358.pdf

Files

art_3A10.1007_2FPL00009358.pdf
Files (78.2 kB)
Name Size Download all
md5:7e3acb126116d8ee999688ba87c835b6
78.2 kB Preview Download

Additional details

Created:
August 19, 2023
Modified:
October 25, 2023