The Szemerédi–Trotter theorem is a mathematical result in the field of Discrete geometry. It asserts that given n points and m lines in the Euclidean plane, the number of incidences (i.e., the number of point-line pairs, such that the point lies on the line) is This bound cannot be improved, except in terms of the implicit constants. An equivalent formulation of the theorem is the following. Given n points and an integer k ≥ 2, the number of lines which pass through at least k of the points is
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - Satz von Szemerédi und Trotter (de)
- Théorème de Szemerédi-Trotter (fr)
- Szemerédi–Trotter theorem (en)
- Теорема Семереди — Троттера (ru)
- Теорема Семереді — Троттера (uk)
- 塞邁雷迪－特羅特定理 (zh)
|
| rdfs:comment
| - In der Mathematik ist der Satz von Szemerédi und Trotter ein 1983 von Endre Szemerédi und William T. Trotter bewiesener Lehrsatz der diskreten Geometrie. (de)
- Le théorème de Szemerédi-Trotter est un résultat de géométrie combinatoire, dû à Endre Szemerédi et William T. Trotter, qui donne la majoration asymptotique (optimale) suivante : pour n points et m droites du plan, le nombre d' (en) (c'est-à-dire le nombre de couples (point, droite) tels que le point appartient à la droite) est ou, de manière équivalente, pour n points et un entier k ≥ 2, le nombre de droites passant par au moins k de ces n points est Ce théorème a de nombreux corollaires, dont le théorème de Beck en (en). (fr)
- 塞邁雷迪－特羅特定理為組合幾何的定理，其斷言給定歐氏平面上任意個點和條直線，至多發生 次重合（incidence，即二元組，其中為一點，為直線，且在上）。 此上界已經是最優的上界了，唯一的改進只可能出現在大O符號中隱藏的常數倍數。 考慮隱藏常數的話，、拉多什·拉多伊契奇（Radoš Radoičić）、、四人給出上界。此後，由於交叉數不等式的常數得到改進，塞邁雷迪－特羅特定理的常數也相應得到改進。截至2019年末，最優的常數是。 另一方面，保奇和托特證明，若將上式的常數換成，則不再為重合數的上界。 定理也有以下等價形式：若給定個點和整數，則經過至少個點的直線數至多為 定理得名自塞邁雷迪·安德烈和，其最先的證明較複雜，用到稱為「胞分解」（cell decomposition）的組合技巧。其後，塞凱利·拉茲洛（Székely László）利用圖的交叉數不等式，給出更簡單的證明， 詳見下文。 塞邁雷迪－特羅特定理可推導出若干其他定理，例如重合幾何的和的。 (zh)
- The Szemerédi–Trotter theorem is a mathematical result in the field of Discrete geometry. It asserts that given n points and m lines in the Euclidean plane, the number of incidences (i.e., the number of point-line pairs, such that the point lies on the line) is This bound cannot be improved, except in terms of the implicit constants. An equivalent formulation of the theorem is the following. Given n points and an integer k ≥ 2, the number of lines which pass through at least k of the points is (en)
- Теорема Семереди — Троттера — результат комбинаторной геометрии.Теорема утверждает, что если даны n точек и m прямых на плоскости, число инциденций (т.е. число пар точка/прямая, в которых точка лежит на прямой) равно и эта граница не может быть улучшена. Эквивалентная формулировка теоремы следующая. Если задано n точек и целое число k > 2, число прямых, проходящих по меньшей мере через k точек, равно Теорема Семереди – Троттера имеет несколько следствий, включая в геометрии инцидентности. (ru)
- Теорема Семереді — Троттера — результат комбінаторної геометрії. Теорема стверджує, що якщо дано n точок та m прямих на площині, кількість інциденцій (тобто, кількість пар точка/пряма, в яких точка лежить на прямій) дорівнює і цю межу неможливо покращити. Еквівалентне формулювання теореми таке. Якщо дано n точок та ціле число k > 2, число прямих, що проходять принпаймні через k точок, дорівнює Теорема Семереді — Троттера має кілька наслідків, серед яких в геометрії інцидентності. (uk)
|
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| has abstract
| - In der Mathematik ist der Satz von Szemerédi und Trotter ein 1983 von Endre Szemerédi und William T. Trotter bewiesener Lehrsatz der diskreten Geometrie. (de)
- Le théorème de Szemerédi-Trotter est un résultat de géométrie combinatoire, dû à Endre Szemerédi et William T. Trotter, qui donne la majoration asymptotique (optimale) suivante : pour n points et m droites du plan, le nombre d' (en) (c'est-à-dire le nombre de couples (point, droite) tels que le point appartient à la droite) est ou, de manière équivalente, pour n points et un entier k ≥ 2, le nombre de droites passant par au moins k de ces n points est Ce théorème a de nombreux corollaires, dont le théorème de Beck en (en). (fr)
- The Szemerédi–Trotter theorem is a mathematical result in the field of Discrete geometry. It asserts that given n points and m lines in the Euclidean plane, the number of incidences (i.e., the number of point-line pairs, such that the point lies on the line) is This bound cannot be improved, except in terms of the implicit constants. As for the implicit constants, it was shown by János Pach, Radoš Radoičić, Gábor Tardos, and Géza Tóth that the upper bound holds. Since then better constants are known due to better crossing lemma constants; the current best is 2.44. On the other hand, Pach and Tóth showed that the statement does not hold true if one replaces the coefficient 2.5 with 0.42. An equivalent formulation of the theorem is the following. Given n points and an integer k ≥ 2, the number of lines which pass through at least k of the points is The original proof of Endre Szemerédi and William T. Trotter was somewhat complicated, using a combinatorial technique known as . Later, László Székely discovered a much simpler proof using the crossing number inequality for graphs. (See below.) The Szemerédi–Trotter theorem has a number of consequences, including Beck's theorem in incidence geometry and the Erdős-Szemerédi sum-product problem in additive combinatorics. (en)
- Теорема Семереди — Троттера — результат комбинаторной геометрии.Теорема утверждает, что если даны n точек и m прямых на плоскости, число инциденций (т.е. число пар точка/прямая, в которых точка лежит на прямой) равно и эта граница не может быть улучшена. Эквивалентная формулировка теоремы следующая. Если задано n точек и целое число k > 2, число прямых, проходящих по меньшей мере через k точек, равно Первоначальное доказательство Семереди и было сложным и использовало комбинаторную технику, известную как разделение ячеек. Позднее Секей обнаружил существенно более простое доказательство, использующее неравенство числа пересечений для графов (см. ниже). Теорема Семереди – Троттера имеет несколько следствий, включая в геометрии инцидентности. (ru)
- Теорема Семереді — Троттера — результат комбінаторної геометрії. Теорема стверджує, що якщо дано n точок та m прямих на площині, кількість інциденцій (тобто, кількість пар точка/пряма, в яких точка лежить на прямій) дорівнює і цю межу неможливо покращити. Еквівалентне формулювання теореми таке. Якщо дано n точок та ціле число k > 2, число прямих, що проходять принпаймні через k точок, дорівнює Початкове доведення Семереді та було складним і спиралось на комбінаторну техніку, відому як поділ комірок. Пізніше Секей виявив значно простіше доведення, що використовує нерівність числа схрещень для графів (див. нижче). Теорема Семереді — Троттера має кілька наслідків, серед яких в геометрії інцидентності. (uk)
- 塞邁雷迪－特羅特定理為組合幾何的定理，其斷言給定歐氏平面上任意個點和條直線，至多發生 次重合（incidence，即二元組，其中為一點，為直線，且在上）。 此上界已經是最優的上界了，唯一的改進只可能出現在大O符號中隱藏的常數倍數。 考慮隱藏常數的話，、拉多什·拉多伊契奇（Radoš Radoičić）、、四人給出上界。此後，由於交叉數不等式的常數得到改進，塞邁雷迪－特羅特定理的常數也相應得到改進。截至2019年末，最優的常數是。 另一方面，保奇和托特證明，若將上式的常數換成，則不再為重合數的上界。 定理也有以下等價形式：若給定個點和整數，則經過至少個點的直線數至多為 定理得名自塞邁雷迪·安德烈和，其最先的證明較複雜，用到稱為「胞分解」（cell decomposition）的組合技巧。其後，塞凱利·拉茲洛（Székely László）利用圖的交叉數不等式，給出更簡單的證明， 詳見下文。 塞邁雷迪－特羅特定理可推導出若干其他定理，例如重合幾何的和的。 (zh)
|
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)