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

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

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

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

История

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

Ласло Фейес Тот , HSM Coxeter и Пол Эрдёш заложили основы дискретной геометрии .

Темы

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

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

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

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

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

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

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

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

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

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

Структурная жесткость и гибкость

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примечания

использованная литература

• Бездек, Андраш (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). Проблемы исследования дискретной геометрии . Берлин: Springer. ISBN 0-387-23815-8.
• Пах, Янош ; Агарвал, Панкадж К. (1995). Комбинаторная геометрия . Нью-Йорк: Wiley-Interscience. ISBN 0-471-58890-3.
• Гудман, Джейкоб Э. и О'Рурк, Джозеф (2004). Справочник по дискретной и вычислительной геометрии, второе издание . Бока-Ратон: Chapman & Hall / CRC. ISBN 1-58488-301-4.CS1 maint: несколько имен: список авторов ( ссылка )
• Грубер, Питер М. (2007). Выпуклая и дискретная геометрия . Берлин: Springer. ISBN 978-3-540-71132-2.
• Матушек, Иржи (2002). Лекции по дискретной геометрии . Берлин: Springer. ISBN 0-387-95374-4.
• Владимир Болтянский , Хорст Мартини , Петру С. Солтан (1997). Экскурсии в комбинаторную геометрию . Springer. ISBN 3-540-61341-2.CS1 maint: несколько имен: список авторов ( ссылка )