Участник:МетаСкептик12/Черновик: различия между версиями

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Интерактивная навигация по истории
← Предыдущая правкаСледующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
Нет описания правки
Нет описания правки
Строка 1: Строка 1:
*Пусть <math>\{(X_i,Y_i)\}, i=1,2...n </math> последовательность координат соседних друг другу вершин <math>n</math>-угольника без самопересечений . Тогда его площадь вычисляется по формуле:
[[Image:Happy-End-problem.svg|thumb|300px|Задача со счастливым концом: любое множество из пяти точек содержит вершины выпуклого четырехугольника.]]
: <math> S = \frac{1}{2}|\sum\limits_{i=1}^n (X_i+X_{i+1})(Y_i+Y_{i+1})|</math>, где (<math>X_{n+1},Y_{n+1})=(X_1,Y_1)</math>.
'''Задача со счастливым концом''' (названная так [[Эрдёш, Пол|Полем Эрдёшем]], поскольку её решение завершилось свадьбой [[George Szekeres|Дьёрдя Секереша]] и [[Esther Klein|Эстер Клейн]]) формулируется следующим образом:
*В самом общем случае площадь многоугольника вычисляется как сумма площадей треугольников, на которые он разбивается не пересекающимися [[Диагональ|диагоналями]].

:'''Теорема.''' Любое множество из пяти точек на плоскости [[general position|в общем положении]]<ref>В данном контексте общее положение означает, что никакие две точки не совпадают и никакие три точки не лежат на одной прямой.</ref> имеет подмножество из четырех точек, которые являются вершинами [[Выпуклый многоугольник|выпуклого ]] [[Четырехугольник|четырехугольника]].

Теорема со счастливым концом доказывается простым анализом. Если не менее четырех точек образуют [[Выпуклая оболочка|выпуклую оболочку]], в качестве выпуклого четырехугольника можно выбрать любой набор из четырех точек оболочки. В противном случае мы имеем треугольник и две точки внутри него. Прямая, проходящая через две внутренние точки, в силу общего положения точек не пересекает одну из сторон треугольника. Вершины этой стороны и две внутренние точки образуют выпуклый четырехугольник.

==Многоугольники с произвольным числом вершин==
Эрдёш и Секереш обобщили этот результат на произвольное число точек, что является оригинальным развитием [[Теория Рамсея|теории Рамсея]]. Они также выдвинули '''гипотезу Эрдёша-Секереша''' - точную формулу для максимального числа вершин выпуклого многоугольника обязательно существующего в множестве из N точек в общем положении.

[[Image:8-points-no-pentagon.svg|thumb|Восемь точек в общем положении для которых нет выпуклого пятиугольника.]]
В {{harv|Erdős|Szekeres|1935}} доказано следующее обобщение:

:'''Теорема.''' Для любого натурального ''N'', всякое достаточно большое множество точек в общем положении на плоскости имеет подмножество ''N'' точек, которые являются вершинами выпуклого многоугольника.
Это доказательство появилось в той же статье, где доказывается [[Теорема Эрдёша — Секереша|теорема Эрдёша — Секереша]] о монотонных подпоследовательностях в числовых последовательностях.

== Размер множества как функция числа вершин многоугольника ==
Пусть ''f''(''N'') означает минимальное ''M'' для которого любое множество any из ''M'' точек в общем положении содержит выпуклый ''N''-угольник. Известно что
* ''f''(3) = 3, очевидно.
* ''f''(4) = 5.<ref> То, что доказала Эстер Клейн.</ref>
* ''f''(5) = 9. Согласно {{harv|Erdős|Szekeres|1935}}, это первым доказал Э. Макаи; первое опубликованное доказательство появилось в {{harv|Kalbfleisch|Kalbfleisch|Stanton|1970}}. Множество из восьми точек не содержащее выпуклый пятиугольник на иллюстрации показывает, чтоt ''f''(5) > 8; сложнее доказать, что любое множество из девяти точек в общем положении содержит выпуклый многоугольник.
* ''f''(6) = 17.Это было доказано в {{harv|Szekeres|Peters|2006}}. В работе реализован сокращенный компьютерный перебор возможных конфигураций из 17 точек.
* Значения ''f''(''N'') неизвестны для ''N'' > 6.

== Гипотеза Эрдёша-Секереша о числе выпуклых многоугольников ==
Исходя из известных значений ''f''(''N'') для ''N'' = 3, 4 и 5, Эрдёш и Секереш предположили, что
:<math> f(N) = 1 + 2^{N-2} </math> для всех <math> N </math>

Эта гипотеза не доказана, но известны оценки сверху и снизу.

== Оценки скорости роста <math> f(N) </math> ==
Конструктивным построением авторы гипотезы сумели позднее доказать оценку снизу, совпадающую с гипотетическим равенством.
:<math>f(N) \geq 1 + 2^{N-2},</math>{{harv|Erdős|Szekeres|1961}}

