Tight bounds on a problem of lines and intersections

Micha Sharir; Steven S. Skiena

doi:10.1016/0012-365X(91)90124-K

Tight bounds on a problem of lines and intersections

Micha Sharir
, Steven S. Skiena

Computer Science

Stony Brook University

New York University
Tel Aviv University

Research output: Contribution to journal › Article › peer-review

Abstract

Consider all arrangements of lines in the plane with r distinct slopes. What is the smallest number of lines f(r) in which there are at least f(r) + 1 points, each defined by the intersection of r lines? We improve the previous lower bound, showing f(r) = Θ(r³).

Original language	English
Pages (from-to)	313-314
Number of pages	2
Journal	Discrete Mathematics
Volume	89
Issue number	3
DOIs	https://doi.org/10.1016/0012-365X(91)90124-K
State	Published - Jun 1 1991

Access to Document

10.1016/0012-365X(91)90124-K

Cite this

@article{ca2d7b0c2e15485cb6e544019a714a59,

title = "Tight bounds on a problem of lines and intersections",

abstract = "Consider all arrangements of lines in the plane with r distinct slopes. What is the smallest number of lines f(r) in which there are at least f(r) + 1 points, each defined by the intersection of r lines? We improve the previous lower bound, showing f(r) = Θ(r3).",

author = "Micha Sharir and Skiena, \{Steven S.\}",

year = "1991",

month = jun,

day = "1",

doi = "10.1016/0012-365X(91)90124-K",

language = "English",

volume = "89",

pages = "313--314",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "3",

}

TY - JOUR

T1 - Tight bounds on a problem of lines and intersections

AU - Sharir, Micha

AU - Skiena, Steven S.

PY - 1991/6/1

Y1 - 1991/6/1

N2 - Consider all arrangements of lines in the plane with r distinct slopes. What is the smallest number of lines f(r) in which there are at least f(r) + 1 points, each defined by the intersection of r lines? We improve the previous lower bound, showing f(r) = Θ(r3).

AB - Consider all arrangements of lines in the plane with r distinct slopes. What is the smallest number of lines f(r) in which there are at least f(r) + 1 points, each defined by the intersection of r lines? We improve the previous lower bound, showing f(r) = Θ(r3).

UR - https://www.scopus.com/pages/publications/44949279238

U2 - 10.1016/0012-365X(91)90124-K

DO - 10.1016/0012-365X(91)90124-K

M3 - Article

SN - 0012-365X

VL - 89

SP - 313

EP - 314

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 3

ER -

Tight bounds on a problem of lines and intersections

Abstract

Access to Document

Other files and links

Fingerprint

Cite this