Kinetic and dynamic data structures for convex hulls and upper envelopes

Giora Alexandron, Haim Kaplan and Micha Sharir
Computational Geometry
Volume 36, Issue 2 , February 2007, Pages 144-158
http://dx.doi.org/10.1016/j.comgeo.2006.01.002

WADS2005論文のジャーナル版．
計算幾何ではdynamic data structure (動的データ構造) だけでなく，kinetic data structure (運動データ構造) の研究もさかんである．
ここで，dynamic data structureとは，考えているデータに変更がある場合を想定したデータ構造で，その変更にすばやく対応できるとよい．そのような変更は例えば点の挿入や削除といった「離散的」なものである．
一方，kinetic data structureでは，考えているデータが動く場合を想定したデータ構造で，その動きに応じてデータ構造の変更ができるとよい．そのような動きは点がある直線に沿って一定速度で動くような「連続的」なものである．
この論文では平面点集合の凸包を保持するデータ構造を議論している．
ただし，各点の座標は記述複雑さ (description complexity) が定数である時間の関数であり，
新たに点が挿入されたり，削除されたり，また，点の軌道が突然変更されるといったことも起こる．
(状況はかなり複雑…)
このような問題に対して，効率的な乱択データ構造を提案している．Treapとか使っている．