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)

enter image description here

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?

  • 2
    $\begingroup$ Please edit the question to clarify whether the polygon is a convex polygon. $\endgroup$ – Apass.Jack Mar 22 at 2:32
  • 1
    $\begingroup$ Nice problem. Have you read how to ask a good homework question?? Besides a thoughtful question, it is expected of you to show your partial progress, thoughts or where you got stuck. It will help draw more better answers faster. Otherwise, this post might be closed or downvoted, as posts that simply dump problems are discouraged. This site is a knowledge-sharing question-and-answer place instead of a solution rendering service. $\endgroup$ – Apass.Jack Mar 22 at 2:34
  • $\begingroup$ Assuming they are convex, take a look at golden-section search / Fibonacci search. $\endgroup$ – Eugene Mar 22 at 7:26

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?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.