Барицентрическое подразделение

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

Это имя также используется в топологии для аналогичной операции с комплексами ячеек. Результат топологически эквивалентен результату геометрической операции, но части имеют произвольную форму и размер. Это пример правила конечного подразделения.

Обе операции имеют ряд приложений в математике и в геометрическом моделировании, особенно когда некоторые функции или форма должна быть аппроксимирована кусочно, например сплайном .

• 1 Барицентрическое подразделение симплекса
• 2 Барицентрическое подразделение выпуклого многогранника
• 3 Барицентрическое подразделение в топологии
• 4 Приложения
• 5 Повторяющееся барицентрическое подразделение
• 6 Относительное барицентрическое подразделение
• 7 Связанные понятия
  • 7.1 Ложное барицентрическое подразделение
  • 7.2 Симплициальные множества
  • 7.3 Теория графов
• 8 Примечания
• 9 См. Также

Барицентрическое подразделение 2-симплекса или треугольника

Барицентрическое подразделение (далее BCS) $n\; \{\backslash \; displaystyle\; n\}$-мерное симплекс $S\; \{\backslash \; displaystyle\; S\}$состоит из (n + 1)! $n\; \{\backslash \; displaystyle\; n\}$-мерных симплексов. Каждый кусок с вершинами $v\; 0,\; v\; 1,\dots ,\; vn\; \{\backslash \; displaystyle\; v\_\; \{0\},\; v\_\; \{1\},\; \backslash \; dots,\; v\_\; \{n\}\}$может быть связан с перестановка $p\; 0,\; p\; 1,\dots ,\; pn\; \{\backslash \; displaystyle\; p\_\; \{0\},\; p\_\; \{1\},\; \backslash \; dots,\; p\_\; \{n\}\}$вершин $S\; \{\backslash \; displaystyle\; S\}$, таким образом, что каждая вершина $vi\; \{\backslash \; displaystyle\; v\_\; \{i\}\}$является барицентром точек $p\; 0,\; p\; 1,\dots ,\; pi\; \{\backslash \; displaystyle\; p\_\; \{0\},\; p\_\; \{1\},\; \backslash \; dots,\; p\_\; \{i\}\}$.

4 стадии барицентрического подразделения

В частности, BCS одной точки (0-мерный симплекс) состоит из самой этой точки. BCS линейного сегмента (1-симплекс) $S\; \{\backslash \; displaystyle\; S\}$состоит из двух меньших сегментов, каждый из которых соединяет одну конечную точку (0-мерную грань) $S\; \{\backslash \; displaystyle\; S\}$до середины самого $S\; \{\backslash \; displaystyle\; S\}$(одномерное лицо).

BCS треугольника $S\; \{\backslash \; displaystyle\; S\}$делит его на шесть треугольников; каждая часть имеет одну вершину $v\; 2\; \{\backslash \; displaystyle\; v\_\; \{2\}\}$в барицентре $S\; \{\backslash \; displaystyle\; S\}$, еще одну $v\; 1\; \{\backslash \; displaystyle\; v\_\; \{1\}\}$в средней точке некоторой стороны, а последний $v\; 0\; \{\backslash \; displaystyle\; v\_\; \{0\}\}$на одной из исходных вершины.

BCS тетраэдра $S\; \{\backslash \; displaystyle\; S\}$делит его на 24 тетраэдра; каждая часть имеет одну вершину в центре $S\; \{\backslash \; displaystyle\; S\}$, одну на некоторой грани, одну вдоль некоторого края и последнюю вершину в некоторой вершине $S\; \{\backslash \; displaystyle\; S\}$.

Важной особенностью BCS является тот факт, что максимальный диаметр $n\; \{\backslash \; displaystyle\; n\}$-мерного симплекса сжимается по крайней мере в $nn\; +\; 1\; \{\; \backslash \; displaystyle\; \{\backslash \; frac\; \{n\}\; \{n\; +\; 1\}\}\}$.

