1996/05/01 by Daria Kravets, C. Gregory Plaxton · 8 citations
Computer Science · Engineering · Mathematics · #Algorithms and Data Compression #Optimization and Packing Problems #Optimization and Search Problems #Hypercube #Monotone polygon #Sequence (biology) #Combinatorics #Polygon (computer graphics) #Tree (set theory) #Element (criminal law) #Computer science #Simple polygon #Parallel algorithm #Discrete mathematics #Algorithm #Mathematics
paper · doi:10.1109/71.503770
published in IEEE Transactions on Parallel and Distributed Systems 7(5), 456-462 (Institute of Electrical and Electronics Engineers)
openalex publication_date 1996/05/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/11
Given a sequence of n elements, the All Nearest Smaller Values (ANSV) problem is to find, for each element in the sequence, the nearest element to the left (right) that is smaller, or to report that no such element exists. Time and work optimal algorithms for this problem are known on all the PRAM models but the running time of the best previous hypercube algorithm is optimal only when the number of processors p satisfies 1/spl les/p/spl les/n/((lg/sup 3/ n)(lg lg n)/sup 2/). In this paper, we prove that any normal hypercube algorithm requires /spl Omega/(M) processors to solve the ANSV problem in O(lg n) time, and we present the first normal hypercube ANSV algorithm that is optimal for all values of n and p. We use our ANSV algorithm to give the first O(lg n)-time n-processor normal hypercube algorithms for triangulating a monotone polygon and for constructing a Cartesian tree.