Polynomial Bounds on the Slicing Number

Details Polynomial Bounds on the Slicing Number Polynomial Bounds on the Slicing Number

2010-04-20

arxiv.org/abs/1004.3381v4

Computer Science

Computational Geometry

Withdrawn, because we found out that most of the results were already known (under a different name). See updated abstract for

Scientific paper

NOTE: Unfortunately, most of the results mentioned here were already known under the name of "d-separated interval piercing". The result that T_d(m) exists was first proved by Gya\'rfa\'s and Lehel in 1970, see [5]. Later, the result was strengthened by Ka\'rolyi and Tardos [9] to match our result. Moreover, their proof (in a different notation, of course) uses ideas very similar to ours and leads to a similar recurrence. Also, our conjecture turns out to be right and was proved for the 2-dimensional case by Tardos and for the general case by Kaiser [8]. An excellent survey article ("Transversals of d-intervals') is available on http://www.renyi.hu/~tardos. Still, we leave this paper available to the public on http://page.mi.fu-berlin.de/dawerner, also because one might find the references useful. ----- We study the following Gallai-type of problem: Assume that we are given a family X of convex objects in R^d such that among any subset of size m, there is an axis-parallel hyperplane intersecting at least two of the objects. What can we say about the number of axis-parallel hyperplanes that sufficient to intersect all sets in the family? In this paper, we show that this number T_d(m) exists, i.e., depends only on m and the dimension d, but not on the size of the set X. First, we derive a very weak super-exponential bound. Using this result, by a simple proof we are able to show that this number is even polynomially bounded for any fixed d. We partly answer open problem 74 on http://maven.smith.edu/~orourke/TOPP/, where the planar case is considered, by improving the best known exponential bound to O(m^2).

Affiliated with

Also associated with

No associations

Rating

Polynomial Bounds on the Slicing Number 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 Polynomial Bounds on the Slicing Number, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Polynomial Bounds on the Slicing Number will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-472335