The complexity of subdivision for diameter-distance tests
The complexity of subdivision for diameter-distance tests
复制标题
直径-距离测试细分的复杂性
DOI：
10.1016/j.jsc.2019.06.004
复制
发表时间：
2020
影响因子：
0.7
通讯作者：
Tsigaridas, Elias
中科院分区：
文献类型：
--
作者：
Burr, Michael;Gao, Shuhong;Tsigaridas, Elias
我们提出了一个一般框架，用于分析基于细分的算法的复杂性，其测试是基于区域的大小和它们的距离，某些集（往往品种）固有的问题正在研究中。我们称这种检验为直径-距离检验。我们说明，直径距离测试是常见的文献证明，许多区间算术为基础的测试，事实上，直径距离测试。对于这类算法，我们提供了两个非自适应边界的复杂性，基于分离的界限，以及自适应的界限，通过应用连续摊销的框架。使用这种结构，我们提供了第一个复杂性分析的算法由Plantinga和Vegeter逼近真实的隐式曲线和曲面。我们提出了自适应和非adaptivea priorest-worst-case边界上的复杂性，该算法的子区域的数量方面的建设和建设的比特复杂性。最后，我们构造超曲面族来证明我们的界是紧的。
We present a general framework for analyzing the complexity of subdivision-based algorithms whose tests are based on the sizes of regions and their distance to certain sets (often varieties) intrinsic to the problem under study. We call such tests diameter-distance tests. We illustrate that diameter-distance tests are common in the literature by proving that many interval arithmetic-based tests are, in fact, diameter-distance tests. For this class of algorithms, we provide both non-adaptive bounds for the complexity, based on separation bounds, as well as adaptive bounds, by applying the framework of continuous amortization.Using this structure, we provide the first complexity analysis for the algorithm by Plantinga and Vegeter for approximating real implicit curves and surfaces. We present both adaptive and non-adaptivea prioriworst-case bounds on the complexity of this algorithm both in terms of the number of subregions constructed and in terms of the bit complexity for the construction. Finally, we construct families of hypersurfaces to prove that our bounds are tight.