# On the number of line separations of a finite set in the plane

Edelsbrunner H, Welzl E. 1985. On the number of line separations of a finite set in the plane. Journal of Combinatorial Theory Series A. 38(1), 15–29.

Download

**No fulltext has been uploaded. References only!**

*Journal Article*|

*Published*

Author

Edelsbrunner, Herbert

^{IST Austria}^{}; Welzl, EmoAbstract

Let S denote a set of n points in the Euclidean plane. A subset S′ of S is termed a k-set of S if it contains k points and there exists a straight line which has no point of S on it and separates S′ from S−S′. We let fk(n) denote the maximum number of k-sets which can be realized by a set of n points. This paper studies the asymptotic behaviour of fk(n) as this function has applications to a number of problems in computational geometry. A lower and an upper bound on fk(n) is established. Both are nontrivial and improve bounds known before. In particular, is shown by exhibiting special point-sets which realize that many k-sets. In addition, is proved by the study of a combinatorial problem which is of interest in its own right.

Publishing Year

Date Published

1985-01-01

Journal Title

Journal of Combinatorial Theory Series A

Volume

38

Issue

1

Page

15 - 29

IST-REx-ID

### Cite this

Edelsbrunner H, Welzl E. On the number of line separations of a finite set in the plane.

*Journal of Combinatorial Theory Series A*. 1985;38(1):15-29. doi:10.1016/0097-3165(85)90017-2Edelsbrunner, H., & Welzl, E. (1985). On the number of line separations of a finite set in the plane.

*Journal of Combinatorial Theory Series A*. Elsevier. https://doi.org/10.1016/0097-3165(85)90017-2Edelsbrunner, Herbert, and Emo Welzl. “On the Number of Line Separations of a Finite Set in the Plane.”

*Journal of Combinatorial Theory Series A*. Elsevier, 1985. https://doi.org/10.1016/0097-3165(85)90017-2.H. Edelsbrunner and E. Welzl, “On the number of line separations of a finite set in the plane,”

*Journal of Combinatorial Theory Series A*, vol. 38, no. 1. Elsevier, pp. 15–29, 1985.Edelsbrunner, Herbert, and Emo Welzl. “On the Number of Line Separations of a Finite Set in the Plane.”

*Journal of Combinatorial Theory Series A*, vol. 38, no. 1, Elsevier, 1985, pp. 15–29, doi:10.1016/0097-3165(85)90017-2.