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. Elsevier. 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. 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 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