Is it possible to find an upper and lower tangent line to a convex hull in $log(n)$ time where $n$ is number of points on a convex hull? I have just done it in linear time where I checked for upper tangent line if orientation of $S,i,i+1$ is greater than zero (anti-clockwise) and if orientation of $S,i,i-1$ is greater than zero as well. Same for lower tangent line where I checked if its clockwise orientation. $S$ is a point from where I want my tangent line to go, $i$ is a point on a convex hull and $i-1$,$i+1$ are its neighbours. This is the only source I've found so far [Link]$_1$ and I really can't understand the algorithm for now.
$\begingroup$
$\endgroup$
8
-
$\begingroup$ Are the vertices of the hull given? Are they given in order, for example counterclockwise? If so, then You can consider the slopes that they form with the given point as an array that is sorted and has been rotated. then you can use binary search to search for maximum and minimum in this way. $\endgroup$– plopApr 13, 2021 at 13:56
-
$\begingroup$ Maybe a bit precise question. How would I know which point is above or below one point on a convex hull. If I have mid point, mid - 1 and mid + 1. I tried using orientation but I'm clueless now. $\endgroup$– ExzoneApr 13, 2021 at 14:03
-
$\begingroup$ What do you mean by a "point is above or below on point"? $\endgroup$– plopApr 13, 2021 at 15:39
-
$\begingroup$ By doing binary search I will start with first index that will initially be zero, last index that will be points.size()-1 and midpoint. If midpoint is not my tangent point I have to check whether midpoint+1 is above or below, if its above I will put my starting point as a midpoint and calculate another midpoint as so on as a binary search works. But the problem is the cyclic calculation of whether midpoint+1 is above or below. $\endgroup$– ExzoneApr 13, 2021 at 18:21
-
1$\begingroup$ If the given point is $p$ and the vertex of the convex hull is $p_i$ we needs to be looking at the slope $s_i$ of the ray $\vec{pp_i}$. Assuming your input is a list $[p_1,p_2,\ldots,p_n]$ of the vertices of the hull in counterclockwise order, you run the algorithm above, but using the $s_i$ as value to compare. You want to find the indexes $i_\min$ and $i_\max$ that give you the maximum and minimum slopes. $\endgroup$– plopApr 13, 2021 at 18:32
|
Show 3 more comments
1 Answer
$\begingroup$
$\endgroup$
Let's assume that the convex polygon $P$ is defined as an ordered list $(p_0,p_1,...,p_{n-1})$ of points, and for each such point $p \in P$ we are able in $O(1)$ time to find a previous point $Prev(p)$ and a next point $Next(p)$ according to this order, taking into account that:
$$Prev(p_0)=p_{n-1}$$ $$Next(p_{n-1})=p_0$$
The binary search over this list is very similar to a binary search over a regular array - on each step you have a $p_{left}$ point, a $p_{right}$ point and a $p_{mid}$ point. You check some condition on the $p_{mid}$ point and then choose a $[p_{left},p_{mid}]$ interval or a $[p_{mid},p_{right}]$ interval for the next step.
The condition you want to check is the following one. In order for the $p_{mid}$ point to be the tangential point for all lines going through the query point $S$, both neighbors of the $p_{mid}$ point must be on the same side of the line, connecting the point $S$ and the $p_{mid}$. You'll have to choose, which side of this line is right and which side is wrong - this will define, which tangent line you'll get (upper or lower). So, if the previous point $Prev(p_{mid})$ is on the wrong side, then you choose the left interval. Similarly, if the next point $Next(p_{mid})$ is on the wrong side of this line, then you choose the right interval for the next step. This algorithm will stop on one of two tangential points if and only if the point $S$ is located outside of the polygon $P$.
The algorithm doesn't need any preprocessing of the convex polygon $P$ and nevertheless finds tangential points for any query point, located outside of the polygon, in $O(\log n)$ time.
