Crossing families

Boris Aronov; Paul Erdos; Wayne Goddard; Daniel J. Kleitman; Michael Klugerman; János Pach; Leonard J. Schulman

doi:10.1145/109648.109687

Crossing families

Boris Aronov, Paul Erdos, Wayne Goddard, Daniel J. Kleitman, Michael Klugerman, János Pach, Leonard J. Schulman

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Given n points in the plane, a crossing family is a collection of line segments, each joining two of the points, suck that any two line segments intersect internally. We show that any n points in general position possess a crossing family of size at least √n/12, and describe an O(n logn)-time algorithm for finding one.

Original language	English (US)
Title of host publication	Proceedings of the Annual Symposium on Computational Geometry
Publisher	Association for Computing Machinery
Pages	351-356
Number of pages	6
ISBN (Print)	0897914260
DOIs	https://doi.org/10.1145/109648.109687
State	Published - Jun 1 1991
Event	7th Annual Symposium on Computational Geometry, SCG 1991 - North Conway, United States Duration: Jun 10 1991 → Jun 12 1991

Publication series

Name	Proceedings of the Annual Symposium on Computational Geometry

Other

Other	7th Annual Symposium on Computational Geometry, SCG 1991
Country/Territory	United States
City	North Conway
Period	6/10/91 → 6/12/91

ASJC Scopus subject areas

Theoretical Computer Science
Geometry and Topology
Computational Mathematics

Access to Document

10.1145/109648.109687

Cite this

Aronov, B, Erdos, P, Goddard, W, Kleitman, DJ, Klugerman, M, Pach, J & Schulman, LJ 1991, Crossing families. in Proceedings of the Annual Symposium on Computational Geometry. Proceedings of the Annual Symposium on Computational Geometry, Association for Computing Machinery, pp. 351-356, 7th Annual Symposium on Computational Geometry, SCG 1991, North Conway, United States, 6/10/91. https://doi.org/10.1145/109648.109687

@inproceedings{d85b370033a04af58686b59720bec7d5,

title = "Crossing families",

abstract = "Given n points in the plane, a crossing family is a collection of line segments, each joining two of the points, suck that any two line segments intersect internally. We show that any n points in general position possess a crossing family of size at least √n/12, and describe an O(n logn)-time algorithm for finding one.",

author = "Boris Aronov and Paul Erdos and Wayne Goddard and Kleitman, {Daniel J.} and Michael Klugerman and J{\'a}nos Pach and Schulman, {Leonard J.}",

note = "Publisher Copyright: {\textcopyright} 1991 ACM.; 7th Annual Symposium on Computational Geometry, SCG 1991 ; Conference date: 10-06-1991 Through 12-06-1991",

year = "1991",

month = jun,

day = "1",

doi = "10.1145/109648.109687",

language = "English (US)",

isbn = "0897914260",

series = "Proceedings of the Annual Symposium on Computational Geometry",

publisher = "Association for Computing Machinery",

pages = "351--356",

booktitle = "Proceedings of the Annual Symposium on Computational Geometry",

}

TY - GEN

T1 - Crossing families

AU - Aronov, Boris

AU - Erdos, Paul

AU - Goddard, Wayne

AU - Kleitman, Daniel J.

AU - Klugerman, Michael

AU - Pach, János

AU - Schulman, Leonard J.

PY - 1991/6/1

Y1 - 1991/6/1

N2 - Given n points in the plane, a crossing family is a collection of line segments, each joining two of the points, suck that any two line segments intersect internally. We show that any n points in general position possess a crossing family of size at least √n/12, and describe an O(n logn)-time algorithm for finding one.

AB - Given n points in the plane, a crossing family is a collection of line segments, each joining two of the points, suck that any two line segments intersect internally. We show that any n points in general position possess a crossing family of size at least √n/12, and describe an O(n logn)-time algorithm for finding one.

UR - http://www.scopus.com/inward/record.url?scp=0347623435&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0347623435&partnerID=8YFLogxK

U2 - 10.1145/109648.109687

DO - 10.1145/109648.109687

M3 - Conference contribution

AN - SCOPUS:0347623435

SN - 0897914260

T3 - Proceedings of the Annual Symposium on Computational Geometry

SP - 351

EP - 356

BT - Proceedings of the Annual Symposium on Computational Geometry

PB - Association for Computing Machinery

T2 - 7th Annual Symposium on Computational Geometry, SCG 1991

Y2 - 10 June 1991 through 12 June 1991

ER -

Crossing families

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this