Дискретная геометрия

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

Набор окружностей и соответствующий граф единичного круга

Дискретная геометрия и комбинаторная геометрия — это разделы геометрии , которые изучают комбинаторные свойства и конструктивные методы дискретных геометрических объектов. Большинство вопросов по дискретной геометрии связаны с конечными или дискретными наборами основных геометрических объектов, таких как точки , линии , плоскости , окружности , сферы , многоугольники и т. д. Предмет фокусируется на комбинаторных свойствах этих объектов, таких как то, как они пересекаются друг с другом, или как они могут быть расположены, чтобы покрыть более крупный объект.

Дискретная геометрия во многом пересекается с выпуклой геометрией и вычислительной геометрией и тесно связана с такими дисциплинами, как конечная геометрия , комбинаторная оптимизация , цифровая геометрия , дискретная дифференциальная геометрия , геометрическая теория графов , торическая геометрия и комбинаторная топология .

История

Хотя многогранники и мозаики изучались в течение многих лет такими людьми, как Кеплер и Коши , современная дискретная геометрия берет свое начало в конце 19-го века. Ранними изученными темами были: плотность упаковок кругов Туэ , проективные конфигурации Рейе и Стейница , геометрия чисел Минковского и раскраски карт Тейта, Хивуда и Хадвигера .

Ласло Фейеш Тот , Х.С.М. Коксетер и Пол Эрдеш заложили основы дискретной геометрии . ^{[1] [2] [3]}

Темы

Многогранники и многогранники

Многогранник — это геометрический объект с плоскими сторонами, который существует в любом общем числе измерений. Многоугольник — это многогранник в двух измерениях, многогранник в трех измерениях и так далее в более высоких измерениях (например, 4-многогранник в четырех измерениях). Некоторые теории еще больше обобщают эту идею, включая такие объекты, как неограниченные многогранники ( апейротопы и тесселяции ) и абстрактные многогранники .

Ниже приведены некоторые аспекты многогранников, изучаемые в дискретной геометрии:

• Многогранная комбинаторика
• Решётчатые многогранники
• Полиномы Эрхарта
• Теорема Пика
• гипотеза Хирша
• Непрозрачный набор

Упаковки, покрытия и облицовка

Упаковки, покрытия и плитки — это способы размещения однородных объектов (обычно кругов, сфер или плиток) в регулярном порядке на поверхности или многообразии .

Упаковка сфер — это расположение неперекрывающихся сфер в содержащем пространстве. Рассматриваемые сферы обычно имеют одинаковый размер, а пространство обычно представляет собой трехмерное евклидово пространство . Однако задачи упаковки сфер можно обобщить для рассмотрения неравных сфер, n -мерного евклидова пространства (где задача становится упаковкой кругов в двух измерениях или упаковкой гиперсфер в более высоких измерениях) или неевклидовых пространств, таких как гиперболическое пространство .

Тесселяция плоской поверхности — это мозаичное покрытие плоскости одной или несколькими геометрическими фигурами, называемыми плитками, без наложений и без зазоров. В математике тесселяции могут быть обобщены на более высокие измерения.

Конкретные темы в этой области включают:

• Круговые упаковки
• Упаковки сфер
• гипотеза Кеплера
• Квазикристаллы
• Апериодичные мозаики
• Периодический график
• Правила конечного подразделения

Жесткость и гибкость конструкции

Графы рисуются как стержни, соединенные вращающимися шарнирами. Граф цикла C _{4 ,} нарисованный как квадрат, может быть наклонен синей силой в параллелограмм, поэтому он является гибким графом. K ₃ , нарисованный как треугольник, не может быть изменен никакой силой, которая к нему приложена, поэтому он является жестким графом.

Конструкционная жесткость — это комбинаторная теория для прогнозирования гибкости ансамблей, образованных жесткими телами, соединенными гибкими связями или шарнирами .

Темы в этой области включают:

• Теорема Коши
• Гибкие многогранники

Структуры заболеваемости

Семь точек являются элементами семи прямых на плоскости Фано , пример структуры инцидентности.

