2
$\begingroup$

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:

calipers

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: enter image description here

$\endgroup$

1 Answer 1

1
$\begingroup$

Notice that for a fixed side, the distances to the vertices are a multiple of the area formed by the side and the vertices. So comparing the areas is in fact a means to compare the distances.

In the figure, you see all antipodal pairs. You can obtain them efficiently by following the polygon edges in clockwise order, every time finding the opposite-most vertex by revolving clockwise and comparing the distances (this is what guarantees linear time complexity).

The opposite corner advances as many times as there are vertices (because it follows the polygon), at the expense of one extra test per side, to detect when the distance decreases.

enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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