The question speaks for itself. It is required to prove that given a set of 2-d points, the pair of points farthest from each other must lie on the convex hull.
问问题
1149 次
2 回答
4
如果存在一条穿过它的线，并且您的点集中的所有点都在该线的同一侧，则点A位于凸包上。对于一组中相距最远的两个点A和B，您可以证明这适用于通过A和B垂直于A和B的线。
于 2013-08-14T14:48:53.060 回答
0
在上面的答案中添加更多细节。
权利要求 1：具有最小 y 坐标的点 (P) 将始终位于一组 N 个点的凸包上。
证明：让我们假设具有最小 y 坐标的点（P）严格位于凸包内。那么凸包上就会存在一个点（Q），使得 Qy < Py，从而与该点 P 具有最小 y 坐标的假设相矛盾。
权利要求 2：当且仅当存在一条通过它的线且该点集合中的所有点都在该线的同一侧时，点 A 位于凸包上。
证明：（仅当条件）考虑具有最小y坐标的点P。根据权利要求 1，点P位于凸包上，并且通过P的平行于 x 轴的线满足集合 S 的所有其他点位于其上方的标准。现在对于凸包上的任何其他点（P' ），我们可以旋转坐标轴，使 P' 具有最小 y 坐标。
（如果条件）设点 P 使得存在一条线（L），集合中的所有点都在一侧。旋转坐标轴，使L的斜率变为零，从而使 P 成为 y 坐标最小的点。现在使用权利要求 1 来证明它确实是凸包上的一个点。
现在可以利用权利要求 2来证明最远的对确实位于前面的答案中提到的凸包上。
于 2016-03-18T00:55:48.557 回答