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

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

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

История [ править ]

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

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

Темы [ править ]

Многогранники и многогранники [ править ]

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

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

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

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

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

Основные статьи: упаковка кругов и тесселяция

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

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

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

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

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

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

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

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

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

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

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

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

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

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

где Р представляет собой набор «точек», L представляет собой набор «линий» , и это частота отношение. Элементы называются флагами. Если

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

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

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

Ориентированные матроиды [ править ]

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

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

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

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

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

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

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

Симплициальные комплексы [ править ]

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

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

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

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

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

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

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

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

Решетки и дискретные группы [ править ]

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

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

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

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

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

Цифровая геометрия [ править ]

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

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

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

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

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

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

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

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

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

См. Также [ править ]

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

Заметки [ править ]

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

Ссылки [ править ]

  • Бездек, Андраш (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 3-540-71132-5.
  • Матушек, Иржи (2002). Лекции по дискретной геометрии . Берлин: Springer. ISBN 0-387-95374-4.
  • Владимир Болтянский , Хорст Мартини , Петру С. Солтан (1997). Экскурсии в комбинаторную геометрию . Springer. ISBN 3-540-61341-2.CS1 maint: несколько имен: список авторов ( ссылка )