Структуры инцидентности обобщают плоскости (такие как аффинные , проективные и плоскости Мёбиуса ), как можно видеть из их аксиоматических определений. Структуры инцидентности также обобщают аналоги более высокой размерности, а конечные структуры иногда называют конечными геометриями .

Формально структура инцидентности представляет собой тройку

${\displaystyle C=(P,L,I).\,}$

где P — набор «точек», L — набор «линий», а — отношение инцидентности . Элементы называются флагами. Если ${\displaystyle I\subseteq P\times L}$ ${\displaystyle I}$

${\displaystyle (p,l)\in I,}$

мы говорим, что точка p «лежит на» прямой . ${\displaystyle l}$

Темы в этой области включают:

• Конфигурации
• Линейные расположения
• Гиперплоскостные конфигурации
• Здания

Ориентированные матроиды

Ориентированный матроид — это математическая структура , которая абстрагирует свойства направленных графов и расположений векторов в векторном пространстве над упорядоченным полем (особенно для частично упорядоченных векторных пространств ). ^[4] Для сравнения, обычный (т.е. неориентированный) матроид абстрагирует свойства зависимости , которые являются общими как для графов , которые не обязательно направлены , так и для расположений векторов над полями , которые не обязательно упорядочены . ^{[5] [6]}

Геометрическая теория графов

Геометрический граф — это граф , в котором вершины или ребра связаны с геометрическими объектами. Примерами служат евклидовы графы, 1- скелет многогранника или политопа , графы единичных дисков и графы видимости .

Темы в этой области включают:

• Графическое изображение
• Полиэдральные графы
• Случайные геометрические графы
• Диаграммы Вороного и триангуляции Делоне

Симплициальные комплексы

Симплициальный комплекс — это топологическое пространство определенного вида, построенное путем «склеивания» точек , отрезков прямых , треугольников и их n -мерных аналогов (см. иллюстрацию). Симплициальные комплексы не следует путать с более абстрактным понятием симплициального множества, появляющимся в современной симплициальной гомотопической теории. Чисто комбинаторным аналогом симплициального комплекса является абстрактный симплициальный комплекс . См. также случайные геометрические комплексы .

Топологическая комбинаторика

Дисциплина комбинаторной топологии использовала комбинаторные концепции в топологии и в начале 20 века превратилась в область алгебраической топологии .

В 1978 году ситуация изменилась на противоположную – методы алгебраической топологии были использованы для решения проблемы комбинаторики – когда Ласло Ловас доказал гипотезу Кнезера , тем самым положив начало новому исследованию топологической комбинаторики . Доказательство Ловаса использовало теорему Борсука-Улама , и эта теорема сохраняет важную роль в этой новой области. Эта теорема имеет много эквивалентных версий и аналогов и использовалась при изучении проблем справедливого дележа .

Темы в этой области включают:

• Лемма Шпернера
• Обычные карты

Решетки и дискретные группы

Дискретная группа — это группа G, снабженная дискретной топологией . С этой топологией G становится топологической группой . Дискретная подгруппа топологической группы G — это подгруппа H , относительная топология которой является дискретной. Например, целые числа , Z , образуют дискретную подгруппу действительных чисел , R ( со стандартной метрической топологией ), но рациональные числа , Q , не образуют.

Решетка в локально компактной топологической группе является дискретной подгруппой со свойством, что факторпространство имеет конечную инвариантную меру . В частном случае подгрупп R ⁿ это равносильно обычному геометрическому понятию решетки , и как алгебраическая структура решеток, так и геометрия совокупности всех решеток относительно хорошо изучены. Глубокие результаты Бореля , Хариш-Чандры , Мостова , Тамагавы , М. С. Рагхунатхана , Маргулиса , Циммера , полученные с 1950-х по 1970-е годы, предоставили примеры и обобщили большую часть теории на случай нильпотентных групп Ли и полупростых алгебраических групп над локальным полем . В 1990-х годах Басс и Любоцкий инициировали изучение решеток деревьев , которое остается активной областью исследований.

Темы в этой области включают:

• Группы размышлений
• Треугольные группы

Цифровая геометрия

Цифровая геометрия имеет дело с дискретными множествами (обычно дискретными точечными множествами), которые считаются оцифрованными моделями или изображениями объектов двумерного или трехмерного евклидова пространства .

