Дискретная геометрия и комбинаторная геометрия — разделы геометрии , изучающие комбинаторные свойства и конструктивные методы дискретных геометрических объектов. Большинство вопросов по дискретной геометрии связаны с конечными или дискретными наборами основных геометрических объектов, таких как точки , линии , плоскости , круги , сферы , многоугольники и т. д. Предмет фокусируется на комбинаторных свойствах этих объектов, например, на том, как они пересекаются друг с другом или как их можно расположить, чтобы покрыть более крупный объект.
Дискретная геометрия во многом перекликается с выпуклой геометрией и вычислительной геометрией и тесно связана с такими предметами, как конечная геометрия , комбинаторная оптимизация , цифровая геометрия , дискретная дифференциальная геометрия , геометрическая теория графов , торическая геометрия и комбинаторная топология .
Хотя многогранники и мозаики уже много лет изучались такими людьми, как Кеплер и Коши , современная дискретная геометрия берет свое начало в конце 19 века. Ранними изучаемыми темами были : плотность упаковок кругов Туэ , проективные конфигурации Рея и Стейница , геометрия чисел Минковского и раскраски карт Тейта, Хивуда и Хадвигера .
Ласло Фейеш Тот , Х.С.М. Коксетер и Пол Эрдеш заложили основы дискретной геометрии . [1] [2] [3]
Многогранник — это геометрический объект с плоскими сторонами, который существует в любом общем количестве измерений. Многоугольник — это многогранник в двух измерениях, многогранник в трех измерениях и т. д. в более высоких измерениях (например, 4 -мерный многогранник в четырех измерениях). Некоторые теории далее обобщают идею, включая такие объекты, как неограниченные многогранники ( апейротопы и мозаики ) и абстрактные многогранники .
Ниже приведены некоторые аспекты многогранников, изучаемые в дискретной геометрии:
Упаковки, покрытия и мозаики — это способы правильного расположения однородных объектов (обычно кругов, сфер или плиток) на поверхности или многообразии .
Упаковка сфер — это расположение непересекающихся сфер внутри вмещающего пространства. Рассматриваемые сферы обычно имеют одинаковый размер, а пространство обычно представляет собой трехмерное евклидово пространство . Однако проблемы упаковки сфер можно обобщить, чтобы рассмотреть неравные сферы, n -мерное евклидово пространство (где проблемой становится упаковка кругов в двух измерениях или упаковка гиперсфер в более высоких измерениях) или неевклидовы пространства, такие как гиперболическое пространство .
Мозаика плоской поверхности — это мозаика плоскости с использованием одной или нескольких геометрических фигур, называемых плитками, без перекрытий и пробелов. В математике тесселяции можно обобщить на более высокие измерения.
Конкретные темы в этой области включают в себя:
Структурная жесткость — это комбинаторная теория для прогнозирования гибкости ансамблей, образованных твердыми телами, соединенными гибкими связями или шарнирами .
Темы в этой области включают в себя:
Структуры инцидентности обобщают плоскости (такие как аффинные , проективные и плоскости Мёбиуса ), как можно видеть из их аксиоматических определений. Структуры инцидентности также обобщают многомерные аналоги, а конечные структуры иногда называют конечными геометриями .
Формально структура инцидентности представляет собой тройку
где P — набор «точек», L — набор «линий» и — отношение инцидентности . Элементы называются флагами. Если
мы говорим, что точка p «лежат на» прямой .
Темы в этой области включают в себя:
Ориентированный матроид — это математическая структура , которая абстрагирует свойства ориентированных графов и расположения векторов в векторном пространстве над упорядоченным полем (особенно для частично упорядоченных векторных пространств ). [4] Для сравнения, обычный (то есть неориентированный) матроид абстрагирует свойства зависимости , которые являются общими как для графов , которые не обязательно направлены , так и для расположения векторов над полями , которые не обязательно упорядочены . [5] [6]
Геометрический граф — это граф , вершины или ребра которого связаны с геометрическими объектами. Примеры включают евклидовы графы, 1- скелет многогранника или многогранника , графы единичного диска и графы видимости .
Темы в этой области включают в себя:
Симплициальный комплекс — это топологическое пространство определенного вида, построенное путем «склейки» точек , отрезков прямых , треугольников и их n -мерных аналогов (см. иллюстрацию). Симплициальные комплексы не следует путать с более абстрактным понятием симплициального множества , появляющимся в современной теории симплициальных гомотопий. Чисто комбинаторным аналогом симплициального комплекса является абстрактный симплициальный комплекс . См. также случайные геометрические комплексы .
Дисциплина комбинаторная топология использовала комбинаторные понятия топологии и в начале 20 века превратилась в область алгебраической топологии .
В 1978 году ситуация изменилась – для решения задачи комбинаторики были использованы методы алгебраической топологии – когда Ласло Ловас доказал гипотезу Кнезера , положив тем самым начало новому исследованию топологической комбинаторики . В доказательстве Ловаса использовалась теорема Борсука-Улама , и эта теорема сохраняет заметную роль в этой новой области. Эта теорема имеет множество эквивалентных версий и аналогов и использовалась при изучении проблем справедливого дележа .
Темы в этой области включают в себя:
Дискретная группа — это группа G , наделенная дискретной топологией . Благодаря этой топологии G становится топологической группой . Дискретная подгруппа топологической группы G — это подгруппа H , относительная топология которой дискретна. Например, целые числа Z образуют дискретную подгруппу действительных чисел R ( со стандартной метрической топологией ), а рациональные числа Q — нет.
Решетка в локально компактной топологической группе — это дискретная подгруппа , фактор -пространство которой имеет конечную инвариантную меру . В частном случае подгрупп Rn это сводится к обычному геометрическому понятию решетки , и как алгебраическая структура решеток , так и геометрия совокупности всех решеток относительно хорошо поняты. Глубокие результаты Бореля , Хариш-Чандры , Мостоу , Тамагавы , М. С. Рагунатана , Маргулиса , Циммера, полученные с 1950-х по 1970-е годы, предоставили примеры и обобщили большую часть теории на случай нильпотентных групп Ли и полупростых алгебраических групп над локальным полем . В 1990-х годах Басс и Любоцкий инициировали изучение решеток деревьев , которое остается активной областью исследований.
Темы в этой области включают в себя:
Цифровая геометрия имеет дело с дискретными наборами (обычно дискретными наборами точек ), которые считаются оцифрованными моделями или изображениями объектов 2D или 3D евклидова пространства .
Проще говоря, оцифровка — это замена объекта дискретным набором его точек. Изображения, которые мы видим на экране телевизора, растровом дисплее компьютера или в газетах, на самом деле являются цифровыми изображениями.
Его основными областями применения являются компьютерная графика и анализ изображений . [7]
Дискретная дифференциальная геометрия — это исследование дискретных аналогов понятий дифференциальной геометрии . Вместо гладких кривых и поверхностей — многоугольники , сетки и симплициальные комплексы . Он используется при изучении компьютерной графики и топологической комбинаторики .
Темы в этой области включают в себя:
{{cite book}}: CS1 maint: multiple names: authors list (link){{cite book}}: CS1 maint: multiple names: authors list (link)