Триангуляция Делоне многомерных поверхностей и ее аппроксимационные свойства

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

1.    Триангуляция Делоне графика липшицевой функции

Рассмотрим некоторую n-мерную поверхность F в пространстве Rn+1, заданную графиком функции xn+1 = f (x1, ...,xn), x E D C Rn. В настоящей статье под k-мерным симплексом S в Rn мы понимаем выпуклую оболочку к + 1 точек pi,i = 0,..., k < n таких, что векторы p1 -p0, p2 -p0, ..., pk -p0 линейно независимы. Определим отображение проекции п : F ^ D, n(xi, ...,Хп+1) = (xi, ...,xn).

Множество точек вида (x 1 , ...,x _n , 0) E R ⁿ⁺¹ обозначим через П . Пусть P i , i = 1,...,N — некоторый набор точек P i E R ⁿ⁺¹ , лежащих на поверхности F , и таких, что любой симплекс в вершинах из P i является невырожденным. Обозначим через P i⁰ = n(P i ) проекцию точки P i в область D . Будем рассматривать триангуляцию поверхности F n -мерными симплексами, построенными на множестве P _i . Здесь под триангуляцией поверхности мы понимаем такой набор T n -мерных симплексов S ₁ , ..., S _m , что:

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

Из всех триангуляций множества точек поверхности F мы будем выделять триангуляции, удовлетворяющие условию, аналогичному условию Делоне для плоских областей (см. [1; 2]). Дадим соответствующие определения.

Определение 1. Пусть S — некоторый n -мерный симплекс в R ⁿ⁺¹ . Описанным шаром F(S ) для S мы назовем (n + 1) -мерный шар, содержащий симплекс и имеющий минимально возможное значение радиуса.

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

Определение 3. Будем говорить, что для двух n -мерных симплексов, пересекающихся по общей (n — 1) -мерной грани, выполнено условие пустоты шара, если описанный шар одного симплекса не содержит внутри себя вершин другого симплекса.

Следует отметить, что в [3] рассмотрен случай, когда вместо шара используется произвольное выпуклое множество.

Теорема 1. Пусть поверхность F задана над выпуклой областью D ⊂ R ⁿ . Триангуляция этой поверхности, для которой любая пара симплексов, пересекающихся по общей (n — 1) -мерной грани, удовлетворяет условию пустоты шара, является триангуляцией Делоне.

Доказательство. Рассмотрим некоторую триангуляцию множества точек P _i , обладающую свойством, указанным в теореме. Для двух соседних симплексов S ⁰ , S ⁰⁰ данной триангуляции построим гиперплоскость П , проходящую через пересечение гиперсфер dF(S 0 ) П dF(S 00 ) . Рассмотрим произвольный симплекс S заданной триангуляции и некоторую вершину A произвольного симплекса триангуляции, отличного от S . Построим луч OA и последовательность указанных плоскостей, которые пересекаются этим лучом следующим образом. Первой луч пересекает одну из плоскостей, проходящую через одну из граней симплекса S . Обозначим эту плоскость через П 1 . Эта плоскость также содержит одну из граней соседнего симплекса S ₁ . Далее луч пересекает одну из плоскостей, содержащих грани симплекса S 1 . Обозначим эту плоскость через П 2 . Плоскость П 2 содержит одну из граней соседнего симплекса S 2 . Поступая таким образом, получим последовательность плоскостей П 1 , П 2 ,..., П _L и последовательность симплексов S 1 ,S 2 ,...,S L . Также обозначим через П ± полупространства, определяемые плоскостями П _i , такие, что луч OA при пересечении плоскости П _i выходит из П - и входит в П + . Ясно, что A Е S L . Предположим, что A Е S 2 . Согласно построению плоскостей П _i выполнено: A Е П + . Заметим, что в силу свойств шаров будет иметь место одно из следующих включений:

F(S) П П+ С F(Si) П П+, или

F (S i ) П П + С F(S ) П П + .

Пусть B — вершина симплекса S 1 , не принадлежащая плоскости П 1 . По предположению теоремы B Е F(S ) , но B Е F (S 1 ) . Таким образом, имеет место включение

