Highest point on polygon?

Question

If you put a polygon on a Cartesian grid, how would you prove that a vertex of that polygon has the largest (or equal to the largest) y coordinate in the polygon? (Sorry I couldn't find this in a Google search.)

Answer 1

The general term for this is convex maximization. This is a particularly trivial type, as the dimension of the search space is only $2$, all the boundaries are straight, and the optimization function is simply the projection $(x,y) \rightarrow y$. The gradient of that function is simply $(0,1)$, that is, a vertical vector. If we follow the gradient, we easily find ourselves at an edge on the "top" of the polygon. Once we reach the edge, we follow the gradient projected onto the tangent of the boundary (since the boundary is straight, the tangent is the same as the edge, so this just means that we follow whichever direction of the edge is pointing "up"). This results in us following the edge until we reach a corner, at which point the projection of the gradient onto the tangent reverses direction (this is similar to how in extremum searches in one dimension, the derivative changes sign when we reach an extremum).

In other words, any interior point clearly has a "better" point above it. Once we get to the edge, going directly up may take us outside of the figure. Once we get to an edge, either that edge is horizontal, in which the vertices on either side of the edge are maximal, or the edge is diagonal/vertical. If the edge is diagonal/vertical, there is one direction along that edge that is "up" (if the edge is diagonal, then no direction is directly "up", but one direction is going partly up). Following that direction results in increasing the y coordinate, until we get to a vertex. So for every interior point, there is some other point we can go to that increases the y coordinate, and for every non-vertex boundary point, there is some other point we can go to that, at the very least, doesn't decrease the y coordinate.

Answer 2

Any polygon placed on a cartesian grid can be described by a finite list of $(x_i,y_i)$ pairs which describe its vertices. Certainly, you can order these pairs by $y$-coordinate from least to greatest in value. A finite set always has a maximal element. Finally, there cannot be an edge point on the polygon with larger $y$-coordinate than one of its adjoining vertices, because this would mean that the segment between the two vertices increases, and then decreases which is impossible for a line segment.

Answer 3

Suppose a point $x$ in the interior of the polygon $P$ maximizes the absolute value of, say, the $x_1$ coordinate. We're asuming $x \neq 0$. Define an open ball $B=B_r(x)$ such that $P \in B \subset P^{\circ}$. Then the point $(1+r/2)x \in B \subset P$ and it's first coordinate has the same sign and bigger absolute value than that of $x$. Therefore, the point that maximizes $|x_1|$ must be in the boundary if $P$.

Dealing with the boundary should involve a little more work, since a whole side of the polygon could maximize $|x_1|$. But I think that you should be able to separate it in cases depending on the direction on the side.

Say you take a point $x$ lies on a side $L$ of the polygon $P$, and call $v=(v_1, v_2)$ the vector that gives the direction of $L$. If $v_1=0$, the $x_1$ coordinate is constant in $L$. So if the maximum of $|x_1|$ is reached in some point of $L$, it is reached in all points of $L$, in particular in both of its vertices. If $v_1 \neq 0$, you should be able to reproduce the ball argument I used for the interior to prove that the maximum can't be reached in some point $x \in L$ that isn't a vertex.

I know you asked for maximum coordinate, not absolute value of the coordinate, but the argument is essentially the same appart from some distinctions based on the sign of the coordinate. Also, I'm assuming you are asking the question in $\mathbb{R}^2$. I'd need you to tell me what you understand by a polygon in $\mathbb{R}^n$ if that wasn't the case. Ask me further questions if you need to.