Encoding Nearest Larger Values

In nearest larger value (NLV) problems, we are given an array A[1..n] of distinct numbers, and need to preprocess A to answer queries of the following form: given any index i in [1,n], return a ``nearest'' index j such that A[j] > A[i]. We consider the variant where the values in A are distinct, and we wish to return an index j such that A[j] > A[i] and |j-i| is minimized, the nondirectional NLV (NNLV) problem. We consider NNLV in the encoding model, where the array A is deleted after preprocessing. The NNLV encoding problem turns out to have an unexpectedly rich structure: the effective entropy (optimal space usage) of the problem depends crucially on details in the definition of the problem. Of particular interest is the tiebreaking rule: if there exist two nearest indices j_1,j_2 such that A[j_1] > A[i] and A[j_2] > A[i] and |j_1 - i| = |j_2 - i|, then which index should be returned? For the tiebreaking rule where the rightmost (i.e., largest index) is returned, we encode a path-compressed representation of the Cartesian tree that can answer all NNLV queries in 1.89997 n + o(n) bits, and can answer queries in O(1) time. An alternative approach, based on forbidden patterns, achieves the same space bound and query time, and (for a slightly different tiebreaking rule) achieves 1.81211 n + o(n) bits. Finally, we develop a fast method of counting distinguishable configurations for NNLV queries. Using this method, we prove a lower bound of 1.62309 n - Theta(1) bits of space for NNLV encodings for the tiebreaking rule where the rightmost index is returned.