Abstract
For a setS ofn points in the plane and forK ⊆ {1, 2, ..., [1/2n]}, letf K (S) denote the number of subsets ofS with cardinalityk εK which can be cut offS by a straight line. We show that there is a positive constantc such thatf K (S)<cn (Σ k ε K k)1/2.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
N. Alon and E. Győri, The number of small semispaces of a finite set of points in the plane, J. Combin Theory Ser. A, to appear.
H. Edelsbrunner, Arrangements and Geometric Computation, forthcoming book.
H. Edelsbrunner and G. Stőckl, The number of extreme pairs of finite point-sets in Euclidean spaces, Institutes for Information Processing, Technical University of Graz, Austria, Report F142 (1984).
H. Edelsbrunner and E. Welzl, On the number of line separations of a finite set in the plane, J. Combin. Theory Ser. A 38 (1985) 15–29.
H. Edelsbrunner and E. Welzl, Constructing belts in two-dimensional arrangements with applications, SIAM J. Comput., to appear.
P. Erdős, L. Lovász, A. Simmons, and E. G. Straus, Dissection graphs of planar point sets, in A Survey of Combinatorical Theory (J. N. Strivastava et al., eds.), North Holland, Amsterdam, 1973.
J. E. Goodman and R. Pollack, On the combinatorial classification of nondegenerate configurations in the plane, J. Combin. Theory Ser. A 29 (1980) 220–235.
J. E. Goodman and R. Pollack, On the number ofk-subsets of a set ofn points in the plane, J. Combin. Theory Ser. A 36 (1984) 101–104.
G. Stőckl, Gesammelte und neue Ergebnisse über extremek-Mengen für ebene Punktmengen, Diplomarbeit, Institutes for Information Processing, Technical University of Graz (1984).
Author information
Authors and Affiliations
Additional information
This research was carried out during the author's stay at the University of Leiden, The Netherlands.
Rights and permissions
About this article
Cite this article
Welzl, E. More onk-sets of finite sets in the plane. Discrete Comput Geom 1, 95–100 (1986). https://doi.org/10.1007/BF02187686
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF02187686