Optimal doubly logarithmic parallel algorithms based on finding all nearest smaller values

The all nearest smaller values problem is defined as follows. Let A = (a₁, a₂, a_n) be n elements drawn from a totally ordered domain. For each a_i, 1 ≤ i ≤ n, find the two nearest elements in A that are smaller than a_i (if such exist): the left nearest smaller element a_j (with j < i) and the right nearest smaller element a_k (with k > i). We give an O(log log n) time optimal parallel algorithm for the problem on a CRCW PRAM. We apply this algorithm to achieve optimal O(log log n) time parallel algorithms for four problems: (i) Triangulating a monotone polygon, (ii) Preprocessing for answering range minimum queries in constant time, (iii) Reconstructing a binary tree from its inorder and either preorder or postorder numberings, (vi) Matching a legal sequence of parentheses. We also show that any optimal CRCW PRAM algorithm for the triangulation problem requires Ω(log log n) time.