F(S) П П+ С F(Si) П П+, что делает невозможным принадлежность A Е F(S), так как из условий теоремы должно быть выполнено A Е F(Si)- Аналогично, по индукции, доказывается, что при условии A Е Sk, к = 3, ...,L будет выполнено A Е F(S). Теорема доказана.

2.    Аппроксимационные свойства триангуляции Делоне

Пусть D С R n , n >  1 — область, в которой задана последовательность { P m } конечных наборов точек. Для каждого такого набора рассмотрим его триангуляцию T m .

Для всякого симплекса S ∈ Tm определим величину максимальной его стороны dS . Положим dm = max ds.

S ∈ T m

Мы будем рассматривать такие наборы точек P m и их триангуляции T m , для которых выполнены условия:

d m ^ 0 при m ^ to .                          (1)

V x G D и V s > 0 3 m ₀ G N : V m > m ₀ 3 a G P m такая, что | a — x | < s .      (2)

Второе условие означает, что Pm является ε-сетью при всех достаточно больших m. Рассмотрим некоторую функцию f (x),x G D класса C 1(D). Для всякого натурального m построим кусочно-аффинную функцию fm(x) такую, что fm(a) = f (a), для любой точки a G Pm.

Несложно показать, что при выполнении условий (1) и (2) последовательность f _m (x) равномерно сходится к функции f(x) на каждом компактном подмножестве K ⊂ D . В данном параграфе мы изучаем возможности триангуляции Делоне для аппроксимации градиента функции f (x) градиентом f _m (x) . Начнем со случая плоской области. В работе [4] было доказано следующее утверждение.

Утверждение 1. Пусть задана последовательность Tm триангуляций плоской области D ⊂ R2, для которой выполнено условие (1). Для треугольника S обозначим через ϕS величину максимального его острого угла. Тогда, если величина dS max---

SeT m tg v s

^ 0 при m ^ то ,

то для любой компактно вложенной подобласти U b D и произвольной функции f G C2(D) выполнено mmax max ^f (x)  V/mixi ^ 0.

S ∈ T _m ,T ⊂ U x ∈ S

Попытаемся оценить величину из утверждения 1 через радиус описанной около треугольника окружности. Будем рассматривать два случая.

• 1)    Рассматриваемый треугольник остроугольный. Тогда ϕ S — угол, расположенный

напротив самой длинной стороны d S . Воспользуемся теоремой синусов:

d s cos v s

-------= 2R cos vS < 2R, sin vs поскольку sidS^S = 2R.

• 2)    Рассматриваемый треугольник тупоугольный. Обозначим через ϕ _d угол, находящийся напротив самой длинной стороны. Очевидно, что v d >  п/2 и v d + 2v s >  п. Если V <  п/4 , то | sin v d | < | sin2v S | . Значит,

d s      2d s cos ² v s    2d s

---- = -------- \ ---- = 4R.

tg v s     sin 2v s      sin v d

Если v >  п/4 , то tg dd^ s <  d _s <  2R. Таким образом, результирующая оценка имеет вид:

d

—— < 4R.

tg v s

Откуда получается следующая теорема

Теорема 2. Пусть задана последовательность T _m триангуляций Делоне плоской области D с R ² , для которой выполнено условие (1). Тогда для любой компактно вложенной подобласти U b D выполнено:

$« $& mx^^f^{(x) -V f} m (x)H о.

Для доказательства заметим, что если выполнены условия (1) и (2), то радиус описанной окружности каждого внутреннего треугольника триангуляции Делоне T _m не превосходит ε. Действительно, если это не так, то для некоторого треугольника триангуляции радиус описанной окружности будет больше ε . Поэтому, в силу (2) найдется точка p ∈ P _m , отличная от вершин этого треугольника, с расстоянием от центра его описанной окружности не большим ε . Но это противоречит определению триангуляции Делоне. Таким образом, если последовательность триангуляций Делоне T m такова, что г ^ 0 при m ^ то , то, согласно вышеполученной оценке, получаем требуемое из утверждения 1.

Перейдем к многомерному случаю. Рассмотрим некоторый n -мерный симплекс S с R n . Обозначим через S i (п — 1) -мерную его грань как (п — 1) -мерный симплекс, построенный по точкам p ₀ , ...,p _i- i ,p _{i +}i , ...,p n . Кроме этого, с симплексом S свяжем орто-нормированный базис { e _i ^S } , как результат процесса ортогонализации Грамма — Шмидта векторов {p i — p ₀ } ,i = 1,...,п . Теперь положим

