Computer Science – Computational Geometry
Scientific paper
2010-12-02
Computer Science
Computational Geometry
13 pages, 2 figures
Scientific paper
Motivated by an open problem from graph drawing, we study several partitioning problems for line and hyperplane arrangements. We prove a ham-sandwich cut theorem: given two sets of n lines in R^2, there is a line l such that in both line sets, for both halfplanes delimited by l, there are n^{1/2} lines which pairwise intersect in that halfplane, and this bound is tight; a centerpoint theorem: for any set of n lines there is a point such that for any halfplane containing that point there are (n/3)^{1/2} of the lines which pairwise intersect in that halfplane. We generalize those results in higher dimension and obtain a center transversal theorem, a same-type lemma, and a positive portion Erdos-Szekeres theorem for hyperplane arrangements. This is done by formulating a generalization of the center transversal theorem which applies to set functions that are much more general than measures. Back to Graph Drawing (and in the plane), we completely solve the open problem that motivated our search: there is no set of n labelled lines that are universal for all n-vertex labelled planar graphs. As a side note, we prove that every set of n (unlabelled) lines is universal for all n-vertex (unlabelled) planar graphs.
Dujmovic Vida
Langerman Stefan
No associations
LandOfFree
A Center Transversal Theorem for Hyperplanes and Applications to Graph Drawing does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A Center Transversal Theorem for Hyperplanes and Applications to Graph Drawing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Center Transversal Theorem for Hyperplanes and Applications to Graph Drawing will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-604825