Tight Triply-Logarithmic Parallel Algorithms for Integer Range Minima and Related Problems

We consider the minimum computation problem and several well known generalizations: prefix minima, range minima, and all-nearest-smaller- values problems, for input elements drawn from the integer domain [1.. s] where s => n. Simple and efficient algorithms are given, all taking O(log log log s) time using an optimal number of processors, and O(ns sup element of) space on the Common CRCW PRAM. Ragde gave a matching lower bound of OMEGA (log log log s) for the minimum problem: our upper bounds are therefore tight. One application of these results is an optimal triply-logarithmic parallel algorithm for triangulating a monotone polygon whose coordinates are taken from the domain.