0
$\begingroup$

I've been reading T.M. Chan algorithm for convex hull of a 2D polygon, here he says that we can find a support line (tangent line) to a polygon given that this polygon is convex and we have its vertices on CCW order in $O(\log H)$ time with $H$ being the number of vertices on the convex hull of the polygon.

Now, I could take this for granted but I decided to see exactly how, since we had it in class but with time $O(n)$. By looking at the references (Shamos and Preparata book) and a Chazelle article I find myself more confused than happy.

Looked into some other notes about convex hull where Chan's algorithm is simplified into text (which is great because now I can understand the time bound better) but here the part about $O(\log H)$ for tangent lines is took by granted and actually left as an exercise so I decided to try it.

To find lets say just a right tangent line to a polygon $P$ given its vertices $p_0,p_1,\dots,p_n$ in CCW order and a point $q$ that lies outside the boundary of $P$, I think first I need to locate the maximum and minium $y-$oriented points, I can do this in $O(\log n)$ ($n$ points on $CH(P)$), but then I'm stuck in the part where I need to do binary search over the other points of $CH(P)$ to find the tangent line.

Any hints?

Right tangent line from a query point $q$ located outside $P$: find a vertex $p_i$ such that $P$ is contained in the closed half-plane to the left of the oriented line $qp_i$.

$\endgroup$
1
$\begingroup$

To be read in order, and ideally not all at once.

Hint 1

Given a vertex $p_i$, let $\mathbf n_i$ the unit vector such that the closed half-plane "to the left" of oriented line $qp_i$ is: $$\{ x\in\mathbb R^2\mid \langle x-p_i,\,\mathbf n_i\rangle \ge 0\}$$ where $\langle \mathbf a,\,\mathbf b\rangle$ denotes the scalar product of vectors $\mathbf a$ and $\mathbf b$. Looking at those unit vectors should be useful.

Hint 2

Vertex $p_i$ supports a right tangent line if and only if $\langle p_{i-1}-p_i,\, \mathbf n_i\rangle \ge 0$ and $\langle p_{i+1}-p_i,\,\mathbf n_i\rangle\ge 0$, with $p_{-1}=p_n$ and $p_{n+1}=p_0$.

Hint 3

If a vertex $p_i$ doesn't satisfy the two conditions from hint 2, you can (very often) figure out "which way" the proper vertex is wrt $p_i$. The only situation where you cannot figure that out, is if $p_i$ supports a "left tangent line".

Hint 4

Dichotomic search?

Hint 5

No.

$\endgroup$
2
  • $\begingroup$ But how am I suppose to find these $n_i$ vectors? $\endgroup$ Sep 12 '18 at 17:09
  • $\begingroup$ You compute the unit vector from $q$ to $p_i$ and rotate it $\pi/2$ radians to the left. $\endgroup$
    – N.Bach
    Sep 12 '18 at 17:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.