An algorithm that find the max X/Y in a polygon in O(log n)

Question

I got a task to create two functions one finds max $X$ and the other $Y$ in a polygon in $O(\log n)$.

The polygon is represented by an array of its vertices where each vertex is represented by its coordinates $(X,Y)$. We also know that the first vertex in the array has the smallest $X$ coordinate and after that, all the other coordinates are set in the array clockwise and also that all of them are different (all the $X$'s and all the $Y$'s are different)

I have the general idea.. using binary search but I'm not sure how to fully apply it.

How should move in the array while checking coordinates and yet keeping it in $O(\log n)$ complexity?

Answer 1

Assume the polygon is a convex polygon; otherwise there might not be an $O(\log n)$ algorithm to find the maximum of X-coordinates or Y-coordinates.

First, let us handle the case of X-coordinate.

Let $x_1, x_2, \cdots, x_n$ be the X-coordinate of the points. Since $x_1$ is the minimum X-coordinate, that sequence is a bitonic sequence. Here are two nice answers to how to sort a bitonic sequence.

Next, let us solve the case of Y-coordinate, which is mildly more complicated.

Let $y_1, y_2, \cdots, y_n, y_{n+1}=y_1$ be the Y-coordinate of the points. We can drill down into the following cases by comparing $y_1$ against $y_2$ and against $y_n$.

• $C_{\lt, \lt}$ when $y_1\lt y_2$ and $y_1\lt y_n$. Here $y_1$ is the minimum.
• $C_{\gt, \gt}$ when $y_1\gt y_2$ and $y_1\gt y_n$. Here $y_1$ is the maximum.
• $C_{\lt, \gt}$ when $y_1\lt y_2$ and $y_1\gt y_n$. Here Y-coordinates goes up from $y_1$ to the maximum, then goes down to the minimum, then goes up to $y_1$.
• $C_{\gt, \lt}$ when $y_1\gt y_2$ and $y_1\lt y_n$. Here Y-coordinates goes down from $y_1$ to the minimum, then goes up to the maximum, then goes down to $y_1$.

The first two cases are bitonic sequences, which can be treated as before.

Let us check the case of $C_{\lt, \gt}$; the case $C_{\gt, \lt}$ can be handled similarly.

Let $y_M$ is the maximum and $y_m$ is the minimum, where $M<m$. Given an index $1<i<n$, we can compare $i$ to $m$ and $M$ as follows:

• If $y[i-1] < y[i] < y[i+1]$ and $y[i] > y_1$, then $i < M$.
• If $y[i-1] < y[i] > y[i+1]$, then $i = M$.
• If $y[i-1] > y[i] > y[i+1]$, then $M < i < m$.
• If $y[i-1] > y[i] < y[i+1]$, then $i = m$.
• If $y[i-1] < y[i] < y[i+1]$ and $y[i] < y_1$, then $i > m$.

The above result enables us to cut the search intervals in half each time with 2 or 3 comparisons, thus ensuring an algorithm with $O(\log n)$ time-complexity.

---

Exercise. What about the case when we have a sequence of $n$ distinct numbers, in which there are $t$ local maximums and $t+1$ local minimums?