Алгоритм Киркпатрика

Построение выпуклой оболочки методом «разделяй и властвуй» — алгоритм построения выпуклой оболочки.

Связанные понятия

Конфигурация прямых (или разбиение плоскости прямыми) — это разбиение плоскости, образованное набором прямых.

Простой многоугольник — это фигура, состоящая из непересекающихся отрезков («сторон»), соединённых попарно с образованием замкнутого пути. Если стороны пересекаются, многоугольник не является простым. Часто слово «простой» опускается из вышеприведённого определения.

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

Подробнее: Алгоритмы построения выпуклой оболочки

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

В вычислительной геометрии известна задача об определении принадлежности точки многоугольнику. На плоскости даны многоугольник и точка. Требуется решить вопрос о принадлежности точки многоугольнику.

Подробнее: Задача о принадлежности точки многоугольнику

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

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

Обобщённый многоугольник — это структура инцидентности, предложенная Жаком Титсом в 1959 году. Обобщённые n-угольники вмещают в качестве частных случаев проективные плоскости (обобщённые треугольники, n=3) и обобщённые четырёхугольники (n=4). Многие обобщённые многоугольники получаются из групп типа Ли, но существуют некоторые экзотические обобщённые многоугольники, которые таким способом не получаются. Обобщённые многоугольники, удовлетворяющие условию, известному как свойство Муфанга, полностью...

Квазитриангуляция — структура разбиения плоскости, обладающая свойствами триангуляции Делоне, но вершинами которой служат не точки, а произвольно наклонённые отрезки. Строго говоря, это разбиение не является триангуляцией в геометрическом смысле, то есть разбиением плоскости на треугольные грани, но является триангуляцией в топологическом смысле.

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

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

Почти многоугольник — это геометрия инцидентности, предложенная Эрнестом Е. Шультом и Артуром Янушкой в 1980. Шульт и Янушка показали связь между так называемыми тетраэдрально замкнутыми системами прямых в евклидовых пространствах и классом геометрий точка/прямая, которые они назвали почти многоугольниками. Эти структуры обобщают нотацию обобщённых многоугольников, поскольку любой обобщённый 2n-угольник является почти 2n-угольником определённого вида. Почти многоугольники интенсивно изучались, а...

Теорема об упаковке кругов (известная также как теорема Кёбе — Андреева — Тёрстона) описывает возможные варианты касания окружностей, не имеющих общих внутренних точек. Граф пересечений (иногда называемый графом касаний) упаковки кругов — это граф, вершины которого соответствуют кругам, а рёбра — точкам касания. Если упаковка кругов осуществляется на плоскости (или, что эквивалентно, на сфере), то их граф пересечений называется графом монет. Графы монет всегда связны, просты и планарны. Теорема упаковки...

Геометрия инцидентности — раздел классической геометрии, изучающий структуры инцидентности.

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

Эта страница содержит список правильных многомерных многогранников (политопов) и правильных cоединений этих многогранников в евклидовом, сферическом и гиперболическом пространствах разных размерностей.

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

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

Конфигурация вершины задаётся как последовательность чисел, представляющих число сторон граней, окружающих вершину. Обозначение «a.b.c» обозначает вершину с тремя гранями около неё и эти грани имеют a, b и c сторон (рёбер).

