Find max y coordinate of a convex polygon

Question

I have an array V[1,2,....,n], where each element of the array represents a vertex of a convex polygon in the form of a coordinate pair (x,y).

It is given that V[1] is the vertex with the minimum x coordinate and that the vertices V[1,2,....,n] are ordered counterclockwise, as in the figure. It is also given that the x coordinates of the vertices are all distinct, as are the y coordinates of the vertices.

Now, I want to find the vertex with max y coordinate value. We all know the naive O(n) method, but is it possible to find it in O(log(n))?

I used the information that V[1] is the vertex with the minimum x coordinate to find the vertex with maximum x coordinate in O(log(n)) time. But is it possible to do it for maximum y coordinate?

Thanks for the help!

Answer 1

Long Version

Binary search is being noted as being the solution in a few places here, but it will only work for some of the cases.

The distribution of the vertices can vary in a number of different ways. You can have many clustered near one point with one isolated elsewhere, you could have vertices that form a parabolic shape (taking your diagram, eliminate vertices 7, 8, and 9 as an example), you could have a logarithmic-like distribution (e.g. only vertices 1, 2, 3, and 4), or really any other number of possibilities. In all of these different cases you're going to have a different quantity and displacement of local maxima and minima.

Odds are you will need a combination of approaches to estimate the distribution and then the application of a strategy that fits the type of distribution.

Let's try to describe such a strategy:

First, keep in mind that you have an array of such vertices, listed in a strict order in a counter-clockwise rotation. This is important and the basis of all further assumptions and reasoning that follow.

Observe the behavior of V[n]. If V[n] has a y-coordinate V[n].y less than that of V[1], or V[n].y < V[1].y, you can conclude that all other vertices V[2, n-1] must also have y-coordinates lower than V[1] (consider why this must be the case). Thus V[1] has the largest y-coordinate.

Now, the rest of this analysis will require that we alter our conceptual model of the polygon to simplify its representation and thus the problem we want to solve. Rather than plot the points (V[i].x, V[i].y) to gain the shape of the polygon, instead plot (i, V[i].y) to represent an imagined continuous function f(i) = V[i].y. The solution to our problem is now the solution to finding the global maximum of the function f(i) = V[i].y.

With that in mind, for all other cases where V[n].y > V[1].y, we must perform a binary search, but we have two possible scenarios to consider:

1. V[2] has a y-coordinate less than V[1].
2. V[2] has a y-coordinate greater than V[1].

This is important because case 1 tells us that V[1] is not a local minima, and case 2 tells us that V[1] is a local minima (once again consider why this must be the case).

Case 2 is a nice, easy case due to V[1] being a local minima. This means that there can only be one additional local minima at V[n], or there is no other local minima at all. We can thus perform a binary- or binary-like search such that we gradually converge on the only local maxima on the curve.

Your diagram is an example of case 1, which is the harder case. V[1] is not a local minima, so it is instead a local maxima. More importantly, you have two possible local maxima, which are located at V[1] and V[n-k] where n-k > 1. To help visualize, if you plot the points for the function f(i) = V[i].y, you will see either a parabolic shape or a sinusoidal shape. The second local maxima at V[n-k] will thus be either the right-most end of the parabola, or the peak of the sinusoidal curve.

(Note: This paragraph is an optional optimization step.) Let's consider how to determine which type of local maxima we're dealing with: if V[n] has a y-coordinate greater than V[n-1], then V[n] must be the second local maxima (again, consider why this must be true) and in fact we can instantly determine that V[n] has the largest y-coordinate. Otherwise, there exists some k such that V[n-k] is our local maxima, meaning we need to perform a search.

This now just leaves us with the consideration for how to conduct the search, to avoid inadvertently converging on V[1] (we need to find a local maxima, and since V[1] is a local maxima we could accidentally converge on it).

Perform a binary search with the following constraints:

• For a given V[i], if V[i].y < V[1].y then converge toward V[n].
• If V[i].y > V[1].y then converge in the direction of increasing y (just compare V[i] to V[i-1] and V[i+1]).

This should allow you to safely converge toward the right-most local maxima and isolate the value within log(n) time.

Now that we've covered the two different cases for V[1].y < V[n].y, let's note that this constrained binary search will work in case 2 just as accurately as it will in case 1. Thus we can then generalize the search for both case 1 and case 2 by following the rules of the constrained binary search for both cases. This reduces the algorithmic complexity significantly.

In all, you should be able to achieve O(log n) time for any general case, with a couple of O(1) edge cases.

Summary

The trick behind this problem is to deconstruct the notion of the polygon, plotting the points (i, V[i].y) rather than (V[i].x, V[i].y), and imagining those points as being on a continuous function. The solution to this problem then becomes the solution to the problem "what is the global maximum of f(i) = V[i].y?". Because of the properties of a convex polygon and the way your vertices are ordered, we can ascertain that V[1] is definitely a local maxima. With that in mind, either V[1] is the global maximum or it isn't, something that we can determine in constant time at the very beginning. If it's not the global maximum, then we can perform a constrained binary search that prevents us from converging on V[1], allowing us to determine the global maximum in logarithmic time. If we feel like being extra sophisticated, we can also determine whether or not V[n] is the global maximum in constant time as an additional optimization step.

