Delaunay triangulations approximate anchor hulls

Tamal K. Dey, Joachim Giesen and Samrat Goswami
Computational Geometry
Volume 36, Issue 2 , February 2007, Pages 131-143
http://dx.doi.org/10.1016/j.comgeo.2006.01.001

SODA2005論文のジャーナル版．
まず，「anchor hull」という概念を導入している．
空間R^2におけるコンパクトな連結集合Σで，その境界∂Σが滑らかなものを考える．
Σの点xに対して，A(x)を∂Σの点でxに最も近いもの全体の集合とする．
ここで，xのanchor hullをA(x)の凸包と定義する．
いろいろな仮定が成立するとき，Delaunay三角形分割の構造がanchor hullの構造と非常に似ていることが証明される．
これを用いた形状マッチングへの応用も述べられている．なかなか面白い．