Другой способ определения BCS симплекса $S\; \{\backslash \; displaystyle\; S\}$- связать каждую часть с последовательностью $F\; 0,\; F\; 1,\dots ,\; F\; n\; \{\backslash \; displaystyle\; F\_\; \{0\},\; F\_\; \{1\},\; \backslash \; dots,\; F\_\; \{n\}\}$из граней из $S\; \{\backslash \; displaystyle\; S\}$с увеличивающимися размерами, так что $F\; i\; \{\backslash \; displaystyle\; F\_\; \{i\}\}$- это фасет из $F\; i\; +\; 1\; \{\backslash \; displaystyle\; F\_\; \{i\; +\; 1\}\}$для $i\; \{\backslash \; displaystyle\; i\}$от 0 до $n\; -\; 1\; \{\backslash \; displaystyle\; n-1\}$. Тогда каждая вершина $vi\; \{\backslash \; displaystyle\; v\_\; \{i\}\}$соответствующей части является барицентром лица $F\; i\; \{\backslash \; displaystyle\; F\_\; \{i\}\}$.

Это альтернативное определение может быть расширен до BCS произвольного $n\; \{\backslash \; displaystyle\; n\}$-мерного выпуклого многогранника на ряд $n\; \{\backslash \; displaystyle\; n\}$-симплексов. Таким образом, BCS пятиугольника $P\; \{\backslash \; displaystyle\; P\}$, например, имеет 10 треугольников: каждый треугольник связан с тремя элементами $F\; 0,\; F\; 1,\; F\; 2\; \{\backslash \; displaystyle\; F\_\; \{0\},\; F\_\; \{1\},\; F\_\; \{2\}\}$из $P\; \{\backslash \; displaystyle\; P\}$- соответственно, угол $P\; \{\backslash \; displaystyle\; P\}$, сторона $P\; \{\backslash \; displaystyle\; P\}$, примыкающая к этому углу, и $P\; \{\backslash \; displaystyle\; P\}$сам.

Подобным образом BCS куба состоит из 48 тетраэдров, каждый из которых связан с последовательностью $F\; 0,\; F\; 1,\; F\; 2,\; F\; 3\; \{\backslash \; displaystyle\; F\_\; \{0\; \},\; F\_\; \{1\},\; F\_\; \{2\},\; F\_\; \{3\}\}$вложенных элементов - вершина, ребро, грань и весь куб. Обратите внимание, что существует 8 вариантов для $F\; 0\; \{\backslash \; displaystyle\; F\_\; \{0\}\}$, 3 для $F\; 1\; \{\backslash \; displaystyle\; F\_\; \{1\}\}$(задано $F\; 0\; \{\backslash \; displaystyle\; F\_\; \{0\}\}$) и 2 для $F\; 2\; \{\backslash \; displaystyle\; F\_\; \{2\}\}$(при $F\; 0,\; F\; 1\; \{\backslash \; displaystyle\; F\_\; \{0\},\; F\_\; \{1\}\}$).

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

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

В топологической версии BCS каждая ячейка заменяется набором резиновых симплексов, также склеенных своими гранями и, возможно, деформированных. Процедура: (1) выбрать для каждой ячейки карту деформации , которая преобразует ее в геометрический выпуклый многогранник, сохраняя его инцидентность и топологические связи; (2) выполнить геометрическую БКШ на этом многограннике; а затем (3) сопоставьте полученное подразделение с исходными ячейками.

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

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

При аппроксимации математической функции или поверхности сплайном точность аппроксимации обычно определяется размером детали - чем больше детали, тем больше ошибка. Таким образом, часто бывает необходимо разделить большие части на более мелкие, чтобы достичь заданной точности.

Теоретически для этой цели можно использовать BCS, поскольку он обладает тем свойством, что самое длинное ребро любого куска меньше самого длинного ребра исходного многогранника на коэффициент меньше $n\; /\; (\; п\; +\; 1)\; \{\backslash \; Displaystyle\; п\; /\; (п\; +\; 1)\}$. Следовательно, применяя BCS достаточно много раз, можно сделать самую большую кромку сколь угодно малой.

