About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Journal of Algorithms
Paper
Optimal doubly logarithmic parallel algorithms based on finding all nearest smaller values
Abstract
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.