3
$\begingroup$

One of the ways to prove that Graham Scan constructs convex hull in linear time is using planarity of the graph obtained by running the algorithm. This graph is always planar, so according to Euler's formula the number of edges can never be more than $3*n$ (where $n$ is the number of vertices). My question is, how do we know that the edges examined by Graham Scan never intersect (hence always form a planar graph)? Here is the screenshot of this being discussed in the course "Computational Geometry" from Tsinghua University (from EdX.org). The lecturer just mentioned it being true, but did not give the proof. enter image description here

$\endgroup$
1
$\begingroup$

The edges examined never intersect because all points are first sorted in terms of angle from the starting point, and then traversed counterclockwise sequentially. By examining edges to each point sorted by their angle counterclockwise and never traversing clockwise (because you stop when you reach the starting node), you ensure that the edges won't interest.

See this for a good visual.

$\endgroup$

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.