TL;DR
線分をつないだ曲線（折れ線）を、形を保ったまま、より少ない点の折れ線に単純化するアルゴリズム。Urs Ramer が 1972 年に、David Douglas と Thomas Peucker が 1973 年に発表した。
なぜ必要か
地図の線や GPS の軌跡などは点の数が多く、そのままでは描画や保存の負担が大きい。Wikipedia によると、このアルゴリズムは地図の線を単純化する（地図の総描）手法として初期に成功したものの 1 つで、最も正確な結果が得られる代わりに時間がかかる。
仕組み
利用者が許容誤差 ε を決めて、次の手順で点を間引く。
- 始点と終点は残し、その間の点を削除の候補にする
- 始点と終点を結ぶ線分から最も遠い点を探す
- その距離が ε 以下なら、間の点をすべて捨てる。捨てても、結果の誤差は ε を超えない
- ε より遠ければ、その点を残し、「始点からその点まで」と「その点から終点まで」の 2 つの区間で同じ処理を再帰的に繰り返す
計算量は、分割が常に端に偏る最悪の場合で O(n²)、ほぼ均等に分かれる場合で Ω(n log n) である。
注意点
単純化が粗すぎると、結果の線が自分自身と交差することがある。この問題を避けるための変種のアルゴリズムが作られている。