The all nearest smaller values problem is defined as follows. Let \(A=(a_ 1,\ldots,a_ n)\) be \(n\) elements drawn from a totally ordered domain. For each \(a_ i\), \(1 \leq i \leq n\), find the two nearest elements in \(A\) that are smaller than \(a_ i\) (if such exist): the left nearest smaller element \(a_ i\) (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,
(v) Matching a legal sequence of parentheses.
For the triangulation problem, we also show that any optimal CRCW PRAM algorithm for the problem requires \(\Omega(\log \log n)\) time.