Комбинаторная геометрия (TkbQnugmkjugx iykbymjnx)

Комбинаторная или дискретная геометрия — раздел геометрии, в котором изучаются комбинаторные свойства геометрических объектов и связанные с ними конструкции. В комбинаторной геометрии рассматривают конечные и бесконечные дискретные множества или структуры базовых однотипных геометрических объектов (точек, прямых, окружностей, многоугольников, тел с одинаковым диаметром, целочисленных решёток и т. п.) и ставят вопросы, связанные со свойствами различных геометрических конструкций из этих объектов или на этих структурах. Проблемы комбинаторной геометрии простираются от конкретных «предметно»-комбинаторных вопросов (хотя и не всегда с простыми ответами) — замощения, упаковка кругов на плоскости, формула Пика — до вопросов общих и глубоких, таких как гипотеза Борсука, проблема Нелсона — Эрдёша — Хадвигера.

История

Хотя многогранники, замощения и упаковка шаров исследовались ещё Кеплером и Коши, современная комбинаторная геометрия начала формироваться в конце XIX века. Одними из первых задач были: плотность упаковки кругов Акселя Туэ, проективная конфигурация^[англ.] Штайница, геометрия чисел Минковского и проблема четырёх красок Фрэнсиса Гутри^[англ.].

Примеры задач

Представление о диапазоне задач комбинаторной геометрии дают следующие примеры.

Лемма Витали о покрытиях — комбинаторногеометрический результат. Широко используется в теории меры.

Ромботришестиугольная упаковка шаров, одна из 11 возможных симметричных упаковок

Задача о возможных и наиболее плотных упаковках кругов на плоскости и шаров в пространстве. Наиболее плотные упаковки кругов и шаров представляются очевидными. Но полное математическое доказательство для кругов было получено только в 1940 году^[1]. Для шаров компьютерное доказательство гипотезы Кеплера появилось спустя 400 лет в 1998 году в работе математика Томаса Хейлса^[англ.]

Восемь точек в общем положении, для которых нет выпуклого пятиугольника

Теорема Эрдёша — Секереша о выпуклых многоугольниках утверждает, что в любом достаточно большом множестве точек в общем положении на плоскости можно найти $n$ точек, являющихся вершинами выпуклого многоугольника. Гипотеза Эрдёша — Секереша о минимальном числе точек, обязательно содержащих выпуклый $n$ -угольник, на сегодня не доказана. Данная задача является также задачей теории Рамсея.

Теорема Минковского о выпуклом теле. Пусть $S$ — замкнутое выпуклое тело, симметричное относительно начала координат $O$ $n$ -мерного евклидова пространства, имеющее объём $\geq 2^{n}$ . Тогда в $S$ найдётся целочисленная точка, отличная от $O$ . Эта теорема положила начало геометрии чисел.

Гипотеза Борсука утверждает, что любое тело диаметра $d$ в $n$ -мерном евклидовом пространстве можно разбить на $n+1$ часть так, что диаметр каждой части будет меньше $d$ . Эта гипотеза была доказана для размерностей $2$ и $3$ , но опровергнута для пространств большой размерности. По известной сегодня оценке она неверна для пространств размерности 64 и более^[2].

Задача Данцера — Грюнбаума заключается в поиске конечного множества из как можно большего количества точек в многомерном пространстве, между которыми можно построить только острые углы.
Задача «никакие три точки не лежат на одной прямой», состоящая в нахождении количества точек, которые можно расположить на решётке $n\times n$ так, чтобы никакие три точки не находились на одной прямой.

См. также

Примечания

↑ Chang, Hai-Chau; Wang, Lih-Chung (2010). "A Simple Proof of Thue's Theorem on Circle Packing". arXiv:1009.4322v1 [math.MG]. {{cite arXiv}}: Неизвестный параметр |accessdate= игнорируется (справка)
↑ Thomas Jenrich, A 64-dimensional two-distance counterexample to Borsuk’s conjecture Архивная копия от 26 декабря 2018 на Wayback Machine

Ссылки

Грюнбаум Б. Этюды по комбинаторной геометрии и теории выпуклых тел. — 1971.
Фейеш Тот, Ласло. Расположения на плоскости, на сфере и в пространстве. — М.: Физматгиз, 1958. — 364 с. — 4500 экз.
Bezdek, András; Kuperberg, W. Discrete geometry: in honor of W. Kuperberg's 60th birthday (англ.). — New York, N.Y: Marcel Dekker^[англ.], 2003. — ISBN 0-8247-0968-3.
Bezdek, Károly. Classical Topics in Discrete Geometry (неопр.). — New York, N.Y: Springer, 2010. — ISBN 978-1-4419-0599-4.
Brass, Peter; Moser, William; Pach, János^[англ.]. Research problems in discrete geometry (неопр.). — Berlin: Springer, 2005. — ISBN 0-387-23815-8.
Pach, János^[англ.]; Agarwal, Pankaj K. Combinatorial geometry (неопр.). — New York: Wiley-Interscience, 1995. — ISBN 0-471-58890-3.
Goodman, Jacob E. and O'Rourke, Joseph. Handbook of Discrete and Computational Geometry, Second Edition (англ.). — Boca Raton: Chapman & Hall/CRC, 2004. — ISBN 1-58488-301-4.
Gruber, Peter M. Convex and Discrete Geometry. — Berlin: Springer, 2007. — ISBN 3-540-71132-5.
Matoušek, Jiří. Lectures on discrete geometry. — Berlin: Springer, 2002. — ISBN 0-387-95374-4.
Vladimir Boltyanski, Horst Martini, Petru S. Soltan,. Excursions into Combinatorial Geometry (неопр.). — Springer, 1997. — ISBN 3-540-61341-2.

[ChangWang-1] Chang, Hai-Chau; Wang, Lih-Chung (2010). "A Simple Proof of Thue's Theorem on Circle Packing". arXiv:1009.4322v1 [math.MG]. {{cite arXiv}}: Неизвестный параметр |accessdate= игнорируется (справка)

[2] Thomas Jenrich, A 64-dimensional two-distance counterexample to Borsuk’s conjecture Архивная копия от 26 декабря 2018 на Wayback Machine

[1]

[2]