О сохранении ориентации треугольника при квазиизометрическом отображении

DOI:

Широко применяемый в компьютерном моделировании способ построения расчетных сеток — получение сетки из некоторой исходной посредством подходящего отображения; при этом должно быть обеспечено сохранение некоторых свойств. В случае если исходной сеткой является триангуляция некоторой области в R ² , такими свойствами могут быть: невырожденность, ориентация, отношение смежности составляющих сетку треугольников. Исследованию условий сохранения подобных свойств посвящено большое количество работ, в которых применяется математический аппарат различной степени сложности. Классическим результатом здесь является теорема Альфорса о сохранении ориентации треугольника при квазиконформном отображении [1]. Из недавних работ укажем [2; 4–9]. Предлагаемый в данной работе признак можно рассматривать как обобщение теоремы Альфорса. Напомним ее формулировку.

Пусть C — плоскость комплексных чисел, D C C — некоторая область, w = / (z) — С 1 -гомеоморфизм на D, сохраняющий ориентацию (|/_ I < IAI). Тогда

^{( I /} I - ^{I /}- 1) ^^{z I}<  M^{w I}<  ^{( I /} I + ^{I /}- 1) ^^z |.

Величина

D y =

I/ , I + I/ - 1 _>1

I/ , I-I/ - 1 "

называется отклонением в точке z. Отображение / называется квазиконформным, если D y ограничено. Отображение / называется К -квазиконформным, если D y <  К .

Теорема 1 ([1, гл. III. D]). Пусть р — некоторое К -квазиконформное отображение конечной плоскости на себя, причем К <  ^/З . Тогда вершины любого равностороннего треугольника отображаются на вершины некоторого треугольника с той же ориентацией.

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

Напомним определение квазиизометрического отображения. Пусть Е — множество в R ” . Отображение / : Е ^ R ” называется квазиизометрическим, если при некоторых положительных числах I <  L выполнено условие

