Lower bounds for weak epsilon-nets and stair-convexity

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Lower bounds for weak epsilon-nets and stair-convexity

Popis výsledku v původním jazyce

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

Název v anglickém jazyce

Lower bounds for weak epsilon-nets and stair-convexity

Popis výsledku anglicky

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

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

<a href="/cs/project/1M0545" target="_blank" >1M0545: Institut Teoretické Informatiky</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2011

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Israel Journal of Mathematics

ISSN

0021-2172

e-ISSN

—

Svazek periodika

182

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

IL - Stát Izrael

Počet stran výsledku

30

Strana od-do

199-228

Kód UT WoS článku

000289109300009

EID výsledku v databázi Scopus

—