Simple Proofs of Classical Theorems in Discrete Geometry via the Guth-Katz Polynomial Partitioning Technique

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F12%3A10125727" target="_blank" >RIV/00216208:11320/12:10125727 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1007/s00454-012-9443-3" target="_blank" >http://dx.doi.org/10.1007/s00454-012-9443-3</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s00454-012-9443-3" target="_blank" >10.1007/s00454-012-9443-3</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Simple Proofs of Classical Theorems in Discrete Geometry via the Guth-Katz Polynomial Partitioning Technique

Popis výsledku v původním jazyce

Recently Guth and Katz (arXiv:1011.4105, 2010) invented, as a step in their nearly complete solution of ErdAs's distinct distances problem, a new method for partitioning finite point sets in R-d , based on the Stone-Tukey polynomial ham-sandwich theorem.We apply this method to obtain new and simple proofs of two well known results: the Szemer,di-Trotter theorem on incidences of points and lines, and the existence of spanning trees with low crossing numbers. Since we consider these proofs particularly suitable for teaching, we aim at self-contained, expository treatment. We also mention some generalizations and extensions, such as the Pach-Sharir bound on the number of incidences with algebraic curves of bounded degree.

Název v anglickém jazyce

Simple Proofs of Classical Theorems in Discrete Geometry via the Guth-Katz Polynomial Partitioning Technique

Popis výsledku anglicky

Recently Guth and Katz (arXiv:1011.4105, 2010) invented, as a step in their nearly complete solution of ErdAs's distinct distances problem, a new method for partitioning finite point sets in R-d , based on the Stone-Tukey polynomial ham-sandwich theorem.We apply this method to obtain new and simple proofs of two well known results: the Szemer,di-Trotter theorem on incidences of points and lines, and the existence of spanning trees with low crossing numbers. Since we consider these proofs particularly suitable for teaching, we aim at self-contained, expository treatment. We also mention some generalizations and extensions, such as the Pach-Sharir bound on the number of incidences with algebraic curves of bounded degree.

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)

Rok uplatnění

2012

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

48

Číslo periodika v rámci svazku

3

Stát vydavatele periodika

DE - Spolková republika Německo

Počet stran výsledku

19

Strana od-do

499-517

Kód UT WoS článku

000307507800001

EID výsledku v databázi Scopus

—