ISSN:
1439-6912
Keywords:
52 C 10
;
68 Q 20
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
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 $$\sqrt {n/12} $$ . As a consequence we show that such a set possesses a crossing family of size at least $$\sqrt {n/12} $$ , and describe a fast algorithm for finding such a family.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01215345
Permalink
