Finding Convex Sets Among Points in the Plane

Kleitman, D. and Pachter, L. (1998) Finding Convex Sets Among Points in the Plane. Discrete and Computational Geometry, 19 (3). pp. 405-410. ISSN 0179-5376. doi:10.1007/PL00009358. https://resolver.caltech.edu/CaltechAUTHORS:20170309-114305555

PDF - Published Version
See Usage Policy.
78kB

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20170309-114305555

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.

Item Type:

Article

Related URLs:

URL	URL Type	Description
https://dx.doi.org/10.1007/PL00009358	DOI	Article
https://link.springer.com/article/10.1007/PL00009358	Publisher	Article
http://rdcu.be/pXjg	Publisher	Free ReadCube access

ORCID:

Author	ORCID
Pachter, L.	0000-0002-9164-6231

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.

Issue or Number:

DOI:

10.1007/PL00009358

Record Number:

CaltechAUTHORS:20170309-114305555

Persistent URL:

https://resolver.caltech.edu/CaltechAUTHORS:20170309-114305555

Official Citation:

Kleitman, D. & Pachter, L. Discrete Comput Geom (1998) 19: 405. doi:10.1007/PL00009358

Usage Policy:

No commercial reproduction, distribution, display or performance rights in this work are provided.

ID Code:

74983

Collection:

CaltechAUTHORS

Deposited By:

George Porter

Deposited On:

10 Mar 2017 03:15

Last Modified:

15 Nov 2021 16:29

Repository Staff Only: item control page