В геометрии плосконосый двуклиноид или сиамский додекаэдр — это трёхмерный выпуклый многогранник с двенадцатью правильными треугольниками в качестве граней. Многогранник не является правильным, поскольку в некоторых вершинах сходятся четыре грани, а в остальных — пять граней. Многогранник является двенадцатигранником, одним из восьми дельтаэдров (выпуклых многогранников с гранями в виде правильных треугольников) и одним из 92 многогранников Джонсона (неоднородные выпуклые многогранники с правильными...

Апейрогон (от др.-греч. ἄπειρος — бесконечный или безграничный и др.-греч. γωνία — угол) — обобщённый многоугольник со счётно-бесконечным числом сторон.

В геометрии образование звёздчатой формы — процесс расширения многоугольника (в пространстве размерности 2), или многогранника в пространствах размерности 3 и выше с образованием новой фигуры.

Декера́кт — десятимерный гиперкуб, аналог куба в десятимерном пространстве. Определяется как выпуклая оболочка 1024 точек. Он может быть назван по символу Шлефли {4,38}, будучи составленным из 3 9-кубов вокруг каждой 8-грани. Слово «декеракт» — портманто из слов «тессеракт» и греч. δεκα — десять измерений. Также он может быть назван как икосаксеннон или икоса-10-топ от греч. εικοσα — двадцать и топ — 10-политоп. Политоп, двойственный к 10-кубу, называется 10-ортоплекс (или 10-гипероктаэдр).

Диаграмма Вороного конечного множества точек S на плоскости представляет такое разбиение плоскости, при котором каждая область этого разбиения образует множество точек, более близких к одному из элементов множества S, чем к любому другому элементу множества.

В математике абстрактный многогранник, неформально говоря, это структура, которая учитывает только комбинаторные свойства традиционных многогранников и игнорирует много других их свойств, таких как углы, длины рёбер и т. д. При этом не требуется наличие какого-либо содержащего многогранник пространства, такого как евклидово пространство. Абстрактная формулировка реализует комбинаторные свойства как частично упорядоченное множество («посет»).

Пра́вильный многоуго́льник — это выпуклый многоугольник, у которого все стороны между собой равны и все углы между смежными сторонами равны.

Нотация Конвея для многогранников, разработанная Конвеем и продвигаемая Хартом, используется для описания многогранников, опираясь на затравочный (т.е. используемый для создания других) многогранник, модифицируемый различными префикс-операциями.

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

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

Вычислительная геометрия — раздел информатики, в котором рассматриваются алгоритмы для решения геометрических задач.

Внеописанный четырёхугольник — это выпуклый четырёхугольник, продолжения всех четырёх сторон которого являются касательными к окружности (вне четырёхугольника). Окружность называется вневписанной. Центр вневписанной окружности лежит на пересечении шести биссектрис. Это биссектрисы двух внутренних углов противоположных углов четырёхугольника, биссектрисы внешних углов двух других вершин, и биссектрисы внешних углов в точках пересечения продолжений противоположных сторон (смотрите рисунок справа, указанные...

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

Правильные четырёхмерные многогранники являются четырёхмерными аналогами правильных многогранников в трёхмерном пространстве и правильных многоугольников на плоскости.

Подробнее: Правильный четырёхмерный многогранник

Четырнадцатиугольник или тетрадекагон — это многоугольник с четырнадцатью сторонами.

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

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

Интегральное исчисление — раздел математического анализа, в котором изучаются понятия интеграла, его свойства и методы вычислений.

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

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

Универсальное множество точек порядка n — это множество S точек евклидовой плоскости со свойством, что любой планарный граф с n вершинами имеет рисунок с прямыми рёбрами, в котором все вершины располагаются в точках множества S.

В геометрии 4-мерный многогранник — это многогранник в четырёхмерном пространстве. Многогранник является связанной замкнутой фигурой, состоящей из многогранных элементов меньшей размерности — вершин, рёбер, граней (многоугольников) и ячеек (3-мерных многогранников). Каждая грань принадлежит ровно двум ячейкам.

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

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

В геометрии построение Витхоффа, или конструкция Витхоффа — это метод построения однородных многогранников или мозаик на плоскости. Метод назван по имени математика В. А. Витхоффа. Часто метод построения Витхоффа называют калейдоскопным построением.

Задача со счастливым концом — утверждение о том, что любое множество из пяти точек на плоскости в общем положении имеет подмножество из четырёх точек, которые являются вершинами выпуклого четырёхугольника.

Плоскость Фано — конечная проективная плоскость порядка 2, имеющая наименьшее возможное число точек и прямых (7 точек и 7 прямых), с тремя точками на каждой прямой и с тремя прямыми, проходящими через каждую точку. Названа по имени итальянского математика Джино Фано.

Конфигурация Кремоны — Ричмонда — конфигурация из 15 прямых и 15 точек, по три точки, лежащих на каждой прямой, и через каждую точку проходят 3 прямых, при этом конфигурация не содержит треугольников. Конфигурацию изучали Кремона (Cremona 1877) и Ричмонд (Richmond 1900). Конфигурация является обобщённым четырёхугольником с параметрами (2,2). Граф Леви конфигурации — это граф Татта — Коксетера.

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

Четырёхугольник (греч. τετραγωνον) — это геометрическая фигура (многоугольник), состоящая из четырёх точек (вершин), никакие три из которых не лежат на одной прямой, и четырёх отрезков (сторон), последовательно соединяющих эти точки. Различают выпуклые и невыпуклые четырёхугольники, невыпуклый четырёхугольник может быть самопересекающимся (см. рис.). Четырёхугольник без самопересечений называется простым, часто под термином «четырёхугольник» имеется в виду только простые четырёхугольники.

Теорема о 9 точках на кубической кривой — теорема алгебраической геометрии, которая гласит, что...

а б в г д е ё ж з и й к л м н о п р с т у ф х ц ч ш щ э ю я