提出用细分方法高效构建隐式几何纤维的构造时间复杂度分析。
A Note on the Time Complexity of Using Subdivision Methods for the Approximation of Fibers
- 从豪斯多夫测度角度分析细分方法构造时间复杂度
- 在特定条件下，复杂度优于密集体素网格遍历
- 适合研究几何表示与计算效率的学者参考
四叉树、八叉树及高维正交树等细分方法在计算机科学多个领域广泛应用，可用于表示曲线、网格或曲面等几何体。该表示通过递归分割包围体素，仅对与给定几何相交的子体素继续细分。众所周知，细分方法比遍历精细体素网格更高效。本文从新视角分析用于表示隐式定义几何（即函数预像）的正交树构造时间复杂度。在特定条件下，其复杂度渐近优于密集体素网格遍历；事实上，复杂度为输出敏感，并与结果几何体的豪斯多夫测度和豪斯多夫维数密切相关。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。