Изменения

== Общие определения(R^d) ==

'''Гиперплоскостью'''(англ. ''hyperplane'') в $\mathbb{R}^d$ называется его подпространство размерности $\mathbb{R}^{d - 1}$.

'''Конфигурацией'''(англ. ''arrangement'') $\mathcal{A}(\mathcal{H})$ называется разбиение $\mathbb{R}^d$ в связные открытые(топологически) ячейки области размерностей $0, 1 \dots d $ множеством $\mathcal{H}$ гиперплоскостей в $ \mathbb{R}^d$.

'''Ячейкой'''(англ. ''cell'') размерности $d$ в $\mathcal{A}(\mathcal{H})$ называется максимальная связная область в $R^d$, не пересекаемая ни одной гиперплоскостью в $\mathcal{H}$. <br>

{{TODO| t=БИДА<br>В случае ограниченных гиперплоскостей, сложно обобщить на ограниченные гиперплоскостиячейками соответствующих размерностей также считаются точки, спросить у Ковалёва}}отрезки (лучи), грани и прочие вплоть до размерности $k - 1$, $i$-мерные объекты, ограничивающие их.

'''Вершина'''(англ. ''vertex'') — ячейка размерности 0. <br>'''Ребро'''(англ. ''edge'') — ячейка размерности 1. <br>'''Грань'''(англ. ''face'') — ячейка размерности 2. <br>'''Сторона'''(англ. ''facet'') — ячейка размерности d-1.

В общем случае, не обязательно требовать, чтобы $\mathcal{S}$ было множеством гиперплоскостей. Накладывая некоторые ограничения на поверхности({{TODO| t=возможно, лучше употребить термин «гиперповерхности», но в англ. литературе это ''surfaces''}})гиперповерхности, можно также добиться корректных конфигураций.

К примеру, в $\mathbb{R}^2$ вместо линий(гиперплоскости в $\mathbb{R}^2$) можно брать монотонные по x(то есть каждая параллельная оси y линия пересекает её не более, чем в 1 точке) Жордановы дуги(англ. ''x-monotonic Jordan arcs''), причём такие что максимально количество взаимопересечений каждой пары дуг такого множества — заранее фиксированная константа. Засчёт этого ограничения отсеиваются такие пары дуг как, например, $y = \sin(x)$ и $y = \cos(x)$. А вот пару дуг $y = \cos(x)$ и $y = x^2$ можно взять.

== Плоскость(R^2) ==

| [[Файл:cell2.png | 320x200 px | frame | Цветами выделены ячейки размерности 2. Жёлтая и зелёная ячейки не ограничены, синяя красная {{- --}} ограничена.]]

Если $k_2 = k_1 + 1$ и $c_1$ ограничивает $c_2$, то $c_1$ — '''подъячейка'''(англ. ''subcell'') $c_2$, а $c_2$ — '''надячейканадъячейка'''(англ. ''supercell'') $c_1$. <br>Если $c_1$ — подъячейка или надъячейка для $c_2$, то говорят что они '''смежны'''(англ. ''incident'').

'''Граф смежности'''(англ. ''incidence graph'') конфигурации $\mathcal{A}(\mathcal{S})$ — граф, в котором множество вершин состоит из всех ячеек(в том числе и ячейки размерности -1 и d+1), а ребро между вершинами существует если ячейки, им соответствующие, смежны. Для конфигурации $n$ гиперплоскостей в пространстве $\mathbb{R}^n$ оценкой на количество вершин является $O(n^d)$.

'''Скелетом'''(англ. ''skeleton'') называется множество всех вершин и рёбер в конфигурации. Естественным образом он представляется в виде графа.Он позволяет пройтись по всей конфигурации.({{TODO|t=вроде больше ничего полезного}}).

=== РСДС(R^2) ===Заметим, что на плоскости можно выделить определённый порядок обхода рёбер и позже использовать эту информацию. Граф смежности же не учитывает порядок рёбер и направление. Для того, чтобы поддерживать этот порядок, используется '''рёберный список двойной связности''', '''РСДС'''(англ. ''doubly-connecned edge list'', ''DCEL'').

Для удобства каждое ребро разбивается на два ориентированных '''полуребра'''(''half-edges''). Каждое полуребро принадлежит только одной грани — той, которая окажется слева если идти по направлению полуребра(т.е. при обходе грани против часовой стрелки).

# Список граней содержит данные о грани(например, номер) и указатель на произвольное полуребро, принадлежащее ей.# Список полурёбер содержит данные о полуребре, его близнеце(''twin edge'') — противоположном направленному полуребру(оно не всегда существует, если его нет, будем хранить null), следующем(''next'') и предыдущем(''previous'') полуребру в порядке обхода грани, указатели на вершины начала(''origin'') и конца(''destination'') и соответствующую ему грань.

== Алгоритмы построения Применения == * Планирование движения роботов (''motion planning'')*: К примеру, с помощью конфигураций решается задача о движении робота, имеющего форму полигона(не обязательно выпуклого) и умеющего поворачиваться, на плоскости с полигональными препятствиями.* Задача о треугольнике минимальной площади(''minimum area triangle'')*: Дано $n$ точек в $\mathcal{R}^d$. С помощью конфигураций можно за $O(n^d)$ найти симплекс минимального объема (симплекс на плоскости — треугольник).