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, становятся менее свободными и удается показать, что число вершин построенного многоугольника близко к минимальному. Однако, поскольку при решении прикладных задач редко удается иметь дело лишь с выпуклыми кривыми, здесь не будем приводить это доказательство.
