On levels in arrangements of lines, segments, planes, and triangles

Pankaj K. Agarwal; Boris Aronov; Micha Sharir

On levels in arrangements of lines, segments, planes, and triangles

Pankaj K. Agarwal, Boris Aronov, Micha Sharir

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We consider the problem of bounding the complexity of the k-th level in an arrangement of n curves or surfaces, a problem dual to, and extending, the well-known k-set problem. (a) We review and simplify some old proofs in new disguise and give new proofs of the bound O(n√k+1) for the complexity of the k-th level in an arrangement of n lines. (b) We derive an improved version of Lovasz Lemma in any dimension, and use it to prove a new bound, O(n²k^2/3), on the complexity of the k-th level in an arrangement of n planes in R³, or on the number of k-sets in a set of n points in three dimensions. (c) We show that the complexity of any single level in an arrangement of n line segments in the plane is O(n^3/2), and that the complexity of any single level in an arrangement of n triangles in 3-space is O(n^17/6).

Original language	English (US)
Title of host publication	Proceedings of the Annual Symposium on Computational Geometry
Editors	Anon
Publisher	ACM
Pages	30-38
Number of pages	9
State	Published - 1997
Event	Proceedings of the 1997 13th Annual Symposium on Computational Geometry - Nice, Fr Duration: Jun 4 1997 → Jun 6 1997

Other

Other	Proceedings of the 1997 13th Annual Symposium on Computational Geometry
City	Nice, Fr
Period	6/4/97 → 6/6/97

ASJC Scopus subject areas

Chemical Health and Safety
Software
Safety, Risk, Reliability and Quality
Geometry and Topology

Cite this

@inproceedings{50072edf4c3c4422ab898199c8c84aa1,

title = "On levels in arrangements of lines, segments, planes, and triangles",

abstract = "We consider the problem of bounding the complexity of the k-th level in an arrangement of n curves or surfaces, a problem dual to, and extending, the well-known k-set problem. (a) We review and simplify some old proofs in new disguise and give new proofs of the bound O(n√k+1) for the complexity of the k-th level in an arrangement of n lines. (b) We derive an improved version of Lovasz Lemma in any dimension, and use it to prove a new bound, O(n2k2/3), on the complexity of the k-th level in an arrangement of n planes in R3, or on the number of k-sets in a set of n points in three dimensions. (c) We show that the complexity of any single level in an arrangement of n line segments in the plane is O(n3/2), and that the complexity of any single level in an arrangement of n triangles in 3-space is O(n17/6).",

author = "Agarwal, {Pankaj K.} and Boris Aronov and Micha Sharir",

year = "1997",

language = "English (US)",

pages = "30--38",

editor = "Anon",

booktitle = "Proceedings of the Annual Symposium on Computational Geometry",

publisher = "ACM",

note = "Proceedings of the 1997 13th Annual Symposium on Computational Geometry ; Conference date: 04-06-1997 Through 06-06-1997",

}

TY - GEN

T1 - On levels in arrangements of lines, segments, planes, and triangles

AU - Agarwal, Pankaj K.

AU - Aronov, Boris

AU - Sharir, Micha

PY - 1997

Y1 - 1997

N2 - We consider the problem of bounding the complexity of the k-th level in an arrangement of n curves or surfaces, a problem dual to, and extending, the well-known k-set problem. (a) We review and simplify some old proofs in new disguise and give new proofs of the bound O(n√k+1) for the complexity of the k-th level in an arrangement of n lines. (b) We derive an improved version of Lovasz Lemma in any dimension, and use it to prove a new bound, O(n2k2/3), on the complexity of the k-th level in an arrangement of n planes in R3, or on the number of k-sets in a set of n points in three dimensions. (c) We show that the complexity of any single level in an arrangement of n line segments in the plane is O(n3/2), and that the complexity of any single level in an arrangement of n triangles in 3-space is O(n17/6).

AB - We consider the problem of bounding the complexity of the k-th level in an arrangement of n curves or surfaces, a problem dual to, and extending, the well-known k-set problem. (a) We review and simplify some old proofs in new disguise and give new proofs of the bound O(n√k+1) for the complexity of the k-th level in an arrangement of n lines. (b) We derive an improved version of Lovasz Lemma in any dimension, and use it to prove a new bound, O(n2k2/3), on the complexity of the k-th level in an arrangement of n planes in R3, or on the number of k-sets in a set of n points in three dimensions. (c) We show that the complexity of any single level in an arrangement of n line segments in the plane is O(n3/2), and that the complexity of any single level in an arrangement of n triangles in 3-space is O(n17/6).

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

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

M3 - Conference contribution

AN - SCOPUS:0030697586

SP - 30

EP - 38

BT - Proceedings of the Annual Symposium on Computational Geometry

A2 - Anon, null

PB - ACM

T2 - Proceedings of the 1997 13th Annual Symposium on Computational Geometry

Y2 - 4 June 1997 through 6 June 1997

ER -

On levels in arrangements of lines, segments, planes, and triangles

Abstract

Other

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this