The Art Gallery Guardian

Find the minimum of a bitonic sequence

A sequence is \(a_0,\ldots,a_{n-1}\) is bitonic if it is a circular shift of a first non-increasing then non-decreasing sequence.

Find an algorithm that can find the minimum value in the sequence in \(O(m+\log n)\) time, where \(m\) is the maximum number of repeats for a single element. This problem is a generalization of a previous problem.

A trick about circular shift of an sequence is to consider the sequence as a periodic sequence. Create sequence \(b\) such that \(b_i = a_i\) for \(i < n\) and \(b_{i+n} = b_i\) for all \(i\geq n\). We only have to find one local minima in any consecutive subsequence of length \(n\). This time we partition a interval into 4 pieces.

We define a valley to be 3 points \(x < y < z\) such that \(b_x \geq b_y\), \(b_y \leq b_z\), but not \(b_x=b_y=b_z\). The valley can't be too large (\(|z-x|\leq n\)). If we have such an valley and this valley contains a local minima, then it is easy to create a smaller (3/4 of the original size) valley that also contain the local minima.

If \(|y-x|\geq |z-y|\), pick the midpoint \(w\) between \(x\) and \(y\), and consider the relations. \(w < y\), then we have an valley \((x,w,y)\). \(w>y\), then we have an valley \((w,y,z)\), if \(b_w=b_y\), consider the midpoint of \(w\) and \(y\) to be \(u\). If \(b_w=b_u=b_y\), we know at least \(1/8\) of the values are the same, and do a linear search between \(x\) and \(z\). Otherwise, we must have \(b_w > b_u < b_y\)(draw it and see why) and this is a new valley!

If we have \(|y-x|<|z-y|\), something similar to above can be done.

It's easy to see the recursion gets us \(O(m+\log (\frac{n}{m}))=O(m+\log n)\). So the only problem comes from how do we find the first valley that contains the local minima. Let \(0 < k < n\) If \(b_0 > b_k\), then \(b_0,b_k,b_n\) is a valley. If \(b_0 < b_k\), then \(b_k,b_n,b_{k+n}\) is a valley. So we pick 3 possible \(k\) that is \(n/4\) apart, and either one of them allow us to construct a valley, or at least \(n/4\) of the points have the same value, and we use linear search.

This algorithm is basically the simplified version of the algorithm in Boris Veroy's paper that can handles repeats.

Posted by Chao Xu on 2013-08-18.
Tags: Algorithm.