Crossing families

B. Aronov; P. Erdos; W. Goddard; D. J. Kleitman; M. Klugerman; J. Pach; L. J. Schulman

doi:10.1007/BF01215345

Crossing families

B. Aronov, P. Erdos, W. Goddard, D. J. Kleitman, M. Klugerman, J. Pach, L. J. Schulman

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

Abstract

Given a set of points in the plane, a crossing family is a collection of line segments, each joining two of the points, such that any two line segments intersect internally. Two sets A and B of points in the plane are mutually avoiding if no line subtended by a pair of points in A intersects the convex hull of B, and vice versa. We show that any set of n points in general position contains a pair of mutually avoiding subsets each of size at least {Mathematical expression}. As a consequence we show that such a set possesses a crossing family of size at least {Mathematical expression}, and describe a fast algorithm for finding such a family.

Original language	English (US)
Pages (from-to)	127-134
Number of pages	8
Journal	Combinatorica
Volume	14
Issue number	2
DOIs	https://doi.org/10.1007/BF01215345
State	Published - Jun 1994

Keywords

AMS subject classification code (1991): 52C10, 68Q20

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Computational Mathematics

Access to Document

10.1007/BF01215345

Fingerprint Dive into the research topics of 'Crossing families'. Together they form a unique fingerprint.

Cite this

@article{8487ae11e50e41b2a333c89d6ae200f5,

title = "Crossing families",

abstract = "Given a set of points in the plane, a crossing family is a collection of line segments, each joining two of the points, such that any two line segments intersect internally. Two sets A and B of points in the plane are mutually avoiding if no line subtended by a pair of points in A intersects the convex hull of B, and vice versa. We show that any set of n points in general position contains a pair of mutually avoiding subsets each of size at least {Mathematical expression}. As a consequence we show that such a set possesses a crossing family of size at least {Mathematical expression}, and describe a fast algorithm for finding such a family.",

keywords = "AMS subject classification code (1991): 52C10, 68Q20",

author = "B. Aronov and P. Erdos and W. Goddard and Kleitman, {D. J.} and M. Klugerman and J. Pach and Schulman, {L. J.}",

year = "1994",

month = jun,

doi = "10.1007/BF01215345",

language = "English (US)",

volume = "14",

pages = "127--134",

journal = "Combinatorica",

issn = "0209-9683",

publisher = "Janos Bolyai Mathematical Society",

number = "2",

}

TY - JOUR

T1 - Crossing families

AU - Aronov, B.

AU - Erdos, P.

AU - Goddard, W.

AU - Kleitman, D. J.

AU - Klugerman, M.

AU - Pach, J.

AU - Schulman, L. J.

PY - 1994/6

Y1 - 1994/6

N2 - Given a set of points in the plane, a crossing family is a collection of line segments, each joining two of the points, such that any two line segments intersect internally. Two sets A and B of points in the plane are mutually avoiding if no line subtended by a pair of points in A intersects the convex hull of B, and vice versa. We show that any set of n points in general position contains a pair of mutually avoiding subsets each of size at least {Mathematical expression}. As a consequence we show that such a set possesses a crossing family of size at least {Mathematical expression}, and describe a fast algorithm for finding such a family.

AB - Given a set of points in the plane, a crossing family is a collection of line segments, each joining two of the points, such that any two line segments intersect internally. Two sets A and B of points in the plane are mutually avoiding if no line subtended by a pair of points in A intersects the convex hull of B, and vice versa. We show that any set of n points in general position contains a pair of mutually avoiding subsets each of size at least {Mathematical expression}. As a consequence we show that such a set possesses a crossing family of size at least {Mathematical expression}, and describe a fast algorithm for finding such a family.

KW - AMS subject classification code (1991): 52C10, 68Q20

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

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

U2 - 10.1007/BF01215345

DO - 10.1007/BF01215345

M3 - Article

AN - SCOPUS:0003501716

VL - 14

SP - 127

EP - 134

JO - Combinatorica

JF - Combinatorica

SN - 0209-9683

IS - 2

ER -