An Efficient and Quasi Linear Worst-Case Time Algorithm for Digital Plane Recognition
An Efficient and Quasi Linear Worst-Case Time Algorithm for Digital Plane Recognition
复制标题
一种高效的准线性数字平面识别最坏情况时间算法
DOI：
10.1007/978-3-540-79126-3_31
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
L. Buzer
中科院分区：
文献类型：
--
作者：
E. Charrier;L. Buzer
本文介绍了一种解决数字式朴素飞机识别问题的方法。这个方法是对以前方法的修改.这是唯一一种在最坏情况下保证O（nlogD）时间复杂度的方法，其中（D-1）表示包围点的边界框的大小，并且在实践中非常有效。所提出的方法包括在确定一组ofnpoints在103对应于一块数字朴素超平面迭代在最坏的情况下。每一次迭代都执行一个产品。该方法确定一组106体素是否对应于一片数字平面在十次迭代的平均值，这是五倍小于上限。此外，该方法成功地减少了数字朴素的平面识别问题在2003年的二维凸函数的可行性问题。当边界框中的点集密集时，即当。
This paper introduces a method for the digital naive plane recognition problem. This method is a revision of a previous one. It is the only method which guarantees anO(nlogD) time complexity in the worst-case, where (D− 1) represents the size of a bounding box that encloses the points, and which is very efficient in practice. The presented approach consists in determining if a set ofnpoints in ℤ3corresponds to a piece of digital naive hyperplane initerations in the worst case. Each iteration performsndot products. The method determines whether a set of 106voxels corresponds to a piece of a digital plane in ten iterations in the average which is five times less than the upper bound. In addition, the approach succeeds in reducing the digital naive plane recognition problem in ℤ3to a feasibility problem on a two-dimensional convex function. This method is especially fitted when the set of points is dense in the bounding box, i.e. when.