Abstract
Let r(n) denote the largest integer such that every family \(\mathcal{C}\) of n pairwise disjoint segments in the plane in general position has r(n) members whose order type can be represented by points. Pach and Tóth gave a construction that shows r(n) < n log8/log9 (Pach and Tóth 2009). They also stated that one can apply the Erdős–Szekeres theorem for convex sets in Pach and Tóth (Discrete Comput Geom 19:437–445, 1998) to obtain r(n) > log16 n. In this note, we will show that r(n) > cn 1/4 for some absolute constant c.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Alon, A., Kalai, G.: Bounding the piercing number. Discrete Comput. Geom. 13, 245–256 (1995)
Bisztriczky, T., Fejes Tóth, G.: A generalization of the Erdős–Szekeres convex n-gon theorem. J. Reine Angew. Math. 395, 167–170 (1989)
Bisztriczky, T., Fejes Tóth, G.: Convexly independent sets. Combinatorica 10, 195–202 (1990)
Eckhoff, J.: Helly, Radon, and Carathéodory type theorems. In: Gruber, P.M., Wills, J.M. (eds.) Handbook of Convex Geometry, pp. 389–448. North-Holland, Amsterdam (1993)
Erdős, P., Szekeres, G.: A combinatorial problem in geometry. Compos. Math. 2, 463–470 (1935)
Goodman, J. E., Pollack, R.: Multidimensional sorting. SIAM J. Comput. 12, 484–507 (1983)
Helly, E.: Über Mengen konvexer Körper mit gemeinschaftlichen Punkten. Jber. Deutsch. Math. Verein. 32, 175–176 (1923)
Katchalski, M., Liu, A.: A problem of geometry in R n. Proc. Am. Math. Soc. 75, 284–288 (1979)
Matousek, J.: Lectures on Discrete Geometry. Springer, New York (2002)
Pach, J., Tóth, G.: A generalization of the Erdős–Szekeres theorem to disjoint convex sets. Discrete Comput. Geom. 19, 437–445 (1998)
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)
Spencer, J.: Turán’s theorem for k-graphs. Discrete Math. 2, 183–186 (1972)
Wenger, R.: Progress in geometric transversal theory. In: Chazelle, B., Goodman, J.E., Pollack, R. (eds.) Advances in Discrete and Computational Geometry, Contemp. Math., vol. 223, pp. 375–393. Amer. Math. Soc., Providence (1999)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Suk, A. On Order Types of Systems of Segments in the Plane. Order 27, 63–68 (2010). https://doi.org/10.1007/s11083-010-9138-4
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11083-010-9138-4