Однако на практике BCS не подходит для этой цели. Во-первых, каждое приложение после первого умножает количество симплексов на $(n\; +\; 1)!\; \{\backslash \; Displaystyle\; (п\; +\; 1)!\}$. BCS также умножает степень каждой исходной вершины на $n!\; \{\backslash \; displaystyle\; n!\}$, а степень каждого ребра равна $(n\; -\; 1)!\; \{\backslash \; Displaystyle\; (п-1)!\}$. Более того, BCS разделит все симплексы, даже те, которые уже достаточно малы. Наконец, каждая стадия BCS также делает симплексы не только меньше, но и «тоньше», то есть имеет тенденцию к увеличению их соотношения сторон (отношения между самым длинным и самым коротким краем). По всем этим причинам на практике редко применяют более одного раунда BCS, и вместо этого используются другие схемы разделения.

Для симплициальных комплексов $L\; \subset \; K\; \{\backslash \; displaystyle\; L\; \backslash \; subset\; K\}$определяется относительное барицентрическое подразделение $K\; \ast \; \{\; \backslash \; displaystyle\; K\; ^\; \{*\}\}$из $K\; \{\backslash \; displaystyle\; K\}$по модулю $L\; \{\backslash \; displaystyle\; L\}$, который состоит из этих симплексы с вершинами $v\; 0\dots \; vk\; B\; (S\; 1\; \prime )\dots \; B\; (S\; l\; \prime )\; \{\backslash \; displaystyle\; v\_\; \{0\}\; \backslash \; dots\; v\_\; \{k\}\; B\; (S\; \text{'}\_\; \{1\})\; \backslash \; dots\; B\; (S\; \text{'}\_\; \{l\})\}$связанный с последовательностью правильных граней $L\; \{\backslash \; displaystyle\; L\}$и барицентров $В\; (S\; i\; \text{'})\; \{\backslash \; displaystyle\; B\; (S\text{'}\; \_\; \{i\})\}$симплексов в $K\; \setminus \; L\; \{\backslash \; displaystyle\; K\; \backslash \; setminus\; L\}$.

Очевидно, $L\; \{\backslash \; displaystyle\; L\}$остается подкомплексом $K\; \ast \; \{\backslash \; displaystyle\; K\; ^\; \{*\}\}$. Только симплексы за пределами $L\; \{\backslash \; displaystyle\; L\}$сжимаются.

Ложное барицентрическое подразделение

Иногда термин «барицентрическое подразделение» неправильно используется для любого подразделения многогранника $P\; \{\backslash \; displaystyle\; P\}$на симплексы, у которых одна вершина находится в центре тяжести $P\; \{\backslash \; displaystyle\; P\}$, а противоположный фасет на границе $P\; \{\backslash \; displaystyle\; P\}$. Хотя это свойство справедливо для истинного барицентрического подразделения, оно также верно и для других подразделений, которые не являются BCS.

Например, если сделать прямой разрез от центра тяжести треугольника до каждого из трех его углов, получится разделение на три треугольника. Обобщая эту идею, мы получаем схему для подразделения $n\; \{\backslash \; displaystyle\; n\}$-мерного симплекса на $n\; +\; 1\; \{\backslash \; displaystyle\; n\; +\; 1\}$симплексов.. Однако это подразделение не является BCS.

Симплициальные множества

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

Теория графов

Термин барицентрическое деление также используется в теории графов (Barycentric_Subdivision (теория графов) ).

1. ^ Мункрес, Джеймс Р.: Элементы алгебраической топологии
2. ^Гиблин, П.Дж.: Графы, поверхности и гомологии
3. ^Гёрсс, П.Г.; Jardine, JF (1999), Simplicial Homotopy Theory, Progress in Mathematics, 174, Basel, Boston, Berlin: Birkhäuser, ISBN 978-3-7643-6064-1, стр. 182

• Аполлоническая сеть
• Комплекс ячеек
• Метод конечных элементов
• Генерация сетки
• Многогранник
• Сплайн