The Art Gallery Guardian

Find the minimum of a bitonic sequence


A sequence is a0,,an1a_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+logn)O(m+\log n) time, where mm 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 bb such that bi=aib_i = a_i for i<ni < n and bi+n=bib_{i+n} = b_i for all ini\geq n. We only have to find one local minima in any consecutive subsequence of length nn. This time we partition a interval into 4 pieces.

We define a valley to be 3 points x<y<zx < y < z such that bxbyb_x \geq b_y, bybzb_y \leq b_z, but not bx=by=bzb_x=b_y=b_z. The valley can't be too large (zxn|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 yxzy|y-x|\geq |z-y|, pick the midpoint ww between xx and yy, and consider the relations. w<yw < y, then we have an valley (x,w,y)(x,w,y). w>yw>y, then we have an valley (w,y,z)(w,y,z), if bw=byb_w=b_y, consider the midpoint of ww and yy to be uu. If bw=bu=byb_w=b_u=b_y, we know at least 1/81/8 of the values are the same, and do a linear search between xx and zz. Otherwise, we must have bw>bu<byb_w > b_u < b_y(draw it and see why) and this is a new valley!

If we have yx<zy|y-x|<|z-y|, something similar to above can be done.

It's easy to see the recursion gets us O(m+log(nm))=O(m+logn)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<n0 < k < n If b0>bkb_0 > b_k, then b0,bk,bnb_0,b_k,b_n is a valley. If b0<bkb_0 < b_k, then bk,bn,bk+nb_k,b_n,b_{k+n} is a valley. So we pick 3 possible kk that is n/4n/4 apart, and either one of them allow us to construct a valley, or at least n/4n/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 .
Tags: Algorithm.