Изменения
→Задача
Упрощение полигональной цепи {{---}} процесс, позволяющий уменьшить число точек полилинии.
==Задача==
Дана некоторая полилиния, заданная последовательностью точек <tex> a_1, a_2, ..., a_n</tex>, и некоторое <tex>\varepsilon</tex>. Требуется найти цепь <tex> a_1, a_i, a_j, ..., a_n </tex>, являющейся подпоследовательностью исходной, для которой верно, что для всех <tex>k</tex>, таких что <tex> i < k < j:</tex> <tex>\rho(a_k, Segment(a_i, a_j)) \le \varepsilon</tex> для любых соседних <tex>i</tex> и <tex>j</tex>.
Существует также альтернативная задача, в которой вместо <tex>\varepsilon</tex> задано число <tex>k</tex> вершин в итоговой цепи, требуется составить цепь <tex> a_1, a_i, a_j, ..., a_n </tex> заданной длины таким образом, что максимально необходимое <tex>\varepsilon</tex> для условия <tex> \rho(a_k, Segment(a_i, a_j)) \le \varepsilon</tex> было минимально.
