Abstract
We study arrangements of intervals in \(\mathbb {R}^2\) for which many pairs form trapezoids. We show that any set of intervals forming many trapezoids must have underlying algebraic structure, which we characterise. This leads to some unexpected examples of sets of intervals forming many trapezoids, where an important role is played by degree 2 curves.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Chazelle, B., Edelsbrunner, H.: An optimal algorithm for intersecting line segments in the plane. J. Assoc. Comput. Mach. 39(1), 1–54 (1992)
Guth, L., Katz, N.H.: On the Erdős distinct distances problem in the plane. Ann. Math. 181(1), 155–190 (2015)
Josefsson, M.: Characterizations of orthodiagonal quadrilaterals. Forum Geom. 12, 13–25 (2012)
Pach, J., Sharir, M.: On vertical visibility in arrangements of segments and the queue size in the Bentley–Ottmann line swee** algorithm. SIAM J. Comput. 20(3), 460–470 (1991)
Pach, J., Sharir, M.: Combinatorial Geometry and Its Algorithmic Applications. The Alcalá Lectures. Mathematical Surveys and Monographs, vol. 152. American Mathematical Society, Providence (2009)
Tóth, Cs.D.: Binary space partitions for line segments with a limited number of directions. SIAM J. Comput. 32(2), 307–325 (2003)
Wiernik, A., Sharir, M.: Planar realizations of nonlinear Davenport–Schinzel sequences by segments. Discrete Comput. Geom. 3(1), 15–47 (1988)
Acknowledgements
We’d like to thank the anonymous referees for improving the presentation of our results. The research of the first author was supported in part by a Four Year Doctoral Fellowship from the University of British Columbia. Research of the second author was supported in part by an NSERC Discovery grant, OTKA K 119528 and NKFI KKP 133819 grants. The research of the third author was supported in part by Killam and NSERC doctoral scholarships.
Author information
Authors and Affiliations
Corresponding author
Additional information
Editor in Charge: János Pach
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Di Benedetto, D., Solymosi, J. & White, E.P. Combinatorics of Intervals in the Plane I: Trapezoids. Discrete Comput Geom 69, 232–249 (2023). https://doi.org/10.1007/s00454-022-00456-y
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-022-00456-y