Конфигурация — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 34: Строка 34:
 
}}
 
}}
  
== Плоскость(R^2) ==
+
=== Обобщения ===
 +
В общем случае, не обязательно требовать, чтобы $\mathcal{S}$ было множеством гиперплоскостей. Накладывая некоторые на поверхности(возможно, лучше употребить термин «гиперповерхности», но в англ. литературе это ''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$ можно взять.
 +
 
 +
== Представления конфигураций ==
 +
 
 +
{{Определение
 +
|id=subcell
 +
|definition=
 +
Пусть $c_1$ - ячейка размерности $k_1$, а $c_2$ — ячейка размерности $k_2$ в конфигурации $\mathcal{A}(\mathcal{S})$. <br>
 +
Если $k_2 = k_1 + 1$ и $c_1$ ограничивает $c_2$, то $c_1$ — '''подъячейка'''(англ. ''subcell'') $c_2$, а $c_2$ — '''надячейка'''(англ. ''supercell'') $c_1$. <br>
 +
Если $c_1$ — подъячейка или надъячейка для $c_2$, то говорят что они '''смежны'''(англ. ''adjacent'').
 +
}}
 +
 
 +
Иногда удобно вводить ячейку размерности -1 — она является подъячейкой любой ячейки размерности 0, и ячейку размерности d+1 — она является надъячейкой любой ячейки размерности d.
  
На $\mathbb{R}^2$ можно ввести обобщение — вместо линий(гиперплоскости в $\mathbb{R}^2$) можно брать монотонные по x(то есть каждая параллельная оси y линия пересекает её не более, чем в 1 точке) Жордановы дуги, причём такие что максимально количество взаимопересечений каждой пары дуг такого множества — заранее зафиксированная константа. Засчёт этого ограничения отсеиваются такие пары дуг как, например, $y = \sin(x)$ и $y = \cos(x)$. А вот пару дуг $y = \cos(x)$ и $y = x^2$ можно взять.
 
  
Также ячейками размерности 0 считаются точки, ограничивающие эти дуги.
+
== Плоскость(R^2) ==
  
Но для упрощения реализаций алгоритмов мы всё же ограничимся использованием прямых, лучей и отрезков.
+
Разрешим ограничивать гиперплоскости — то есть введём лучи и отрезки. Тогда ячейками размерности 0 также считаются точки, ограничивающие их.
  
 
=== Примеры ===
 
=== Примеры ===
Строка 50: Строка 64:
 
  | [[Файл:cell0.png | 320x200 px | frame | Взяв поочерёдно за множество S множества {a, EF}, {a, AB}, {AB, CD, EF}, получим ячейки G, H и I размерности 0. Как было замечено, точки A, B, C, D, E, F — также ячейки размерности 0 как органичивающие отрезки.]]
 
  | [[Файл:cell0.png | 320x200 px | frame | Взяв поочерёдно за множество S множества {a, EF}, {a, AB}, {AB, CD, EF}, получим ячейки G, H и I размерности 0. Как было замечено, точки A, B, C, D, E, F — также ячейки размерности 0 как органичивающие отрезки.]]
 
|}
 
|}
 +
  
  

Версия 02:10, 4 ноября 2011

<wikitex>

Эта статья находится в разработке!

Общие определения(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}$.

Ячейкой размерности $k$, где $0 \le k < d$ в $\mathcal{A}(\mathcal{H})$ называется максимальная связная область в пересечении гиперплоскостей подмножества $\mathcal{S} \in \mathcal{H}$, которая не пересекается ни одной гиперплоскостью из множества $\mathcal{H} \setminus \mathcal{S}$.

//БИДА, сложно обобщить на ограниченные гиперплоскости.


Определение:
Вершина(англ. vertex) — ячейка размерности 0.

Ребро(англ. edge) — ячейка размерности 1.
Грань(англ. face) — ячейка размерности 2.

Сторона(англ. facet) — ячейка размерности d-1.


Обобщения

В общем случае, не обязательно требовать, чтобы $\mathcal{S}$ было множеством гиперплоскостей. Накладывая некоторые на поверхности(возможно, лучше употребить термин «гиперповерхности», но в англ. литературе это 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$ можно взять.

Представления конфигураций

Определение:
Пусть $c_1$ - ячейка размерности $k_1$, а $c_2$ — ячейка размерности $k_2$ в конфигурации $\mathcal{A}(\mathcal{S})$.

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

Если $c_1$ — подъячейка или надъячейка для $c_2$, то говорят что они смежны(англ. adjacent).


Иногда удобно вводить ячейку размерности -1 — она является подъячейкой любой ячейки размерности 0, и ячейку размерности d+1 — она является надъячейкой любой ячейки размерности d.


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

Разрешим ограничивать гиперплоскости — то есть введём лучи и отрезки. Тогда ячейками размерности 0 также считаются точки, ограничивающие их.

Примеры

Возьмём $\mathcal{H} = \{AB, CD, EF, a\}$.

Цветами выделены ячейки размерности 2. Жёлтая и зелёная ячейки не ограничены, синяя - ограничена.
Взяв множество S с единственным отрезком AB, получим три ячейки размерности 1. Взяв за множество S поочерёдно CD, EF и a, получим остальные ячейки размерности 1.
Взяв поочерёдно за множество S множества {a, EF}, {a, AB}, {AB, CD, EF}, получим ячейки G, H и I размерности 0. Как было замечено, точки A, B, C, D, E, F — также ячейки размерности 0 как органичивающие отрезки.









Источники

  • Goodman J.E., O'Rourke J. Handbook of discrete and computational geometry. p. 537, 2004, 2nd edition.

</wikitex>