TY - GEN

T1 - Crossing families

AU - Aronov, Boris

AU - Erdos, Paul

AU - Goddard, Wayne

AU - Kleitman, Daniel J.

AU - Klugerman, Michael

AU - Pach, János

AU - Schulman, Leonard J.

N1 - Funding Information:
1Department 2Mathematicat 3 Department Technology 4 Courant Institute, New York University 5Research supported in part by DARPA grant NOOO14-s9. .J. 1988, Air Force grant AFOSl%89-0271, NSF grant DMS-8606225, and an ONR graduate fellowship. Further, part of this work was conducted at and supported by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and – NSF-STC88-09648.
Publisher Copyright:
© 1991 ACM.

PY - 1991/6/1

Y1 - 1991/6/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0347623435&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0347623435&partnerID=8YFLogxK

U2 - 10.1145/109648.109687

DO - 10.1145/109648.109687

M3 - Conference contribution

AN - SCOPUS:0347623435

SN - 0897914260

T3 - Proceedings of the Annual Symposium on Computational Geometry

SP - 351

EP - 356

BT - Proceedings of the Annual Symposium on Computational Geometry

PB - Association for Computing Machinery

T2 - 7th Annual Symposium on Computational Geometry, SCG 1991

Y2 - 10 June 1991 through 12 June 1991

ER -