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

«Комбинаторная геометрия» перенаправляется сюда. Термин комбинаторная геометрия также используется в теории матроидов для обозначения простого матроида , особенно в старых текстах.

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

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

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

История

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

Ласло Фейеш Тот , Х.С.М. Коксетер и Пол Эрдеш заложили основы дискретной геометрии .

Темы

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

Основные статьи: Многогранник и Многогранник

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

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

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

Упаковки, покрытия и черепица

Основные статьи: упаковка кругов и мозаика

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

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

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

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

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

жесткость

Основная статья: Структурная жесткость

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

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

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

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

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

Основная статья: Структура заболеваемости

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

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

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

$C=(P,L,I).\,$

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

$(p,l)\in I,$

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

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

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

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

Основная статья: Ориентированный матроид

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

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

Основная статья: Геометрическая теория графов

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

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

• Рисование графика
• Многогранные графы
• Случайные геометрические графики
• Диаграммы Вороного и триангуляции Делоне

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

Основная статья: Симплициальный комплекс

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

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

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

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

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

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

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

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

Основные статьи: Решетка (группа) и дискретная группа

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

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

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

• Группы отражения
• Треугольные группы

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

Основная статья: Цифровая геометрия

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

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

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

дифференциальная

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

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

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

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

См. также

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

Ссылки

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