V Е,Е‘ е Е I 1^ ’ — 4I‘) — /(x")I < L I ж’ — х^м\.             (1)

Легко видеть, что если Е — выпуклая область, то отображение, удовлетворяющее условию вида (1), является L/Z-квазиконформным.

• 1.    Предварительные сведения

Для формулировки и доказательства заявленного результата потребуются некоторые сведения из работы [3], где, в частности, предложена характеристика степени невырожденности треугольника и вычислено ее значение для равностороннего треугольника. Приведем необходимые сведения.

Отображение F : I ^ R ” , где I = {1,..., к} — отрезок натуральных чисел, будем называть семейством к точек в R ” или к-точечным семейством. Табличное задание отображения F будем записывать как

F = Р ² ч

I F (1) F(2) '"F (к)/

Пусть / : F(I) ^ R” — некоторое отображение. Композицию / oF определим стандарт- ным образом:

/ oF =

(     1         2             кА t/(F(1))/(F(2)) .../(F(к))/ .

Пусть ст : I ^ I — некоторая перестановка. Композицию

F о т =

(     1         2             кА tF(t(1))F(т(2)) ...FКк))/ будем называть перенумерацией семейства F.

Для к-точечных семейств F , G зададим набор чисел A(F, G) как набор отношений расстояний между одинаково нумерованными парами точек семейств F , G за исключе-0 нием отношений вида :

A(F,G) = { |^F(i)^F(j)| , (м) : 1 <  i< к, |F(OF(j)| + |G(i)G(^)| > 0}

№^G C j ^{) |}

(здесь |... | — евклидова длина отрезка); и определим величину р следующим образом:

P (F,G) =

0, если для всех г, j |F (i)F(j )| = 0 и |G(г)G(j )| = 0; max A(F, G)

log               , иначе                                     ’ min A(F, G)

зафиксировав в качестве основания логарифма некоторое число, большее единицы, и a полагая - = +ro, log(+w) = +ro.

Величина ρ инвариантна относительно ортогональных преобразований простран- ства R” (то есть для ортогональных преобразований О',0" : R” ^ R” имеем р(О о о F,0" о G) = p(F, G)) и является расстоянием между классами ортогонально эквива-

лентных (то есть совмещаемых ортогональными преобразованиями) семейств, представителями которых являются семейства F , G. Далее величину p (F, G) будем называть расстоянием (а также р -расстоянием) между семействами F , G. Если о — некоторая перестановка, то, вообще говоря, p (F о о , G) = p (F, G).

Пусть Ы — некоторое множество к-точечных семейств. Расстояние от к-точечного семейства F до множества Ы определим стандартным образом:

p (F, U ) = inf p(F,U ).

Если множество Ы инвариантно относительно перенумерации (то есть из U ЕЫ следует V o F о о Е Ы ), то p ((F о о ), Ы ) = p (F, Ы ) для любой перестановки о (в работе [3] это утверждение явно не выделено). Везде далее подразумевается, что в соотношениях, содержащих обозначения р и log, основание логарифма, указанного явно, и основание логарифма, подразумеваемого в обозначении ρ согласно определению этой величины, — одно и то же число, большее единицы.

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

Теорема 2 ([3]). Пусть I = {1,..., к} , где к > 2 , и F : I ^ R ” — семейство точек, имеющее хотя бы два различных значения. Пусть / : F(I) ^ R ” — отображение, удовлетворяющее условию вида (1). Тогда

P ^{( F,/ оF} ) < log ^.

Рассмотрим случай трехточечных семейств в R2. Семейство У : {1, 2,3} ^ R2 назовем коллинеарным, если его значения У(1), У(2), У(3) расположены на одной прямой. (В работе [3] такие семейства названы планарными.) Обозначим Т множество коллинеарных семейств. Как показано в [3], вычисление значения р(Х, Т), где X — некоторое трехточечное семейство, сводится к вычислению значений вида p(X , Y) для конечного количества семейств Y Е Р; каждое из этих семейств строится определенным образом на основании семейства X (необходимые построения делаются циркулем и линейкой).

Далее, значения трехточечного семейства — вершины некоторого треугольника; если семейство коллинеарно, то этот треугольник вырожден. Обратно, если вершины треугольника АВС являются значениями семейства X, то они же будут значениями семейств вида X о у для любой перестановки у . Поскольку множество Р , очевидно, ^ -инвариантно, то p (X о у , Р ) = p (X, Р ). На этом основании величину p (X, Р ) будем называть расстоянием от треугольника до множества вырожденных треугольников, и словом треугольник будем обозначать как множество точек, определяемое этим термином в элементарной геометрии, так и трехточечное семейство.

В работе [3] дано явное выражение величины p (X, Р ) через длины а, Ь, с сторон треугольника X:

P(X,Р) = log mHа+Ь, Ь+С, а+С} , с а Ь и показано, что равносторонний треугольник является наиболее удаленным от множества вырожденных треугольников, а именно, доказана следующая теорема.

Теорема 3. Пусть X — трехточечное семейство в R 2 , X (г) = X(j) при г = j . Тогда: 1) p (X, Р ) < log2 ;

• 2)    p (X, Р ) = log 2 тогда и только тогда, когда значения семейства X являются вершинами равностороннего треугольника.

• 2.    Основной результат

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

Уточним используемые далее понятия контура и отображения, сохраняющего ориентацию. Контуром в R ² будем называть замкнутую кривую без самопересечений. Пусть Г — некоторый ориентированный контур. Будем говорить, что отображение / : Г ^ R ² сохраняет ориентацию контура Г, если /(Г) — контур, и этот контур ориентирован одноименно с контуром Г.

Пусть Т = АВС — некоторый треугольник; Г _т — контур, образованный его сторонами. Очевидно, условие одноименности ориентации контуров Г _т и /(Г _т ) еще не обеспечивает одноименность ориентации треугольников АВС и /(А) /(В) /(С).

Сформулируем основной результат.

Теорема 4. Пусть Т = АВС — ориентированный невырожденный треугольник в R2; / : Гт ^ R2 — отображение, удовлетворяющее условию (1) на множестве {А, В, С} и сохраняющее ориентацию контура Гт. Если log ^< р(Т,Р),                                   (2)

то треугольник / (А)/ (В )/(С) ориентирован одноименно с треугольником АВС .

