12.5.3. СВОЙСТВА АЛГОРИТМА 12.2

Суммируем свойства, которыми обладает аппроксимация, осуществляемая на основе допущений на отклонения, использованные в процедуре COLLINEAR и на шаге 8 алгоритма 12.2.

Утверждение 12.4. Если на шаге 9 процедуры COLLINEAR ненормированное расстояние до прямой сравнивается лишь с фиксированным пороговым значением То и если угол со между двумя прямыми (шаг 8 алгоритма 12.2) меньше, чем где — максимальная длина прямых то максимальное расстояние до прямой меньше, чем

Доказательство. В основе доказательства лежит ряд тригонометрических соотношений. Объекты, используемые при доказательстве, определены на рис. 12.7.

Рис. 12.7. Иллюстрация к доказательству утверждения 12.4

Отметим, что с прямыми и можно оперировать совершенно одинаково, т. е. в качестве прямой можно использовать как так и и т. д., в качестве используется Поскольку новая ошибка определяется отрезком то

Поскольку — треугольник, угол меньше или равен углу

Равенство углов и со наступает в случае, когда они оба равны нулю. Следовательно,

Поскольку

По определению Кроме того, Следовательно

Оценка, вводимая утверждением 12.4, несколько завышена из-за усиления неравенств в процессе доказательства. Хотя нами было показано, что алгоритм 12.2 обеспечивает построение аппроксимирующего многоугольника, расположенного вблизи от аппроксимируемых точек (и также непрерывного), мы не показали, что число сегментов, входящих в аппроксимацию, близко к минимальному. Если допустить, что экспериментальные точки получены в результате квантования некоторой выпуклой кривой, то неравенства, используемые в доказательстве утверждения 12.4, становятся менее свободными и удается показать, что число вершин построенного многоугольника близко к минимальному. Однако, поскольку при решении прикладных задач редко удается иметь дело лишь с выпуклыми кривыми, здесь не будем приводить это доказательство.