An intersection-sensitive algorithm for snap rounding

Mark de Berg, Dan Halperin and Mark Overmars
Computational Geometry
Volume 36, Issue 3, April 2007, Pages 159-165
http://dx.doi.org/10.1016/j.comgeo.2006.03.002

任意精度のアレンジメントを有限精度のアレンジメントに変換することをsnap roundingと呼んで，平面上の直線分に対してsnap roundした後のアレンジメントが望ましい性質を持つように変換するためのアルゴリズムを議論．
まず，「望ましい性質」にどのようなものがあるか定める必要があり，ここでは「Fixed-precision representation」，「Geometric similarity」，「Topological similarity」，「Non-redundancy」を考えている．
詳細は論文参照．
で，これら4つの性質を満たすような変換像をO((n+I)log n)時間で構成するアルゴリズムを与えている．
ここで，nは線分の数，Iはアレンジメントにおける交点数であり，既存アルゴリズムの計算量を改善している．

Snap rounding の研究自体がまだ乏しいようで，やるべきことはたくさんあるという印象を受けた．