Доказательство. Сначала отметим следующее утверждение.

Лемма . Пусть / : D с R ” ^ R ” —отображение, для которого выполнено условие (1); γ — спрямляемая кривая. Тогда

• ¹    НИ I/ ⁽ Y )| <  ^L • | Y |

( | γ | — длина кривой).

(Доказательство леммы сводится к представлению длины рассматриваемых кривых как предела последовательностей длин правильно вписанных ломаных и оценке длин звеньев этих ломаных согласно соотношению (1).)

Для определенности будем полагать ориентацию контура Г положительной. Обозначим А = /(Л), В ‘ = /(В), С ‘ = / (С ), Т ‘ — треугольник А ' В ‘ С ‘ . Имеем: контур / о Г проходит через точки А ' , В ' , С' и его ориентация положительна. Предположим, что ориентация треугольника Т ' = А ' В ' С ' отрицательна. Геометрически очевидно, что контур / о Г гомотопен контуру вида Г * , который можно описать следующим образом. Из отрицательно ориентированного треугольника АВС' исключается одна сторона. Концы оставшейся двузвенной ломаной, на звеньях которой задана ориентация, определенная ориентацией треугольника, соединяются ориентированной кривой. Ориентация и положение кривой задаются так, чтобы на получившейся замкнутой кривой было задано положительное направление обхода. Доказательство изложим для случая, когда исключаемая сторона есть отрезок [А ,С ' ].

Имеем

|/([А, С ])|>|АВ ' | + |В ' С ' |.                              (3)

Рассмотрим набор величин

|АВ^, |   |В ' С ' |    |АВ^, | + |В ' С ' |

| ав | ’ |вc |’         | Ас |       .                                  ⁽ )

Оценим их. По теореме 2, где полагаем F = Т и / о F = Т ' , имеем р (Т, Т ' ) <

< log J , то есть

* <^                  (5) ' <^ <ь,                    (6) * <^ <^                  (7)

Рассмотрим третью из величин набора (4). Из неравенства треугольника |А^,В^, | + |В ' С ' | >  >  |А^,С ' | и левой части оценки (7) имеем

|АВ' | + |В ' С ' |

|АС |      > .

С другой стороны, из неравенства (8) (в прочтении справа налево) и правой части неравенства леммы, приведенной в начале доказательства,

* • М < |/(Y)| < Ь • |Y| , где полагаем у — двузвенная ломаная АВС, выводим

\А'В 1 + |В ' С ' |

|ЛС|       <^Ь.

Таким образом,

I <

| A’ B'\ + \BC ‘ |

|ЛС|      < ^L

Заметим теперь, что элементы набора (4) численно совпадают со значеними набора А(Т , Т ‘‘ ) для вырожденного треугольника Т ‘‘ = { д ’ J ‘ J ’’} , где C " — точка пересечения прямой A ’ B ‘ и окружности с центром в точке B ‘ радиуса \B ‘ C ‘ \, расположенная правее точки В ‘ . Из неравенств (5), (6), (9) выводим:

р (Т,Т ‘‘ ) < log L/Z.

С другой стороны, поскольку треугольник Т ‘‘ вырожден, то

р (Т,Т ‘‘ ) >  р (Т, Р ).                                  (11)

Из (10), (11) имеем log J >  р (Т, Р ), что противоречит неравенству (2) в условии теоремы.

Случаи другой расстановки наименований значений семейства / о Т рассматриваются аналогично. Теорема доказана.

Из теорем 3 и 4 выводим следующее утверждение.

Следствие 1. Пусть Т = ABC — правильный ориентированный треугольник в R ² ; / : Г _т ^ R ² — отображение, удовлетворяющее условию (1) на множестве {A,B,C } и сохраняющее ориентацию контура Г _т . Если L/1 <  2 , то треугольник / (A) / (B) /(C) ориентирован одноименно с треугольником ABC .

Доказательство. Из неравенств п. 1) и п. 2) в заключении теоремы 3 и неравенства в заключении теоремы 2 выводим:

log ^L<  log 2 = р (Т, Р ).

Откуда по теореме 4 получаем требуемое.