algorithmgeometrymaxconvexconvex-polygon

Find max y coordinate of a convex polygon

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

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!

Solution

  • 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:

    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]:

    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.