Abstract
We prove a Hadwiger transversal-type result, characterizing convex position on a family of non-crossing convex bodies in the plane. This theorem suggests a definition for the order type of a family of convex bodies, generalizing the usual definition of order type for point sets. This order type turns out to be an oriented matroid. We also give new upper bounds on the Erdős–Szekeres theorem in the context of convex bodies.
Similar content being viewed by others
References
Bisztriczky, T., Fejes, T.G.: A generalization of the Erdős–Szekeres convex n-gon theorem. J. Reine Angew. Math. 395, 167–170 (1989)
Bjorner, A., Sturmfels, B., Las Vergnas, M., White, N., Ziegler, G.: Oriented Matroids. Cambridge University Press, Cambridge (1993)
Ekchoff, J.A.: Gallai-type transversal problem in the plane. Discrete Comput. Geom. 9, 203–214 (1993)
Erdős, P., Szekeres, G.: A combinatorial problem in geometry. Compos. Math. 2, 464–470 (1935)
Grunbaum, B.: In: Kaibel, V., Klee, V., Ziegler, G.M. (eds.) Convex Polytopes, 2nd edn. Springer, New York (2003). ISBN 0-387-00424-6
Matusek, J.: Lectures on Discrete Geometry. Springer, New York (2002)
Mnev, N.E.: The universality theorems on the classification problem of configuration varieties and convex polytopes varieties (pp. 527–543). In: Viro, O.Y. (ed.) Topology and Geometry: Rohlin Seminar. Lecture Notes in Mathematics, p. 1346. Springer, Berlin (1988)
Pach, J., Tóth, G.: A generalization of the Erdős–Szekeres theorems to disjoint convex sets. Discrete Comput. Geom. 19, 437–445 (1998)
Pach, J., Tóth, G.: Erdős–Szekeres type theorems for segments and non-crossing convex sets. Geom. Dedic. 81, 1–12 (2000)
Pach, J., Tóth, G.: Families of Convex Sets not Representable by Points Indian Statistical Institute Platinum Jubilee Commemorative Volume—Architecture and Algorithms, pp. 43–53. World Scientific, Singapore (2009)
Suk, A.: On the order type of system of segments in the plane. Order 27, 63–68 (2010)
Toth, G., Valtr, P.: A note on the Erdős–Szekeres theorem. Discrtete Comp. Geom. 19, 457–459 (1998)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Hubard, A., Montejano, L., Mora, E. et al. Order Types of Convex Bodies. Order 28, 121–130 (2011). https://doi.org/10.1007/s11083-010-9156-2
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11083-010-9156-2