Однако наилучшая известная оценка сверху при ''N'' ≥ 7 не является близкой.
:<math>f(N) \leq {2N-5 \choose N-2} + 1 = O\left(\frac{4^N}{\sqrt N}\right).</math> {{harv|Tóth|Valtr|2005}}. Смотри [[биномиальные коэффициенты]] и [[«O» большое и «o» малое]] относительно обозначений и [[Формула Стирлинга|формулу Стирлинга]] для вывода асимптотики.

==Пустые многоугольники==
Интересен также вопрос о том, содержит ли достаточно большое множество точек в общем положении ''пустой'' выпуклый четырехугольник, [[пятиугольник]], и так далее. То есть многоугольник не содержащий внутренних точек.

Если внутри четырехугольника, существующего согласно теореме со счастливым концом, есть точка, то, соединив эту точку с двумя вершинами [[Диагональ|диагонали]] мы получим два четырехугольника один из которых выпуклый и пустой. Таким образом, пять точек в общем положении содержат пустой выпуклый четырехугольник, как видно на иллюстрации. Любые десять точек в общем положении содержит пустой выпуклый пятиугольник {{harv|Harborth|1978}}. Однако существуют сколь угодно большие множества точек в общем положении, которые не содержат пустой выпуклый [[Правильный семиугольник|семиугольник]].{{harv|Horton|1983}}

Таким образом, задача о пустых многоугольниках не является проблемой [[Теория Рамсея|теории Рамсея]] и в принципе решена.

Вопрос о существовании пустого [[Шестиугольник|шестиугольника]] долгое время оставался открытым. Но в {{harv|Nicolás|2007}} и {{harv|Gerken|2008}} } было доказано, что всякое достаточно большое множество точек в общем положении содержит пустой шестиугольник. Сегодня известно, что это множество должно содержать не более ''f''(9) (предположительно 129) и не менее 30 точек.{{harv|Overmars|2003}}.

== Примечания ==
{{примечания|2}}

