Towards a de Bruijn-Erdős Theorem in the L1-Metric

Kód výsledku v IS VaVaI

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

Výsledek na webu

<a href="http://www.researchgate.net/publication/257429129_Towards_a_de_BruijnErds_Theorem_in_the_L_1-Metric" target="_blank" >http://www.researchgate.net/publication/257429129_Towards_a_de_BruijnErds_Theorem_in_the_L_1-Metric</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s00454-013-9496-y" target="_blank" >10.1007/s00454-013-9496-y</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Towards a de Bruijn-Erdős Theorem in the L1-Metric

Popis výsledku v původním jazyce

A well-known theorem of de Bruijn and Erdos states that any set of n non-collinear points in the plane determines at least n lines. Chen and Chvatal asked whether an analogous statement holds within the framework of finite metric spaces, with lines defined using the notion of betweenness. In this paper, we prove that the answer is affirmative for sets of n points in the plane with the L1 metric, provided that no two points share their x- or y-coordinate. In this case, either there is a line that contains all n points, or X induces at least n distinct lines. If points of X are allowed to share their coordinates, then either there is a line that contains all n points, or X induces at least n/37 distinct lines.

Název v anglickém jazyce

Towards a de Bruijn-Erdős Theorem in the L1-Metric

Popis výsledku anglicky

A well-known theorem of de Bruijn and Erdos states that any set of n non-collinear points in the plane determines at least n lines. Chen and Chvatal asked whether an analogous statement holds within the framework of finite metric spaces, with lines defined using the notion of betweenness. In this paper, we prove that the answer is affirmative for sets of n points in the plane with the L1 metric, provided that no two points share their x- or y-coordinate. In this case, either there is a line that contains all n points, or X induces at least n distinct lines. If points of X are allowed to share their coordinates, then either there is a line that contains all n points, or X induces at least n/37 distinct lines.

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/GPP201%2F12%2FP288" target="_blank" >GPP201/12/P288: Reprezentace grafů</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 periodika

Discrete and Computational Geometry

ISSN

0179-5376

e-ISSN

—

Svazek periodika

49

Číslo periodika v rámci svazku

3

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

11

Strana od-do

659-670

Kód UT WoS článku

—

EID výsledku v databázi Scopus

—