Abstract
An extreme triple or 3-set of a finite setS in the plane is a subset ofS of size 3 of the formS∩h, for some half-planeh. We establish an upper bound [11n/6]+1 for the number of extreme triples of anyS with |S|=n≥10. This almost matches the known lower bound [11n/6].
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
H. Edelsbrunner,Algorithms in Combinatorial Geometry, Springer-Verlag, Heidelberg, 1987.
H. Edelsbrunner and G. Stöckl, The number of extreme pairs of finite point-sets in Euclidean spaces,J. Combin. Theory Ser. A 43 (1986), 344–349.
J. E. Goodman, Proof of a conjecture of Burr, Grünbaum, and Sloane,Discrete Math. 32 (1980), 27–35.
J. E. Goodman and R. Pollack, Allowable sequences and order types in discrete and computational geometry, inNew Trends in Discrete and Computational Geometry, J. Pach, ed., pp. 103–134, Springer-Verlag, New York, 1993.
J. Snoeyink and J. Hershberger, Sweeping arrangements of curves, inDiscrete and Computational Geometry: Papers from the DIMACS Special Year, J. E. Goodman, R. Pollack, and W. Steiger, eds., pp. 309–349, AMS, Providence, RI, and ACM, New York, 1991.
G. Stöckl, Gesammelte und neue Ergebnisse über extremek-Mengen für ebene Punktmengen, Diplomarbeit, Institutes for Information Processing, Technical University of Graz, Graz, 1984.
Author information
Authors and Affiliations
Additional information
This research was supported by the National Science Foundation under Grant CCR-9118874.
Rights and permissions
About this article
Cite this article
Ramos, E.A. The number of extreme triples of a planar point set. Discrete Comput Geom 16, 1–19 (1996). https://doi.org/10.1007/BF02711130
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02711130