On Mutually Avoiding Sets

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F13%3A10192375" target="_blank" >RIV/00216208:11320/13:10192375 - isvavai.cz</a>

Výsledek na webu

<a href="http://link.springer.com/chapter/10.1007/978-1-4614-7258-2_36/fulltext.html" target="_blank" >http://link.springer.com/chapter/10.1007/978-1-4614-7258-2_36/fulltext.html</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-1-4614-7258-2_36" target="_blank" >10.1007/978-1-4614-7258-2_36</a>

Jazyk výsledku

angličtina

Název v původním jazyce

On Mutually Avoiding Sets

Popis výsledku v původním jazyce

Two finite sets of points in the plane are called mutually avoiding if any straight line passing through two points of any one of these two sets does not intersect the convex hull of the other set. For any integer n, we construct a set of n points in general position in the plane which contains no pair of mutually avoiding sets of size more than O(SQUARE ROOTn) each. The given bound is tight up to a constant factor, since Aronov et al. showed a polynomial-time algorithm for finding two mutually avoidingsets of size ?(SQUARE ROOTn) each in any set of n points in general position in the plane.

Název v anglickém jazyce

On Mutually Avoiding Sets

Popis výsledku anglicky

Two finite sets of points in the plane are called mutually avoiding if any straight line passing through two points of any one of these two sets does not intersect the convex hull of the other set. For any integer n, we construct a set of n points in general position in the plane which contains no pair of mutually avoiding sets of size more than O(SQUARE ROOTn) each. The given bound is tight up to a constant factor, since Aronov et al. showed a polynomial-time algorithm for finding two mutually avoidingsets of size ?(SQUARE ROOTn) each in any set of n points in general position in the plane.

Druh

C - Kapitola v odborné knize

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

<a href="/cs/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Centrum excelence - Institut teoretické informatiky (CE-ITI)</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2013

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 knihy nebo sborníku

The Mathematics of Paul Erdős I

ISBN

978-1-4614-7257-5

Počet stran výsledku

8

Strana od-do

533-540

Počet stran knihy

564

Název nakladatele

Springer

Místo vydání

New York

Kód UT WoS kapitoly

—