Lower bounds for weak epsilon-nets and stair-convexity
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F11%3A10100316" target="_blank" >RIV/00216208:11320/11:10100316 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1007/s11856-011-0029-1" target="_blank" >http://dx.doi.org/10.1007/s11856-011-0029-1</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/s11856-011-0029-1" target="_blank" >10.1007/s11856-011-0029-1</a>
Alternative languages
Result language
angličtina
Original language name
Lower bounds for weak epsilon-nets and stair-convexity
Original language description
A set N SUBSET OF ? d is called a weak ?-net (with respect to convex sets) for a finite X SUBSET OF ? d if N intersects every convex set C with |X INTERSECTION C| GREATER-THAN OR EQUAL TO ?|X|. For every fixed d GREATER-THAN OR EQUAL TO 2 and every r GREATER-THAN OR EQUAL TO 1 we construct sets X SUBSET OF ? d for which every weak 1/r -net has at least ?(r log dMINUS SIGN 1 r) points; this is the first superlinear lower bound for weak ?-nets in a fixed dimension. The construction is a stretched grid, and convexity in this grid can be analyzed using stair-convexity, a new variant of the usual notion of convexity. We also consider weak ?-nets for the diagonal of our stretched grid in ? d , d GREATER-THAN OR EQUAL TO 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 th
Czech name
—
Czech description
—
Classification
Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BA - General mathematics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/1M0545" target="_blank" >1M0545: Institute for Theoretical Computer Science</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)
Others
Publication year
2011
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Israel Journal of Mathematics
ISSN
0021-2172
e-ISSN
—
Volume of the periodical
182
Issue of the periodical within the volume
1
Country of publishing house
IL - THE STATE OF ISRAEL
Number of pages
30
Pages from-to
199-228
UT code for WoS article
000289109300009
EID of the result in the Scopus database
—