How to understand Shamos algorithm?

Question

I wanted to find shortest time algorithm for finding the diameter of a convex hull, so I found Shamos algorithm on wikipedia:

GetAllAntiPodalPairs(p[1..n])
    i0 = n
    i = 1
    j = i + 1
    while (Area(i, i + 1, j + 1) > Area(i, i + 1, j))
        j = j + 1
        j0 = j
    while (j != i0)
        i = i + 1
        yield i, j
        while (Area(i, i + 1, j + 1) > Area(i, i + 1, j)
            j = j + 1
            if ((i, j) != (j0, i0))
                yield i, j
            else 
                return
        if (Area(j, i + 1, j + 1) = Area(i, i + 1, j))
            if ((i, j) != (j0, i0))
                yield i, j + 1
            else 
                yield i + 1, j

And this is a gif to visualize the algorithm:

I cannot understand the Area in the code . how it will be calculated given i , i+1 and j+1? And what's exactly the p[1..n] ? Is it the given points or that's different?

I've created a shape for solving that using this algorithm. I know that's not easy but can someone trace the algorithm for this shape? Anybody like me will enjoy it:

user_17537755 · Answer

From a quick research, this is what I understand from the code and the wiki page:

P is the array of vertex of the convex hull, sorted in clockwise (or counter-clockwise).
Area(i,j,k) calculates the area of the triangle formed by P[i],P[j], and P[k]

The code is trying to find parallel lines showing in the gif.

the code block

while (Area(i, i + 1, j + 1) > Area(i, i + 1, j))
        j = j + 1
        j0 = j

is trying to find the farest point j0 relative to the Line L formed by P[i],P[i+1]. A line parallel to L and pass the point j0 and the line L itself forms a line pair in the gif.

How to understand Shamos algorithm?

1 Answers