1679
правок
Изменения
Нет описания правки
К примеру, в $\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) ==
Разрешим ограничивать гиперплоскости — то есть введём лучи и отрезки. Тогда ячейками размерности 0 также считаются точки, ограничивающие их.
=== Пример ===
Возьмём $\mathcal{H} = \{AB, CD, EF, a\}$.
{|align="left"
| [[Файл:cell2.png | 320x200 px | frame | Цветами выделены ячейки размерности 2. Жёлтая и зелёная ячейки не ограничены, синяя - ограничена.]]
| [[Файл:cell1.png | 320x200 px | frame | Взяв множество S с единственным отрезком AB, получим три ячейки размерности 1. Взяв за множество S поочерёдно CD, EF и a, получим остальные ячейки размерности 1.]]
| [[Файл:cell0.png | 320x200 px | frame | Взяв поочерёдно за множество S множества {a, EF}, {a, AB}, {AB, CD, EF}, получим ячейки G, H и I размерности 0. Как было замечено, точки A, B, C, D, E, F — также ячейки размерности 0 как органичивающие отрезки.]]
|}
== Представления конфигураций ==
Пусть $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$, то говорят что они '''смежны'''(англ. ''adjacentincident'').
}}
Иногда удобно вводить ячейку размерности -1 — она является подъячейкой любой ячейки размерности 0, и ячейку размерности d+1 — она является надъячейкой любой ячейки размерности d.
=== Граф смежности ===
'''Граф смежности'''(англ. ''incidence graph'') конфигурации $\mathcal{A}(\mathcal{S})$ — граф, в котором множество вершин состоит из всех ячеек(в том числе и ячейки размерности -1 и d+1), а ребро между вершинами существует если ячейки, им соответствующие, смежны. Для конфигурации $n$ гиперплоскостей в пространстве $\mathbb{R}^n$ оценкой на количество вершин является $O(n^d)$.
== Плоскость(R^2) == Разрешим ограничивать гиперплоскости — то есть введём лучи и отрезки. Тогда ячейками размерности 0 также считаются точки, ограничивающие их. Пример === Примеры ===Возьмём $\mathcal{H} = \{AB, CD, EF, a\}$.
{|align="left"
| [[Файл:cell2sample_graph.png | 320x200 px | frame | Цветами выделены Пример конфигурации. Номерами обозначены ячейки размерности 2. Жёлтая и зелёная ячейки не ограничены, синяя - ограничена.]] | [[Файл:cell1inc_graph.png | 320x200 px | frame | Взяв множество S с единственным отрезком AB, получим три ячейки размерности 1Граф смежности для этой конфигурации. Взяв за множество S поочерёдно CD, EF и a, получим остальные ячейки Ячейка Super — ячейка размерности d+1.]] | [[Файл:cell0.png | 320x200 px | frame | Взяв поочерёдно за множество S множества {a, EF}, {a, AB}, {AB, CD, EF}, получим ячейки G, H и I размерности 0. Как было замечено, точки A, B, C, D, E, F Sub — также ячейки размерности 0 как органичивающие отрезки.-1]]
|}
