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 setsA andB of points in the plane are mutually avoiding if no line subtended by a pair of points inA intersects the convex hull ofB, and vice versa. We show that any set ofn points in general position contains a pair of mutually avoiding subsets each of size at least
<img src="/fulltext-image.asp?format=htmlnonpaginated&src=H134H2P7H854067T_html\493_2005_Article_BF01215345_TeX2GIFIE1.gif" border="0" alt="
$$\sqrt {n/12} $$
" />. As a consequence we show that such a set possesses a crossing family of size at least
<img src="/fulltext-image.asp?format=htmlnonpaginated&src=H134H2P7H854067T_html\493_2005_Article_BF01215345_TeX2GIFIE2.gif" border="0" alt="
$$\sqrt {n/12} $$
" />, and describe a fast algorithm for finding such a family. |
Year | DOI | Venue |
|---|---|---|
1994 | 10.1007/BF01215345 | Combinatorica |
Keywords | DocType | Volume |
52 C 10, 68 Q 20 | Journal | 14 |
Issue | ISSN | Citations |
2 | 1439-6912 | 5 |
PageRank | References | Authors |
0.79 | 3 | 7 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Boris Aronov | 1 | 1430 | 149.20 |
| Paul Erdös | 2 | 191 | 42.33 |
| Wayne Goddard | 3 | 5 | 0.79 |
| 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 |