TY - JOUR

T1 - Lower bounds for weak epsilon-nets and stair-convexity

AU - Bukh, Boris

AU - Matoušek, J.

AU - Nivasch, Gabriel

N1 - Funding Information:
pp. 1–10. ∗∗Work was carried out while the author was at Princeton University and at the Rényi Institute. Work was partially supported by the project Phenomena in High Dimensions. † Work was done while the author was at Tel Aviv University. Work was supported by Israel Science Foundation Grant 155/05 and by the Hermann Minkowski– MINERVA Center for Geometry at Tel Aviv University. Received February 18, 2009 and in revised form September 28, 2009

PY - 2011/3

Y1 - 2011/3

N2 - A set N ⊂Rd is called a weake{open}-net (with respect to convex sets) for a finite X ⊂ Rd if N intersects every convex set C with {divides}X ∩ C{divides} ≥ e{open}{divides}X{divides}. For every fixed d ≥ 2 and every r ≥ 1 we construct sets X ⊂ Rd for which every weak 1/r -net has at least Ω(r logd-1r) points; this is the first superlinear lower bound for weak e{open}-nets in a fixed dimension. The construction is a stretched grid, i. e., the Cartesian product of d suitable fast-growing finite sequences, and convexity in this grid can be analyzed using stair-convexity, a new variant of the usual notion of convexity. We also consider weak e{open}-nets for the diagonal of our stretched grid in Rd, d ≥ 3, which is an "intrinsically 1-dimensional" point set. In this case we exhibit slightly superlinear lower bounds (involving the inverse Ackermann function), showing that the upper bounds by Alon, Kaplan, Nivasch, Sharir and Smorodinsky (2008) are not far from the truth in the worst case. Using the stretched grid we also improve the known upper bound for the so-called second selection lemma in the plane by a logarithmic factor: We obtain a set T of t triangles with vertices in an n-point set in the plane such that no point is contained in more than O(t2/(n3 logn3/t)) triangles of T.

AB - A set N ⊂Rd is called a weake{open}-net (with respect to convex sets) for a finite X ⊂ Rd if N intersects every convex set C with {divides}X ∩ C{divides} ≥ e{open}{divides}X{divides}. For every fixed d ≥ 2 and every r ≥ 1 we construct sets X ⊂ Rd for which every weak 1/r -net has at least Ω(r logd-1r) points; this is the first superlinear lower bound for weak e{open}-nets in a fixed dimension. The construction is a stretched grid, i. e., the Cartesian product of d suitable fast-growing finite sequences, and convexity in this grid can be analyzed using stair-convexity, a new variant of the usual notion of convexity. We also consider weak e{open}-nets for the diagonal of our stretched grid in Rd, d ≥ 3, which is an "intrinsically 1-dimensional" point set. In this case we exhibit slightly superlinear lower bounds (involving the inverse Ackermann function), showing that the upper bounds by Alon, Kaplan, Nivasch, Sharir and Smorodinsky (2008) are not far from the truth in the worst case. Using the stretched grid we also improve the known upper bound for the so-called second selection lemma in the plane by a logarithmic factor: We obtain a set T of t triangles with vertices in an n-point set in the plane such that no point is contained in more than O(t2/(n3 logn3/t)) triangles of T.

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

U2 - 10.1007/s11856-011-0029-1

DO - 10.1007/s11856-011-0029-1

M3 - ???researchoutput.researchoutputtypes.contributiontojournal.article???

AN - SCOPUS:79953668239

SN - 0021-2172

VL - 182

SP - 199

EP - 228

JO - Israel Journal of Mathematics

JF - Israel Journal of Mathematics

IS - 1

ER -