---

Short Version

When V[1].y > V[n].y, the maximum is V[1].y. Your solution should use a binary search in cases where V[1].y < V[n].y only. This binary search must abide by the following constraints, given an arbitrary V[i]:

• Base case: if V[1].y > V[i].y, converge in the direction of V[n].
• Standard case: if V[i].y < V[i+1].y, converge in the direction of V[n]; else if V[i].y < v[i-1].y, converge in the direction of V[1]; else V[i].y is the maximum.

There is also an optional optimization that can be performed for the edge case where V[1].y < V[n].y and V[n].y > V[n-1].y. This optimization can be safely skipped and can make conceptualizing and implementing the solution simpler.

The pseudo-code for the corresponding algorithm is as follows:

Solution With Optimization

If V[1].y > V[n].y, then V[1].y is the maximum.

If V[1].y < V[n].y and V[n].y > V[n-1].y, then V[n].y is the maximum.

If V[1].y < V[n].y and V[n].y < V[n-1].y, then perform the constrained binary search.

This strategy has two O(1) edge cases and a standard O(log n) case.

Solution Without Optimization

If V[1].y > V[n].y, then V[1].y is the maximum.

If V[1].y < V[n].y, then perform the constrained binary search.

This strategy has one O(1) edge case and a standard O(log n) case.

Answer 2

You can find the extreme point in any direction using a binary search as described here.

The essential idea is to examine the vector at the end points and the midpoint and use this to determine which part to expand.

Answer 3

Because the polygon is convex, the angle of the vector between successive points monotonically increases from 270 degrees (down. call that -90 degrees) through 0 (right), 90 (up), 180 (left), etc., as you move from one point to the next around the polygon.

Therefore you can binary search to find the smallest angle greater than 180 degrees. The point where the vector to the next point becomes > 180 degrees (V[8] in your example) is where the polygon turns from heading upward or left to heading down, and that point must have the largest Y coordinate.

I think the article that Peter linked to says the same thing, but that's a lot of words to read for such a simple idea.

Answer 4

Let V[m] be the vertex with max y coordinate.

The simplest case to consider is m=1, when V[2].y < V[1].y > v[n].y. Since the exclusion of this case makes subsequent reasoning simpler we'll assume that an initial check for this case is performed.

Consider an edge E[i] with origin V[i], where 1<i<=n. Given the constraint that all x and y coordinates are distinct, E[i] has to lie in one of the 4 planar quadrants:

Given that we've excluded the case where m=i=1, for E[i] lying in Quadrants I, II, or IV it must be the case that m>i. If E[i] lies in Quadrant III then either m=i, which is true if V[i].y > V[i-1].y, or m<i.

We can use this reasoning as the basis for a binary search, where at each iteration we perform:

if E[i] lies in Quadrant III
   if V[i].y > V[i-1].y then m=i
   else consider left half
else
   consider right half

Here's some Java code to illustrate:

static Point maxY(Point[] v)
{       
    // check for max at origin
    if(v[1].y < v[0].y && v[v.length-1].y < v[0].y)
    {
        return v[0];
    }

    int left = 0; 
    int right = v.length-1;     
    Point maxY = null;
    while(left <= right)
    {
        int mid = left + (right-left)/2;
        if(v[(mid+1)%v.length].y < v[mid].y && v[(mid+1)%v.length].x < v[mid].x)
        {
            // Quadrant III
            if(v[mid].y > v[mid-1].y) 
            {
                maxY = v[mid];
                break;
            }
            right = mid - 1;
        }
        else 
        {
            left = mid + 1;
        }
    }
    return maxY;
}

And some simple test cases:

public static void main(String[] args)
{
    Point[][] tests = {
            {new Point(0, 10), new Point(10, 0), new Point(9, 5)},
            {new Point(0, 0), new Point(9, 5), new Point(10, 10)},
            {new Point(0, 0), new Point(10, 10), new Point(5, 8)},
            {new Point(0, 5), new Point(9, 0), new Point(10, 10)},
            {new Point(0, 5), new Point(6,0), new Point(10, 6), new Point(5,10)}};

    for(Point[] coords : tests) 
        System.out.println(maxY(coords) + " : " + Arrays.toString(coords));
}

Output:

(0, 10) : [(0, 10), (10, 0), (9, 5)]
(10, 10) : [(0, 0), (9, 5), (10, 10)]
(10, 10) : [(0, 0), (10, 10), (5, 8)]
(10, 10) : [(0, 5), (9, 0), (10, 10)]
(5, 10) : [(0, 5), (6, 0), (10, 6), (5, 10)]