Name
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 p n/12. As a consequence we show that such a set possesses a crossing family of size at least p n/12, and describe a fast algorithm for finding such a family. |
Year | DOI | Venue |
|---|---|---|
1991 | 10.1145/109648.109687 | Symposium on Computational Geometry 2013 |
Keywords | DocType | Volume |
line segments,combinatorial geometry | Conference | 14 |
Issue | ISSN | ISBN |
2 | 1439-6912 | 0-89791-426-0 |
Citations | PageRank | References |
5 | 0.93 | 3 |
Authors | ||
7 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Boris Aronov | 1 | 1430 | 149.20 |
| Paul Erdős | 2 | 264 | 42.20 |
| Wayne Goddard | 3 | 5 | 0.93 |
| Daniel J. Kleitman | 4 | 854 | 277.98 |
| Michael Klugerman | 5 | 73 | 7.52 |
| János Pach | 6 | 2366 | 292.28 |
| Leonard J. Schulman | 7 | 1328 | 136.88 |