Choosing points for finding bridge in a convex hull

Question

In finding convex hull for a set of points using divide and conquer algorithm, we need to find an upper and lower bridge. The algorithm for finding these bridges, for example, the upper bridge is:

1. Start with any bridge. For example, a bridge is guaranteed if you join the rightmost vertex on the left to the leftmost vertex on the right.

2. Keeping the left end of the bridge fixed, see if the right end can be raised. That is, look at the next vertex on the right polygon going clockwise, and see whether that would be a (better) bridge. Otherwise, see if the left end can be raised while the right end remains fixed.

3. If made no progress in (2) (cannot raise either side), then stop else repeat (2).

My question is is it mandatory to choose only the rightmost vertex on the left to the leftmost vertex on the right? Can we choose:

a. leftmost vertex on the left to the leftmost vertex on the right?

b. rightmost vertex on the left to the rightmost vertex on the right?

c. leftmost vertex on the left to the rightmost vertex on the right?

Answer 1

Actually, the original algorithm by Preparata uses variants a and b. The only thing that you need to guarantee is that the slopes (in any coordinate system) of line segments between the two extremal points on both of the partial hulls is monotone and that you are walking in the right direction. As long as you can guarantee this, you can choose any extremal point combination you like.