How to Mathematically Represent the R.L. Graham Algorithm

68 Views Asked by At

I am aware the convex hull algorithm known as Graham Scan can be computed by sorting the derived vectors from points given in a 2D plane. One then iterates through a series of Cross Product calculations to find the determinant of a pair of vectors derived from the sequence of given points. This determine whether to move clockwise of counter clockwise with respect to drawing a convex hull in an efficient manner.

How do I represent that using sigma notation?

I was thinking along the line of: $\sum_{i=1}^{N} Det(V_i,V_{i+1})...Det(V_n,V_{n-1}),$ where $V_i$ is the initial vector.

Thank you in advance.

1

There are 1 best solutions below

0
On BEST ANSWER

According to this paper, it looks like what I had above is the best way to represent Graham Scan: $\sum_{i=1}^{N} Det(V_i,V_{i+1})...Det(V_n,V_{n-1}),$ where $V_i$ is the initial vector.