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

H. Edelsbrunner, E. Welzl, Journal of Combinatorial Theory Series A 38 (1985) 15–29.

Download
No fulltext has been uploaded. References only!

Journal Article | Published
Abstract
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-2
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. https://doi.org/10.1016/0097-3165(85)90017-2
Edelsbrunner, Herbert, and Emo Welzl. “On the Number of Line Separations of a Finite Set in the Plane.” Journal of Combinatorial Theory Series A 38, no. 1 (1985): 15–29. 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, pp. 15–29, 1985.
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.
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.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar