---
_id: '4113'
abstract:
- lang: eng
  text: 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.
article_processing_charge: No
article_type: original
author:
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
- first_name: Emo
  full_name: Welzl, Emo
  last_name: Welzl
citation:
  ama: Edelsbrunner H, Welzl E. On the number of line separations of a finite set
    in the plane. <i>Journal of Combinatorial Theory Series A</i>. 1985;38(1):15-29.
    doi:<a href="https://doi.org/10.1016/0097-3165(85)90017-2">10.1016/0097-3165(85)90017-2</a>
  apa: Edelsbrunner, H., &#38; Welzl, E. (1985). On the number of line separations
    of a finite set in the plane. <i>Journal of Combinatorial Theory Series A</i>.
    Elsevier. <a href="https://doi.org/10.1016/0097-3165(85)90017-2">https://doi.org/10.1016/0097-3165(85)90017-2</a>
  chicago: Edelsbrunner, Herbert, and Emo Welzl. “On the Number of Line Separations
    of a Finite Set in the Plane.” <i>Journal of Combinatorial Theory Series A</i>.
    Elsevier, 1985. <a href="https://doi.org/10.1016/0097-3165(85)90017-2">https://doi.org/10.1016/0097-3165(85)90017-2</a>.
  ieee: H. Edelsbrunner and E. Welzl, “On the number of line separations of a finite
    set in the plane,” <i>Journal of Combinatorial Theory Series A</i>, vol. 38, no.
    1. Elsevier, pp. 15–29, 1985.
  ista: 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.
  mla: Edelsbrunner, Herbert, and Emo Welzl. “On the Number of Line Separations of
    a Finite Set in the Plane.” <i>Journal of Combinatorial Theory Series A</i>, vol.
    38, no. 1, Elsevier, 1985, pp. 15–29, doi:<a href="https://doi.org/10.1016/0097-3165(85)90017-2">10.1016/0097-3165(85)90017-2</a>.
  short: H. Edelsbrunner, E. Welzl, Journal of Combinatorial Theory Series A 38 (1985)
    15–29.
date_created: 2018-12-11T12:07:01Z
date_published: 1985-01-01T00:00:00Z
date_updated: 2022-01-31T14:14:25Z
day: '01'
doi: 10.1016/0097-3165(85)90017-2
extern: '1'
intvolume: '        38'
issue: '1'
language:
- iso: eng
month: '01'
oa_version: None
page: 15 - 29
publication: Journal of Combinatorial Theory Series A
publication_identifier:
  eissn:
  - 1096-0899
  issn:
  - 0097-3165
publication_status: published
publisher: Elsevier
publist_id: '2011'
quality_controlled: '1'
scopus_import: '1'
status: public
title: On the number of line separations of a finite set in the plane
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 38
year: '1985'
...