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

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 | United States |

City | North Conway |

Period | 6/10/91 → 6/12/91 |

### ASJC Scopus subject areas

- Theoretical Computer Science
- Geometry and Topology
- Computational Mathematics

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

## Cite this

Aronov, B., Erdos, P., Goddard, W., Kleitman, D. J., Klugerman, M., Pach, J., & Schulman, L. J. (1991). Crossing families. In

*Proceedings of the Annual Symposium on Computational Geometry*(pp. 351-356). (Proceedings of the Annual Symposium on Computational Geometry). Association for Computing Machinery. https://doi.org/10.1145/109648.109687