Войти
Набор окружностей и соответствующих граф единичного диска Дискретная геометрия и комбинаторная геометрия являются ветвями геометрии, изучающими комбинаторные свойства и конструктивные методы дискретных геометрические объекты. Большинство вопросов по дискретной геометрии связаны с конечными или дискретными наборами базовых геометрических объектов, таких как точек, линий, плоскости, круги, сферы, многоугольники и т. Д. Субъект сосредотачивается на комбинаторных свойствах этих объектов, таких как то, как они пересекаются друг с другом, или как они могут быть расположены, чтобы покрыть более крупный объект.
Дискретная геометрия во многом пересекается с выпуклой геометрией и вычислительной геометрией и тесно связана с такими предметами, как конечная геометрия, комбинаторная оптимизация, цифровая геометрия, дискретная дифференциальная геометрия, геометрическая теория графов, торическая геометрия и комбинаторная топология.
Хотя многогранники и мозаики многие годы изучались такими людьми, как Кеплер и d Коши, современная дискретная геометрия берет свое начало в конце 19 века. Первыми изучаемыми темами были: плотность кольцевых упаковок по Туэ, проективные конфигурации по Рейе и Стейниц, геометрия номера Минковски и раскраски карт Тейта, Хивуда и Хадвигера.
Ласло Фейес Тот, HSM Кокстер и Пол Эрдёш заложили основы дискретной геометрии.
A Многогранник представляет собой геометрический объект с плоским сторон, которое существует в любом общем количестве измерений. Многоугольник - это двухмерный многогранник, многогранник в трех измерениях и т. Д. В более высоких измерениях (например, 4-многогранник в четырех измерениях). Некоторые теории дополнительно обобщают идею включения таких объектов, как неограниченные многогранники (апейротопы и мозаики ) и абстрактные многогранники.
. Ниже приведены некоторые из изученных аспектов многогранников. в дискретной геометрии:
Упаковки, покрытия и мозаики - это все способы размещения однородных объектов (обычно кругов, сфер или плиток) регулярным образом на поверхности или многообразии.
A упаковка сфер - это расположение неперекрывающихся сфер внутри содержащее пространство. Рассматриваемые сферы обычно имеют одинаковый размер, а пространство обычно трех- мерное евклидово пространство. Однако проблемы упаковки сфер могут быть обобщены для рассмотрения неравных сфер, n-мерного евклидова пространства (где проблема сводится к упаковке кругов в двух измерениях или упаковке гиперсферы в более высоких измерениях) или в неевклидово пространства, такие как гиперболическое пространство.
A тесселяция плоской поверхности - это мозаика плоскости с использованием одного или нескольких геометрические формы, называемые плиткой, без нахлестов и разрывов. В математике мозаики можно обобщить на более высокие измерения.
Конкретные темы в этой области включают:
Графики изображены в виде стержней, соединенных вращающимися шарнирами. График цикла C4, нарисованный в виде квадрата, может быть наклонен синей силой в параллелограмм, так что это гибкий график. K 3, нарисованный в виде треугольника, не может быть изменен какой-либо силой, приложенной к нему, поэтому это жесткий график. Структурная жесткость - это комбинаторная теория для прогнозирования гибкости ансамблей, образованных твердыми телами, соединенными гибкими связями или шарнирами.
В этой области рассматриваются следующие темы:
Семь точек - это элементы семи линий в плоскости Фано, пример структуры инцидентности. Структуры инцидентности обобщают плоскости (например, аффинные, проективные и плоскости Мёбиуса ), что видно из их аксиоматических определений. Структуры инцидентности также являются обобщением многомерных аналогов, и конечные структуры иногда называют конечными геометриями.
Формально структура инцидентности представляет собой тройную
где P - набор "точек", L - набор "линий" и 
мы говорим, что точка p «лежит на» линии 
Темы в этой области включают:
ориентированный матроид - это математическая структура, которая абстрагирует свойства ориентированных графов и расположения векторов в векторном пространстве над упорядоченным полем (особенно для частично упорядоченных векторных пространств ). Для сравнения, обычный (т.е. неориентированный) матроид абстрагирует свойства зависимости, которые являются общими как для графов, которые не обязательно направлены, так и для расположение векторов над полями , которые не обязательно упорядочены.
A геометрический граф - это граф, в котором вершины или ребра связаны с геометрическими объектами. Примеры включают евклидовы графы, 1- скелет многогранника или многогранник и графы видимости.
В этой области рассматриваются следующие темы:
A симплициальный комплекс - это топологическое пространство определенного вида, построены путем «склеивания» точек, отрезков, треугольников и их n-мерных аналогов (см. иллюстрацию). Симплициальные комплексы не следует путать с более абстрактным понятием симплициального множества, появляющимся в современной теории симплициальных гомотопий. Чисто комбинаторный аналог симплициального комплекса - это абстрактный симплициальный комплекс.
Дисциплина комбинаторной топологии использовала комбинаторные концепции в топологии, а в начале 20 века это превратился в область алгебраической топологии.
В 1978 году ситуация изменилась - методы из алгебраической топологии были использованы для решения задачи в комбинаторике - когда Ласло Ловас доказал гипотеза Кнезера, тем самым положив начало новому исследованию топологической комбинаторики . В доказательстве Ловаса использовалась теорема Борсука-Улама, и эта теорема сохраняет важную роль в этой новой области. Эта теорема имеет множество эквивалентных версий и аналогов и использовалась при исследовании задач справедливого деления.
Темы в этой области включают:
A дискретная группа - это группа G, оснащенная дискретная топология. С этой топологией G становится топологической группой . Дискретная подгруппа топологической группы G - это подгруппа H, относительная топология которой является дискретной. Например, целые числа, Zобразуют дискретную подгруппу вещественных чисел, R(со стандартной метрической топологией ), но рациональные числа, Q, не делайте.
A решетка в локально компактной топологической группе представляет собой дискретную подгруппу со свойством, что фактор-пространство имеет конечное инвариантная мера. В частном случае подгрупп в R, это составляет обычное геометрическое понятие решетки, и как алгебраическая структура решеток, так и геометрия совокупности всех решеток относительно понятно хорошо. Глубокие результаты Бореля, Хариш-Чандра, Мостоу, Тамагава, М. С. Рагхунатан, Маргулис, Циммер, полученные с 1950-х по 1970-е годы, предоставили примеры и обобщили большую часть теории на нильпотентный Группы Ли и полупростые алгебраические группы над локальным полем. В 1990-х годах Басс и Любоцкий инициировали изучение решеток деревьев, которое остается активной областью исследований.
В этой области рассматриваются следующие темы:
Цифровая геометрия имеет дело с дискретными наборами (обычно дискретными точки множества) считаются оцифрованными моделями или изображениями объектов 2D или 3D евклидова пространства.
Проще говоря, оцифровка заменяет объект дискретным набором его точек. Изображения, которые мы видим на экране телевизора, растровом дисплее компьютера или в газетах, на самом деле являются цифровыми изображениями.
Его основные области применения - компьютерная графика и анализ изображений.
Дискретная дифференциальная геометрия - это исследование дискретных аналогов понятий в дифференциальная геометрия. Вместо гладких кривых и поверхностей используются многоугольники, сетки и симплициальные комплексы. Он используется при изучении компьютерной графики и топологической комбинаторики.
. В эту область входят следующие темы:
