数据结构 - 多边形

Question

直径我需要一个数据structute允许

• addPoint（X，Y）在O（logN）的
• printDiameter（）在O（logN）的

其中N是多边形中当前的点数。
显然，这两点将位于多边形的凸包上。使用反节点对（旋转卡尺）的概念，我们可以发现N个点的直径是O（N）。
This整齐地解释了O（n）解决方案，但它不支持插入点。

Answer 1

A K-d树能做的O（logN）的插入，只要它在某种程度上balanced。对于直径部分，您必须检查每个节点才能找到最远的，所以它应该是O（N）。 另一种解决方案是使用QuadTree，并遍历它以仅获取位于树外部的节点。