Distance-preserving approximations of polygonal paths

Joachim Gudmundsson, Giri Narasimhan and Michiel Smid
Computational Geometry
Volume 36, Issue 3, April 2007, Pages 183-196
http://dx.doi.org/10.1016/j.comgeo.2006.05.002

地図上の道などはコンピュータ内部で折れ線として表現されているが，例えば表示の解像度を下げたときには元々の折れ線を表示するより，それを近似した折れ線を表示するだけで十分であることが多い．
そのため，折れ線の曲がり角をいくつか間引いて，元の折れ線を近似する折れ線を求めるという問題が考えられてきている．(この論文で挙げられている最古の先行研究は1980年代中ごろのIri-Imaiの論文である．)

この論文は2つの問題を考えている．
1つは許容近似誤差が与えられたときに，間引かずに残す曲がり角の数を最小化する問題．もう1つは間引かずに残す曲がり角の数が与えられたときに，近似誤差を最小にする間引き方を与える問題．
誤差は，間引かなかった曲がり角の間の距離が元の折れ線と間引いた後の折れ線の間でどれだけ変化したかという比の最大値で計算する．
これを著者らはdistance-preserving approximationと呼んでいる．

まず前者の問題について，論文はO(n^2)アルゴリズムを与えている (nはだいたい元の折れ線の曲がり角の数) ．
これはグラフを作って，その上での最短パス問題を解くことで実現している．
後者の問題についてはソートと二分探索に基づくO(n^2 log n)時間アルゴリズムを与えている．
また，well-separated pair decompositionに基づく近似アルゴリズムも与えている．面白い．