## 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 | |

State | Published - Jun 1994 |

## Keywords

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

## ASJC Scopus subject areas

- Discrete Mathematics and Combinatorics
- Computational Mathematics