最大的三角形凸包 [英] Largest triangle in convex hull
问题描述
这个问题已经回答了，但我现在面临的主要问题是在理解的答案之一。
The question has already been answered, but the main problem I am facing is in understanding one of the answers..
从 http://stackoverflow.com/a/1621913/2673063
如何为下面的算法 O（N）？
它规定为 首先分拣点/计算的凸包（在为O（n log n）的时间），如果有必要，我们可以假设我们有凸多边形/船体循环排序它们出现在多边形的顺序之分。调用点1，2，3，...，N。让（可变）点A，B和C，开始为1，2，和3分别（在循环顺序）。我们将移动A，B，C，直到农行是最大面积的三角形。 （我们的想法是类似于旋转卡钳方法，为计算的直径（最远对）时使用。）
It states as By first sorting the points / computing the convex hull (in O(n log n) time) if necessary, we can assume we have the convex polygon/hull with the points cyclically sorted in the order they appear in the polygon. Call the points 1, 2, 3, … , n. Let (variable) points A, B, and C, start as 1, 2, and 3 respectively (in the cyclic order). We will move A, B, C until ABC is the maximum-area triangle. (The idea is similar to the rotating calipers method, as used when computing the diameter (farthest pair).)
使用A和B固定，推进C（例如最初，用A = 1，B = 2，C通过C = 3，C = 4先进，...）只要三角形的面积增加，即只要区（A，B，C）≤区（A，B，C + 1）。这点C将是一个最大化区（ABC）的那些固定A和B（换句话说，该功能区（ABC）是单峰的形式为C的函数。）
With A and B fixed, advance C (e.g. initially, with A=1, B=2, C is advanced through C=3, C=4, …) as long as the area of the triangle increases, i.e., as long as Area(A,B,C) ≤ Area(A,B,C+1). This point C will be the one that maximizes Area(ABC) for those fixed A and B. (In other words, the function Area(ABC) is unimodal as a function of C.)
接着，提前B（不改变A和C）如果该增加的区域。如果是的话，再推进c以上面。话又说回来推进b。如果可能的话，等，这将给出最大面积三角形A为顶点之一。 （该部分达这里应该很容易证明，并简单地分别做这为每个A将得到O（N 2），但上读取。）现在再次推进A中，如果它改善了区域等 虽然这有三个嵌套的循环，注意，B和C始终走向前，而他们最多2n倍推进总（同样，一个进步至多N次），所以整个事情在O（n）时间运行
Next, advance B (without changing A and C) if that increases the area. If so, again advance C as above. Then advance B again if possible, etc. This will give the maximum area triangle with A as one of the vertices. (The part up to here should be easy to prove, and simply doing this separately for each A would give O(n2). But read on.) Now advance A again, if it improves the area, etc. Although this has three "nested" loops, note that B and C always advance "forward", and they advance at most 2n times in total (similarly A advances at most n times), so the whole thing runs in O(n) time.
推荐答案
由于 0的更详细的解释（N）运行。
As the author of the answer that is the subject of the question, I feel obliged to give a more detailed explanation of the O(n) runtime.
首先，只是作为一个例子，这里是从纸的图形，示出了前几个步骤的算法，对于特定样品输入（一个12边形）。首先，我们有A，B，C为连续三个顶点（图中的步骤1），推进ç只要面积增加（步骤2至6），然后提前B，等等。
Firstly, just as an example, here is a figure from the paper, showing the first few steps of the algorithm, for a particular sample input (a 12-gon). First we start with A, B, C as three consecutive vertices (step 1 in the figure), advance C as long as area increases (steps 2 to 6), then advance B, and so on.
用星号在他们之上的三角形是锚定局部最大值，即那些最适合给定A（即，无论是推进C或B会降低区域）。
The triangles with asterisks above them are the "anchored local maxima", i.e., the ones that are best for a given A (i.e., advancing either C or B would decrease the area).
至于运行时是 O（N）：让实际值B的，在的时候，它已经增加了一些条款，而忽略包装各地，是NB，同样对于C是NC。 （换句话说， B = NB％N 和 C = NC％N ）。现在，请注意，
As far as the runtime being O(n): Let the "actual" value of B, in terms of the number of times it's been incremented and ignoring the wrap around, be nB, and similarly for C be nC. (In other words, B = nB % n and C = nC % n.) Now, note that,
-
（B超前A的）无论A的值，我们有一个与乐; NB＆LT;一个+ N
("B is ahead of A") whatever the value of A, we have A ≤ nB < A + n
NB总是增加
所以，作为甲从0到n变化，我们知道，NB介于0和2n个唯一不同：它可以最多2n倍递增。同样NC。这表明，该算法，这是成比例的次数，A，B和C的总数的运行时间被增加，由为O（n）+ O（2n）的+ O（2n）的，这是O（n为界）。
So, as A varies from 0 to n, we know that nB only varies between 0 and 2n: it can be incremented at most 2n times. Similarly nC. This shows that the running time of the algorithm, which is proportional to the total number of times A, B and C are incremented, is bounded by O(n) + O(2n) + O(2n), which is O(n).
这篇关于最大的三角形凸包的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