== Литература ==
{{refbegin|2}}
*{{citation
| last1 = Chung | first1 = F.R.K. | author1-link = Fan Chung
| last2 = Graham | first2 = R.L. | author2-link = Ronald Graham
| doi = 10.1007/PL00009353
| journal = Discrete and Computational Geometry
| pages = 367–371
| issue = 3
| title = Forced convex n-gons in the plane
| volume = 19
| year = 1998}}.
*{{citation
| last1 = Erdős | first1 = P. | author1-link = Paul Erdős
| last2 = Szekeres | first2 = G. | author2-link = George Szekeres
| journal = Compositio Math
| pages = 463–470
| title = A combinatorial problem in geometry
| url = http://www.numdam.org/item?id=CM_1935__2__463_0
| volume = 2
| year = 1935}}.
*{{citation
| last1 = Erdős | first1 = P. | author1-link = Paul Erdős
| last2 = Szekeres | first2 = G. | author2-link = George Szekeres
| journal = Ann. Univ. Sci. Budapest. Eötvös Sect. Math.
| pages = 53–62
| title = On some extremum problems in elementary geometry
| volume = 3–4
| year = 1961}}. Reprinted in: {{citation
| last = Erdős | first = P. | author-link = Paul Erdős
| editor-last = Spencer | editor-first = J.
| location = Cambridge, MA
| pages = 680–689
| publisher = MIT Press
| title = The Art of Counting: Selected Writings
| year = 1973}}.
*{{citation
| last = Gerken | first = Tobias
| doi = 10.1007/s00454-007-9018-x
| issue = 1–3
| journal = Discrete and Computational Geometry
| pages = 239–272
| title = Empty convex hexagons in planar point sets
| volume = 39
| year = 2008}}.
*{{citation
| last = Grünbaum | first = Branko | authorlink = Branko Grünbaum
| edition = 2nd
| editor1-last = Kaibel | editor1-first = Volker
| editor2-last = Klee | editor2-first = Victor | editor2-link = Victor Klee
| editor3-last = Ziegler | editor3-first = Günter M. | editor3-link = Günter M. Ziegler
| isbn = 0-387-00424-6
| publisher = [[Springer-Verlag]]
| series = Graduate Texts in Mathematics
| title = Convex Polytopes
| volume = 221
| year = 2003}}.
*{{citation
| last = Harborth | first = Heiko
| issue = 5
| journal = Elem. Math.
| pages = 116–118
| title = Konvexe Fünfecke in ebenen Punktmengen
| volume = 33
| year = 1978}}.
*{{citation
| doi = 10.4153/CMB-1983-077-8
| last = Horton | first = J. D.
| issue = 4
| journal = [[Canadian Mathematical Bulletin]]
| pages = 482–484
| title = Sets with no empty convex 7-gons
| volume = 26
| year = 1983}}.
*{{citation
| last1 = Kalbfleisch | first1 = J.D.
| last2 = Kalbfleisch | first2 = J.G.
| last3 = Stanton | first3 = R.G.
| title = Proc. Louisiana Conf. Combinatorics, Graph Theory and Computing
| publisher = Louisiana State Univ.
| location = Baton Rouge, La.
| series = Congressus Numerantium
| pages = 180–188
| contribution = A combinatorial problem on convex regions
| volume = 1
| year = 1970}}.
*{{citation
| last1 = Kleitman | first1 = D.J. | author1-link = Daniel Kleitman
| last2 = Pachter | first2 = L.
| doi = 10.1007/PL00009358
| journal = Discrete and Computational Geometry
| pages = 405–410
| issue = 3
| title = Finding convex sets among points in the plane
| volume = 19
| year = 1998}}.
*{{citation
| last1 = Morris | first1 = W.
| last2 = Soltan | first2 = V.
| doi = 10.1090/S0273-0979-00-00877-6
| journal = Bulletin of the American Mathematical Society
| pages = 437–458
| title = The Erdős-Szekeres problem on points in convex position—A survey
| issue = 04
| url = http://www.ams.org/bull/2000-37-04/S0273-0979-00-00877-6/home.html
| volume = 37
| year = 2000}}.
*{{citation
| last = Nicolás | first = Carlos M.
| doi = 10.1007/s00454-007-1343-6
| issue = 2
| journal = Discrete and Computational Geometry
| pages = 389–397
| title = The empty hexagon theorem
| volume = 38
| year = 2007}}.
*{{citation
| last = Overmars | first = M. | author-link = Mark Overmars
| doi = 10.1007/s00454-002-2829-x
| journal = Discrete and Computational Geometry
| pages = 153–158
| title = Finding sets of points without empty convex 6-gons
| issue = 1
| volume = 29
| year = 2003}}.
*{{citation
| last = Peterson | first = Ivars
| journal = MAA Online
| title = Planes of Budapest
| url = http://www.maa.org/mathland/mathtrek_10_3_00.html
| year = 2000}}.
*{{citation
| last1 = Scheinerman | first1 = Edward R.
| last2 = Wilf | first2 = Herbert S.
| doi = 10.2307/2975158
| issue = 10
| journal = [[American Mathematical Monthly]]
| pages = 939–943
| title = The rectilinear crossing number of a complete graph and Sylvester's "four point problem" of geometric probability
| volume = 101
| year = 1994
| publisher = Mathematical Association of America
| jstor = 2975158}}.
*{{citation
| last1 = Szekeres | first1 = G. | author1-link = George Szekeres
| last2 = Peters | first2 = L.
| doi = 10.1017/S144618110000300X
| journal = [[ANZIAM Journal]]
| pages = 151–164
| title = Computer solution to the 17-point Erdős-Szekeres problem
| issue = 02
| url = http://www.austms.org.au/Publ/ANZIAM/V48P2/2409.html
| volume = 48
| year = 2006}}.
*{{citation
| last1 = Tóth | first1 = G.
| last2 = Valtr | first2 = P.
| doi = 10.1007/PL00009363
| journal = Discrete and Computational Geometry
| pages = 457–459
| title = Note on the Erdős-Szekeres theorem
| issue = 3
| volume = 19
| year = 1998}}.
*{{citation
| last1 = Tóth | first1 = G.
| last2 = Valtr | first2 = P.
| contribution = The Erdős-Szekeres theorem: upper bounds and related results
| pages = 557–568
| publisher = Mathematical Sciences Research Institute Publications, no. 52
| title = Combinatorial and computational geometry
| year = 2005}}.
*{{citation
| last = Valtr | first = P.
| title = On the empty hexagons
| url = http://kam.mff.cuni.cz/~valtr/h.ps
| year = 2006}}.
{{refend}}

==Ссылки==
* [http://planetmath.org/encyclopedia/HappyEndingProblem.html Happy ending problem] and [http://planetmath.org/encyclopedia/RamseyTheoreticProofOfTheErdHosSzekeresTheorem.html Ramsey-theoretic proof of the Erdős-Szekeres theorem] on [[PlanetMath]]
*{{mathworld | urlname = HappyEndProblem | title = Happy End Problem}}

[[:Категория:Евклидова геометрия]]
[[:Категория:Математика]]

[[ar:مسألة نهاية سعيدة]]
[[es:Problema del final feliz]]
[[fr:Happy Ending problem]]
[[en:Happy Ending problem]]
[[hu:Happy End-probléma]]
[[fi:Erdősin-Szekeresin konjektuuri]]
[[th:ปัญหาแฮปปี้เอ็นดิ้ง]]
[[zh:幸福結局問題]]

Версия от 11:55, 26 февраля 2013

  • Пусть последовательность координат соседних друг другу вершин -угольника без самопересечений . Тогда его площадь вычисляется по формуле:
, где (.
  • В самом общем случае площадь многоугольника вычисляется как сумма площадей треугольников, на которые он разбивается не пересекающимися диагоналями.
Источник — https://ru.wikipedia.org/ruwiki/w/index.php?title=Участник:МетаСкептик12/Черновик&oldid=52826734