Disjoint empty convex polygons in planar point sets
Author(s) -
Attila Guly�s,
L�zl� Szab�
Publication year - 2001
Publication title -
elemente der mathematik
Language(s) - English
Resource type - Journals
eISSN - 1420-8962
pISSN - 0013-6018
DOI - 10.1007/s000170050089
Subject(s) - disjoint sets , regular polygon , combinatorics , planar , mathematics , point (geometry) , geometry , computer science , computer graphics (images)
Recently, the study of convex polygons has gained a renewed interest because of their importance in computer graphics, geometric learning theory, and artificial intelligence, for instance. Surprisingly, many simple questions are unanswered in this field. Let us start with a beautiful example. We say that a set of points in the plane is in general position if no three of the points lie on a line. Decades ago, Erdős, Klein, and Szekeres posed the problem of determining the maximum number f(k) of points in general position in the plane so that no k points form the vertex set of a convex polygon. Erdős and Szekeres [3] proved that
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom