快速赫尔最坏情况的说明 [英] Quick Hull Worst case explanation

问题描述

这是最坏的情况下为快速船体??以及我们如何知道这是最坏的情况下 我很困惑与快包算法。事实上，我理解，运行行列式找到一个三角形的面积，并且如果该区域为正，则该点是上的极值点的左边。 而做这件事情递归，将有O（n）的效率建造船体。 然后，我不理解的是，如何在效率有时会提及O（nlogn）和）（N ^ 2）？对于这些情况下，这种效率证明又如何呢？ 请，如果有人可以通过一些具体的例子帮助;这将是很大的帮助。

What is the worst case for quick hull?? And how we can know that it is the worst case I am confused with quick hull algorithm. Actually, I understood, that running determinant to find the area of a triangle, and if the area is positive, then the point is on the left of the extreme points. And doing this thing recursively, will have O(n) efficiency for constructing a hull. Then I don't understood, that how to efficiency is sometimes mentioned O(nlogn) and )(n^2)? for which cases this efficiency turns out and how? please if someone can help by some particular example; that would be great help.

推荐答案

QuickHull是一种快速的算法，因为在你的的步骤之一消除了一堆点的这个谎言一个三角形内。该步骤QuickHull是：

QuickHull is a fast algorithm because in one of the steps you eliminate a bunch of points that lie inside a triangle. The steps for QuickHull are:

1. 您选择最右边和最左边的点，并跟踪它们之间的行
2. 您找到点说，就是从你的行
最远
3. 您绘制这三点之间的三角
4. 您消除您的三角形内部点，回到步骤2。

这是当你点随机放置在飞机上的情况，但也有情况下，当点被严重分散，你不能排除任何人在任何给定的一步。其中一个这种情况下，是当点是在圆的边界

This is the case when your points are placed randomly on the plane, but there are cases when the points are badly distributed and you can't eliminate any of them in any given step. One of this cases is when the points are in the border of a circle:

正如你所看到的，遇到这种情况时，在算法的第4步以上可以消除无分的。这就是为什么在最坏的情况下QuickHull是为O（n ^ 2）。

As you can see, when this happens, in step 4 of the algorithm above you eliminate no points at all. This is why in the worst case QuickHull is O(n^2).

这篇关于快速赫尔最坏情况的说明的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！