n

P k ^— Р о = ^a Si ee T .

i =1

Причем, не ограничивая общности, можно считать, что a Sk > 0 . Ясно, что a Si = 0 при i > k . Пусть a Sk обозначает площадь проекции грани S l на плоскость n S , натянутую на векторы e ^s ,..., e ^s- i , e ^s ₊i , ...,e S .

Пусть ^ _k обозначает угол между вектором p k — p ₀ и плоскостью, натянутой на векторы e ₁ ,...,e k_{- 1} , k = 2,...,n, ^ 1 = п/2 , а 9 k обозначает угол между гранью S _k и плоскостью П _к . В [4] доказано следующее утверждение.

Утверждение 2. Предположим, что для области D ⊂ Rn, последовательности наборов точек Pm и их триангуляций Tm выполнены условия (1) и (2). Тогда для любой функции f Е C2 (D) и любой компактно вложенной подобласти U b D имеет место неравенство где

S max Umax |V f (x) — V f _m (x) | <  d m X

n

2+vnE i=1

| sin^ i || cos9 i |

= — max max

2 U 1

d ² f (x) ∂x _i ∂x j

Таким образом, для доказательства сходимости градиентов кусочно-линейных функций f _m (x) к градиенту функции f (x) достаточно получить оценку величины

n

X

| sin^ i || cos 9 i | ’

характеризующей геометрию симплекса.

Обозначим через ξ i вектор нормали к грани S i данного симплекса S . Тогда cos 6 i = h ^ i ,e i i . По построению базиса { e i } имеем для некоторых a ik

i ei = ^aik(pk — po).

k =1

Заметим, что в силу геометрических соображений

1 ^a ii = 1           i :       .

| p i - p o | sin V i

^COS i         | S i |        k =1 “^ik         | S i |             sin vM — P o || S i | .

Учитывая, что |h ξ i , p i - p 0 i| совпадает с высотой симплекса, опущенной на основание S i , окончательно получаем

• ¹        = | P i ^— P o \\ ^S i \ = | P i ^— P o |

| sin vi cos gi|         nV             hi    ’ где V — объем симплекса, а hi — его высота, опущенная из вершины pi . Таким образом, для оценки указанной величины необходимо оценить снизу двугранные и плоские углы при вершине p0 . К сожалению, в общем случае не удается это сделать. Тем не менее для остроугольных симплексов в R3 мы доказываем существование необходимой оценки снизу таких углов.

Теорема 3. Пусть Tm, m = 1,2,3,... — последовательность остроугольных триангуляций конечных наборов Pm точек области D ⊂ R3, для которых выполнены условия (1) и (2). Тогда для функций f (x),x Е D класса C2(D) и компактно вложенной подобласти U b D выполнено sup sup |Vf (x) —^fm(x^\^ 0

S∈T,S⊂U x∈S при m → ∞.

Предварительно докажем вспомогательную лемму.

Лемма 1. Пусть заданы три числа 0 < A i <  п/2 + 6, где 0 <  6 <  п/2. Если A i + A 2 + A 3 >  п, то хотя бы два из этих чисел не меньше, чем A _o = 2 (^п — 6) .

Доказательство. Предположим противное, то есть некоторые из двух данных чисел меньше, чем λ ₀ . Тогда для их суммы имеем

Г A i < 2A o + 2 + 6 = п, i =1

что противоречит условию леммы.

Полагая δ = 0 и, учитывая, что сумма углов плоского и сферического треугольников не меньше π , получаем следствие.

Следствие. Для остроугольного тетраэдра справедливы утверждения:

• 1.    В любой вершине найдутся два двугранных угла не меньших π/4 .

• 2.    На любой грани найдутся два плоских угла не меньших π/4 .

Таким образом, найдется такая вершина тетраэдра, при которой имеются два двугранных и два плоских угла не меньшие, чем π/4 . Тогда, если это вершина p 0 , то

| p i - p 0 | _≤    1   _{=2 .}

h i         sin ^{2 π} ₄

Справедливость теоремы теперь следует из оценки (3).