反对数的上限是多少？

对映体对是一对顶点的x，y，使得我们可以得出平行切线凸包通过顶点的x和y 1h而不需相交H.反对数的上限是多少？

我发现很多算法来找到这样对，但我不能够推导出可能配对数的上限。

有人可以给n个数的凸包的上界并证明它吗？

2014-09-25 CodeLover

参见Preparata＆Shamos的计算几何，定理4.18。当您围绕多边形旋转切线时，它会依次触碰每个顶点（N次移动）;同时，反对顶点也在轮廓上前进（N个移动，没有回溯）。当没有边平行时，有N对。对于平行边缘（最多N/2对），反对数不超过3N/2。 – 2014-09-25 21:19:01

查看计算几何by Preparata & Shamos，定理4.18。当您旋转多边形周围的切线时，它会依次触及每个顶点（N移动）;当您旋转多边形周围的切线时，它会依次触及每个顶点（N移动）。同时，对角顶点也在轮廓上前进（N移动，没有回溯）。

当没有平行边缘时，确切地有N对（一边没有移动与另一边移动一致）。当有平行边缘时，可能会有额外的一对，总数为N + P，其中P是平行边缘对的数量，最多为N/2。

2014-09-25 21:20:57

我无法找到该书。你能否提一下这样的证明，这将是非常有用的。谢谢 – CodeLover 2014-09-26 04:11:21

不，文字太长了。但原则是显而易见的。 – 2014-09-26 07:31:13

请上传图片或文字，你不需要输入。 – CodeLover 2014-09-26 08:05:45

回答