Omer Berkman, Baruch Schieber, et al.
International Journal of Computational Geometry and Applications
The all nearest smaller values problem is defined as follows. Let A = (a1, a2, an) be n elements drawn from a totally ordered domain. For each ai, 1 ≤ i ≤ n, find the two nearest elements in A that are smaller than ai (if such exist): the left nearest smaller element aj (with j < i) and the right nearest smaller element ak (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. © 1993 Academic Press, Inc.
Omer Berkman, Baruch Schieber, et al.
International Journal of Computational Geometry and Applications
Sepehr Assadi, Krzysztof Onak, et al.
SODA 2019
Arturs Backurs, Piotr Indyk, et al.
ICML 2019
Don Coppersmith, Uzi Vishkin
Discrete Applied Mathematics