Комбінаторна геометрія

Комбінаторна або дискретна геометрія — розділ геометрії, в якому вивчаються комбінаторні властивості геометричних об'єктів та пов'язані з ними конструкції. У комбінаторній геометрії розглядають скінченні і нескінченні дискретні множини або структури базових однотипних геометричних об'єктів (точок, прямих, кіл, многокутників, тіл з однаковим діаметром, цілочисельних ґраток тощо) і ставлять питання, пов'язані з властивостями різних геометричних конструкцій з цих об'єктів або на цих структурах. Проблеми комбінаторної геометрії простягаються від конкретних «предметно»-комбінаторних питань (хоча і не завжди з простими відповідями) — замощення, пакування кіл на площині, формула Піка — до питань загальних і глибоких — гіпотеза Борсука, проблема Нельсона — Ердеша — Гадвігера.

Хоча многогранники, замощення і пакування куль досліджувалися ще Кеплером і Коші, сучасна комбінаторна геометрія почала формуватися в кінці 19-го століття. Одними з перших завдань були: щільність пакування кіл Акселя Туе^[ru], проективна конфігурація Штайніца, геометрія чисел Мінковського і проблема чотирьох фарб Френсіса Гатрі^[en]).

Уявлення про діапазон задач комбінаторної геометрії дають такі приклади.

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

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

• Задача зі щасливим кінцем стверджує, що в будь-якій достатньо великій множині точок у загальному положенні на площині можна знайти ${\displaystyle n}$точок, які є вершинами опуклого многокутника. Гіпотезу Ердеша — Секереша про найменше число точок, які обов'язково містять опуклий ${\displaystyle n}$-кутник, на сьогодні не доведено. Дана задача є також завданням теорії Рамсея.

• Теорема Мінковського про опукле тіло. Нехай ${\displaystyle S}$ — замкнуте опукле тіло, симетричне відносно початку координат ${\displaystyle O}$ ${\displaystyle n}$-вимірного евклідового простору, що має об'єм ${\displaystyle \geq 2^{n}}$. Тоді в ${\displaystyle S}$ знайдеться цілочисельна точка, відмінна від ${\displaystyle O}$. Ця теорема поклала початок геометрії чисел.

• Гіпотеза Борсука стверджує, що будь-яке тіло діаметра ${\displaystyle d}$ в ${\displaystyle n}$-вимірному евклідовому просторі можна розбити на ${\displaystyle n+1}$ частину так, що діаметр кожної частини буде меншим, ніж ${\displaystyle d}$. Цю гіпотезу було доведено для розмірностей ${\displaystyle 2}$ і ${\displaystyle 3}$, але спростовано для просторів більшої розмірності. За відомою сьогодні оцінкою вона не правильна для просторів розмірності 64 і більше^[2].

• Задача Данцера — Ґрюнбаума полягає в пошуку скінченної множини з якомога більшої кількості точок у багатовимірному просторі, між якими можна побудувати тільки гострі кути.

• Обчислювальна геометрія
• Скінченна геометрія
• Геометрія чисел
• Комбінаторика багатогранників
• Алгебрична комбінаторика

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