确定在O(log n)时间内点是否位于凸包中 [英] Determine whether a point lies in a convex hull in O(log n) time

问题描述

我研究了几种算法来确定点是否在凸包中，但是我似乎找不到能在O(logn)时间内完成技巧的算法，也无法自己提出设a []为包含凸包的顶点的数组，无论如何我都可以对该数组进行预处理，以使其有可能在O(logn)时间检查新点是否位于凸包内.

I've researched several algorithms for determining whether a point lies in a convex hull, but I can't seem to find any algorithm which can do the trick in O(logn) time, nor can I come up with one myself.Let a[] be an array containing the vertices of the convex hull, can I pre-process this array in anyway, to make it possible to check if a new point lies inside the convex hull in O(logn) time.

推荐答案

看起来可以.

1. 将a[]中的顶点按相对于其中一个顶点的极角排序(称为A). O(N log N)，就像凸包计算一样.
2. 读取点，确定其极角. O(1)
3. 找到两个相邻顶点，其中一个顶点的极角应小于步骤2中的点，而另一个顶点的角应较大(B和C). O(log N)，二进制搜索
4. 然后是简单的几何:在A，B，C的点之间绘制三角形，并检查步骤2中的点是否位于其中. O(1)

1. Sort vertices in a[] by polar angle relative to one of vertices (call it A). O(N log N), like convex hull computation.
2. Read point, determine its polar angle. O(1)
3. Find two neighbor vertices, one of them should have polar angle less than point from step 2, and other should have angle bigger (B and C). O(log N), binary search
4. Then simple geometry: draw the triangle between points from A, B, C and check if point from step 2 lies inside. O(1)

这篇关于确定在O(log n)时间内点是否位于凸包中的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！