9
As the polygon is convex, it is simple! Two vertices is consecutive if all other vertices are located just on one side of the line that goes through these two points. This means that the cross product of this vector with the others all have the same sign (all negative or all positive). For example, if those two points are called $P_1$ and $P_2$, you should ...
5
Given that the polygon is convex, its centroid $C$ is in its interior. Test the gradients of the lines $CV$ for each vertex $V$. This gives a linear time test.
4
An alternative to OmG's answer (which is great) would be to sort your points into an ordered array where you can find any points neighbors by looking at the points on either side. This method would be very good if you need to work with the same polygon for many calculations as most work is done upfront but afterwards the cost of determining if two points are ...
2
Any line can be represented in the form $\{p + xv : x \in \mathbb{R}\}$, or in other words, by a point $p$ on the line and a vector $v$ parallel to the line. Without loss of generality, we can take $v$ to have norm 1 (if not, replace $v$ with $v/\|v\|_2$). Also, if we ignore lines where the $z$-component of $v$ is zero, then without loss of generality we ...
1
Is this a valid approach to construct a Priority Search Tree in O(n) time, from a set of points sorted on the y-coordinates?
No.
In revision 8, it constructs a valid search tree on $y$.
The check in step 2 will almost always yield not satisfied.
The best I thought up, ignoring non-unique priority values:
Proceed the complete binary search tree ...
Only top voted, non community-wiki answers of a minimum length are eligible