Проще говоря, оцифровка — это замена объекта дискретным набором его точек. Изображения, которые мы видим на экране телевизора, растровом дисплее компьютера или в газетах, на самом деле являются цифровыми изображениями.

Его основными областями применения являются компьютерная графика и анализ изображений . ^[7]

Дискретная дифференциальная геометрия

Дискретная дифференциальная геометрия — это изучение дискретных аналогов понятий дифференциальной геометрии . Вместо гладких кривых и поверхностей существуют многоугольники , сетки и симплициальные комплексы . Она используется при изучении компьютерной графики и топологической комбинаторики .

Темы в этой области включают:

• Дискретный оператор Лапласа
• Дискретное внешнее исчисление
• Дискретное исчисление
• Дискретная теория Морзе
• Топологическая комбинаторика
• Анализ формы спектра
• Анализ фракталов

Смотрите также

• Дискретная и вычислительная геометрия (журнал)
• Дискретная математика
• Пол Эрдёш

Примечания

1. Пач, Янош; и др. (2008), Интуитивная геометрия, памяти Ласло Фейеша Тота, Институт математики Альфреда Реньи
2. Катона, GOH (2005), «Ласло Фейеш Тот – Некролог», Studia Scientiarum Mathematicarum Hungarica , 42 (2): 113
3. Барань, Имре (2010), «Дискретная и выпуклая геометрия», в Хорвате, Янош (ред.), Панорама венгерской математики в двадцатом веке, I , Нью-Йорк: Springer, стр. 431–441, ISBN 9783540307211
4. Rockafellar 1969. Бьорнер и др., Главы 1–3. Боковский, глава 1. Циглер, глава 7.
5. Бьёрнер и др., Главы 1-3. Боковский, Главы 1-4.
6. Поскольку матроиды и ориентированные матроиды являются абстракциями других математических абстракций, почти все соответствующие книги написаны для ученых-математиков, а не для широкой публики. Для изучения ориентированных матроидов хорошей подготовкой будет изучение учебника по линейной оптимизации Неринга и Такера, который пронизан идеями ориентированных матроидов, а затем перейти к лекциям Циглера по многогранникам.
7. См. Ли Чен, Цифровая и дискретная геометрия: теория и алгоритмы, Springer, 2014.

Ссылки

• Bezdek, András (2003). Дискретная геометрия: в честь 60-летия В. Куперберга . Нью-Йорк, Нью-Йорк: Марсель Деккер. ISBN 0-8247-0968-3.
• Бездек, Карой (2010). Классические темы дискретной геометрии . Нью-Йорк, штат Нью-Йорк: Спрингер. ISBN 978-1-4419-0599-4.
• Bezdek, Károly (2013). Lectures on Sphere Arrangements - the Discrete Geometric Side . Нью-Йорк, Нью-Йорк: Springer. ISBN 978-1-4614-8117-1.
• Bezdek, Károly ; Deza, Antoine; Ye, Yinyu (2013). Дискретная геометрия и оптимизация . Нью-Йорк, Нью-Йорк: Springer. ISBN 978-3-319-00200-2.
• Брасс, Питер; Мозер, Уильям; Пах, Янош (2005). Исследовательские проблемы в дискретной геометрии . Берлин: Springer. ISBN 0-387-23815-8.
• Пах, Янош ; Агарвал, Панкадж К. (1995). Комбинаторная геометрия . Нью-Йорк: Wiley-Interscience. ISBN 0-471-58890-3.
• Гудман, Джейкоб Э. и О'Рурк, Джозеф (2004). Справочник по дискретной и вычислительной геометрии, второе издание . Бока-Ратон: Chapman & Hall/CRC. ISBN 1-58488-301-4.{{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )
• Грубер, Питер М. (2007). Выпуклая и дискретная геометрия . Берлин: Springer. ISBN 978-3-540-71132-2.
• Матушек, Иржи (2002). Лекции по дискретной геометрии . Берлин: Шпрингер. ISBN 0-387-95374-4.
• Владимир Болтянский , Хорст Мартини, Петру С. Солтан (1997). Экскурсии в комбинаторную геометрию . Springer. ISBN 3-540-61341-2.{{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )