細分割法によるファイバー近似の時間計算量に関する一考察
A Note on the Time Complexity of Using Subdivision Methods for the Approximation of Fibers
暗黙的に定義された幾何（関数のファイバー）を直交木で表現する際の構築時間計算量を解析し、特定条件下で密なボクセル格子走査より漸近的に優れ、出力感応的でハウスドルフ測度・次元と関連することを示した。
著者: Michael M. Bilevich, Dan Halperin
分類: cs.CG, cs.RO
原文アブストラクト
Subdivision methods such as quadtrees, octrees, and higher-dimensional orthrees are standard practice in different domains of computer science. We can use these methods to represent given geometries, such as curves, meshes, or surfaces. This representation is achieved by splitting some bounding voxel recursively while further splitting only sub-voxels that intersect with the given geometry. It is fairly known that subdivision methods are more efficient than traversing a fine-grained voxel grid. In this short note, we propose another outlook on analyzing the construction time complexity of orthrees to represent implicitly defined geometries that are fibers (preimages) of some function. This complexity is indeed asymptotically better than traversing dense voxel grids, under certain conditions, which we specify in the note. In fact, the complexity is output sensitive, and is closely related to the Hausdorff measure and Hausdorff dimension of the resulting geometry.
