Связанные понятия
Конфигурация прямых (или разбиение плоскости прямыми) — это разбиение плоскости, образованное набором прямых.
Число пересечений графа — наименьшее число элементов в представлении данного графа как графа пересечений конечных множеств, или, эквивалентно, наименьшее число клик, необходимых для покрытия всех рёбер графа.
Восходящее планарное представление направленного ациклического графа — это вложение графа в евклидово пространство, в котором рёбра представлены как непересекающиеся монотонно возрастающие кривые. То есть, кривая, представляющая любое ребро, должна иметь свойство, что любая горизонтальная прямая пересекает его максимум в одной точке, и никакие два ребра не могут пересекаться, разве что на концах. В этом смысле это идеальный случай для послойного рисования графа, стиля представления графа, в котором...
Задача о наименьшей окружности или задача о минимальном покрывающем круге — задача о вычислении наименьшей окружности, содержащей все заданные точки из множества на евклидовой плоскости.
Простой многоугольник — это фигура, состоящая из непересекающихся отрезков («сторон»), соединённых попарно с образованием замкнутого пути. Если стороны пересекаются, многоугольник не является простым. Часто слово «простой» опускается из вышеприведённого определения.
Многоугольник Петри для правильного многогранника в размерности n — это пространственный многоугольник, такой что любые (n-1) последовательных ребра (но не n) принадлежат одной (n-1)-мерной грани.
Диаграмма Вороного конечного множества точек S на плоскости представляет такое разбиение плоскости, при котором каждая область этого разбиения образует множество точек, более близких к одному из элементов множества S, чем к любому другому элементу множества.
Комбинаторика многогранников — это область математики, принадлежащая комбинаторике и комбинаторной геометрии и изучающая вопросы подсчёта и описания граней выпуклых многогранников.
В математике
абстрактный многогранник , неформально говоря, это структура, которая учитывает только комбинаторные свойства традиционных многогранников и игнорирует много других их свойств, таких как углы, длины рёбер и т. д. При этом не требуется наличие какого-либо содержащего многогранник пространства, такого как евклидово пространство. Абстрактная формулировка реализует комбинаторные свойства как частично упорядоченное множество («посет»).
Пра́вильный двадцатичетырёхъяче́йник, или просто двадцатичетырёхъяче́йник, или икоситетрахор (от др.-греч. εἴκοσι — «двадцать», τέτταρες — «четыре» и χώρος — «место, пространство»), — один из правильных многоячейников в четырёхмерном пространстве.
Подробнее: Двадцатичетырёхъячейник
В математике конечное правило подразделения — это рекурсивный способ деления многоугольника и других двумерных фигур на всё меньшие и меньшие части. Правила подразделения в этом смысле является обобщением фракталов. Вместо повторения одного и того же узора снова и снова здесь имеются небольшие изменения на каждом шаге, что позволяет получить более богатые структуры, сохраняя при этом поддержку элегантного стиля фракталов . Правила подразделения используются в архитектуре, биологии и информатике...
Косое разбиение графа — это разбиение его вершин на два подмножества, такое что порождённый подграф, образованный одним из его подмножеств вершин является несвязным, а другой порождённый подграф, образованный другим подмножеством является дополнением несвязного графа. Косые разбиения играют важную роль в теории совершенных графов.
Вложение Татта или барицентричное вложение простого вершинно 3-связного планарного графа — вложение без пересечений с рёбрами в виде отрезков с дополнительными свойствами, что внешняя грань имеет выпуклый многоугольник в качестве границы и что каждая внутренняя вершина является геометрическим центром соседей. Если внешний многоугольник фиксирован, это условие на внутренние вершины определяет их положения однозначно как решение системы линейных уравнений. Решение уравнений даёт планарное вложение...
Прямолинейный скелет — это метод представления многоугольника его топологическим скелетом. Прямолинейный скелет подобен в некотором роде срединным осям, но отличается тем, что скелет состоит из отрезков, в то время как срединные оси многоугольника могут включать параболические кривые.
Теорема об упаковке кругов (известная также как теорема Кёбе — Андреева — Тёрстона) описывает возможные варианты касания окружностей, не имеющих общих внутренних точек. Граф пересечений (иногда называемый графом касаний) упаковки кругов — это граф, вершины которого соответствуют кругам, а рёбра — точкам касания. Если упаковка кругов осуществляется на плоскости (или, что эквивалентно, на сфере), то их граф пересечений называется графом монет. Графы монет всегда связны, просты и планарны. Теорема упаковки...
Кососимметрический граф — это ориентированный граф, который изоморфен своему собственному транспонированному графу, графу, образованному путём обращения всех дуг, с изоморфизмом, который является инволюцией без неподвижных точек. Кососимметрические графы идентичны двойным покрытиям двунаправленных графов.
Задачи упаковки — это класс задач оптимизации в математике, в которых пытаются упаковать объекты в контейнеры. Цель упаковки — либо упаковать отдельный контейнер как можно плотнее, либо упаковать все объекты, использовав как можно меньше контейнеров. Многие из таких задач могут относиться к упаковке предметов в реальной жизни, вопросам складирования и транспортировки. Каждая задача упаковки имеет двойственную задачу о покрытии, в которой спрашивается, как много требуется некоторых предметов, чтобы...
n-Мерная
целочисленная решётка (или кубическая решётка), обозначается Zn, — это решётка в евклидовом пространстве Rn, точки которой являются n-кортежами целых чисел. Двумерная целочисленная решётка называется также квадратной решёткой. Zn является наиболее простым примером решётки корней. Целочисленная решётка является нечётной унимодулярной решёткой.
Правильные четырёхмерные многогранники являются четырёхмерными аналогами правильных многогранников в трёхмерном пространстве и правильных многоугольников на плоскости.
Подробнее: Правильный четырёхмерный многогранник
Одновременное вложение графов — это техника визуализации двух и более различных графов на одном и том же множестве помеченных вершин, при которой избегается пересечения рёбер в каждом из графов. Пересечения между рёбрами разных графов разрешаются, не разрешается только пересечение рёбер одного графа.
Статья описывает упаковку
кругов на поверхностях. Для связанной статьи об упаковке кругов с заданным графом пересечений, см. статью «Теорема об упаковке кругов».
Обобщённый многоугольник — это структура инцидентности, предложенная Жаком Титсом в 1959 году. Обобщённые n-угольники вмещают в качестве частных случаев проективные плоскости (обобщённые треугольники, n=3) и обобщённые четырёхугольники (n=4). Многие обобщённые многоугольники получаются из групп типа Ли, но существуют некоторые экзотические обобщённые многоугольники, которые таким способом не получаются. Обобщённые многоугольники, удовлетворяющие условию, известному как свойство Муфанга, полностью...
В геометрии 4-мерный многогранник — это многогранник в четырёхмерном пространстве. Многогранник является связанной замкнутой фигурой, состоящей из многогранных элементов меньшей размерности — вершин, рёбер, граней (многоугольников) и ячеек (3-мерных многогранников). Каждая грань принадлежит ровно двум ячейкам.
Планарное накрытие конечного графа G — это конечный накрывающий граф графа G, являющийся планарным графом. Любой граф, который может быть вложен в проективную плоскость, имеет планарное накрытие. Нерешённая гипотеза Сэйи Негами утверждает, что только эти графы и имеют планарные накрытия.
Треугольник Шварца представляется тремя рациональными числами (p q r), каждое из которых задаёт угол в вершине. Значение n/d означает, что угол в вершине треугольника равен d/n развёрнутого угла. 2 означает прямоугольный треугольник. Если эти числа целые, треугольник называется треугольником Мёбиуса и он соответствует мозаике без перекрытий, а группа симметрии называется группой треугольника. На сфере имеется 3 треугольника Мёбиуса и ещё одно однопараметрическое семейство. На плоскости имеется три...
Геометрический остов (англ. geometric spanner) или t-остовной граф, или t-остов первоначально был введён как взвешенный граф на множестве точек в качестве вершин, для которого существует t-путь между любой парой вершин для фиксированного параметра t. t-Путь определяется как путь в графе с весом, не превосходящим в t раз пространственное расстояние между конечными точками. Параметр t называется коэффициентом растяжения остова.
Итеративное сжатие — это алгоритмическая техника разработки фиксированно-параметрически разрешимых алгоритмов, в которой один элемент (такой как вершина графа) добавляется в задачу на каждом шаге и используется небольшое решение задачи перед добавлением элемента, чтобы найти небольшое решение задачи после добавления.
Вписанно-описанный четырёхугольник — это выпуклый четырёхугольник, который имеет как вписанную окружность, так и описанную окружность. Из определения следует, что вписанно-описанные четырёхугольники имеют все свойства как описанных четырёхугольников, так и вписанных четырёхугольников. Другие названия этих четырёхугольников: хордо-касающийся четырёхугольник и бицентрический четырёхугольник. Их также называют двух-окружностными четырёхугольниками.
Если дано топологическое пространство и группа действий на нём, образы отдельной точки под действием группы действий образуют орбиты действий. Фундаментальная область — это подмножество пространства, которое содержит в точности по одной точке из каждой орбиты. Она даёт геометрическую реализацию абстрактного множества представителей орбит.
Подробнее: Фундаментальная область
Задача о самом широком пути — это задача нахождения пути между двумя выбранными вершинами во взвешенном графе, максимизирующего вес минимального по весу ребра графа (если рассматривать вес ребра как ширину дороги, то задача стоит в выборе самой широкой дороги, связывающей две вершины). Задача о самом широком пути известна также как задача об узком месте или задача о пути с максимальной пропускной способностью. Можно приспособить алгоритмы кратчайшего пути для вычисления пропускной способности путём...
Пифагорова мозаика (замощение двумя квадратами) — замощение евклидовой плоскости квадратами двух различных размеров, в которой каждый квадрат касается четырёх квадратов другого размера своими четырьмя сторонами. Исходя из этой мозаики, можно доказать (наглядно) теорему Пифагора, за что мозаика и получила название пифагоровой. Мозаика часто используется в качестве узора для кафельного пола. В этом контексте мозаика известна также как узор классов.
Задача о гамильтоновом пути и задача о гамильтоновом цикле — это задачи определения, существует ли гамильтонов путь (путь в неориентированном или ориентированном графе, который проходит все вершины графа ровно один раз) или гамильтонов цикл в заданном графе (ориентированном или неориентированном). Обе задачи NP-полны.
В геометрии пространственный многоугольник — это многоугольник, вершины которого не компланарны. Пространственные многоугольники должны иметь по меньшей мере 4 вершины. Внутренняя поверхность таких многоугольников однозначно не определяется.
В вычислительной геометрии известна задача об определении принадлежности точки многоугольнику. На плоскости даны многоугольник и точка. Требуется решить вопрос о принадлежности точки многоугольнику.
Подробнее: Задача о принадлежности точки многоугольнику
Теорема Галлаи – Хассе – Роя – Витавера — это вид двойственности между раскрасками вершин заданного неориентированного графа и ориентациями его рёбер. Теорема утверждает, что минимальное число красок, необходимых для правильной раскраски любого графа G, на единицу больше длины максимального пути в ориентации графа G, в которой эта длина пути минимальна. В ориентации, в которых путь максимальной длины имеет минимальную длину, всегда входит по меньшей мере одна ациклическая ориентация.
Однородная мозаика может существовать как на евклидовой плоскости, так и на гиперболической плоскости. Однородные мозаики связаны с конечными однородными многогранниками, которые можно считать однородными замощениями сферы.
Ребро в геометрии — отрезок, соединяющий две вершины многоугольника или многогранника (в размерностях 3 и выше). В многоугольниках ребро является отрезком, лежащим на границе и чаще называется стороной многоугольника. В трёхмерных многогранниках и в многогранниках большей размерности ребро — это отрезок, общий для двух граней. Отрезок, соединяющий две вершины и проходящий через внутренние или внешние точки, ребром не является и называется диагональю.
Обобщённый четырёхугольник — это структура инцидентности, главное свойство которой — отсутствие треугольников (однако структура содержит много четырёхугольников). Обобщённый четырёхугольник является по определению полярным пространством ранга два. Обобщённые четырёхугольники являются обобщёнными многоугольниками с n = 4 и почти 2n-угольниками с n = 2. Они являются также в точности частичными геометриями pg(s,t,α) с α = 1.
В теории графов
хорошо покрытый граф (иногда встречается название хорошо укрытый граф) — это неориентированный граф, в котором любое минимальное вершинное покрытие имеет один и тот же размер (как и любое другое минимальное вершинное покрытие). Хорошо покрытые графы определил и изучал Пламмер.
Парке́т или замощение — разбиение плоскости многоугольниками (или пространства многогранниками) без пробелов и перекрытий.
Треуго́льный парке́т (треугольный паркета́ж) или треугольная мозаика — это замощение плоскости равными правильными треугольниками, расположенными сторона к стороне.
В гиперболической геометрии
гиперболический треугольник является треугольником на гиперболической плоскости. Он состоит из трёх отрезков, называемых сторонами или рёбрами, и трёх точек, называемых углами или вершинами.
Диэдральная группа (группа диэдра) — группа симметрии правильного многоугольника, включающая как вращения, так и осевые симметрии. Диэдральные группы являются простейшими примерами конечных групп и играют важную роль в теории групп, геометрии и химии. Хорошо известно и совершенно тривиально проверяется, что группа, образованная двумя инволюциями с конечным числом элементов в области определения является диэдральной группой.
Выпуклым многоугольником называется
многоугольник , все точки которого лежат по одну сторону от любой прямой, проходящей через две его соседние вершины.
Отношение инцидентности — это бинарное отношение между двумя различными типами объектов. Это включает понятия, которые можно выразить такими фразами как «точка лежит на прямой» или «прямая принадлежит плоскости». Наиболее существенное отношение инцидентности — между точкой P и прямой l, которое записывается как P I l. Если P I l, пара (P, l) называется флагом. В разговорном языке существует много выражений, описывающих отношение инцидентности (например, прямая проходит через точку, точка лежит на...
Подробнее: Инцидентность (геометрия)
Десятиуго́льник (правильный десятиугольник — декагон) — многоугольник с десятью углами и десятью сторонами.