An optimal hypercube algorithm for the all nearest smaller values problem

Author

Kravets, Dina ; Plaxton, C. Greg

Author_Institution

Dept. of Comput. Sci., New Jersey Inst. of Technol., Newark, NJ, USA

fYear

1994

fDate

26-29 Oct 1994

Firstpage

505

Lastpage

512

Abstract

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. Berkman, Schieber, and Vishkin (1993) give an ANSV algorithm that runs in O(lg n) time on an (n/lg n)-processor CREW PRAM. In this paper, we present an O(lg n)-time n-processor normal hypercube algorithm for the ANSV problem. Furthermore, we prove that any normal hypercube algorithm requires Ω(n) processors to solve the ANSV problem in O(lg n) time. 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

Keywords

computational complexity; computational geometry; parallel algorithms; Cartesian tree; O(lg n) time; all nearest smaller values problem; monotone polygon; normal hypercube algorithm; optimal hypercube algorithm; sequence; triangulating; Binary trees; Computer science; Geometry; Hypercubes; Labeling; Merging; Nearest neighbor searches; Parallel algorithms; Phase change random access memory;

fLanguage

English

Publisher

ieee

Conference_Titel

Parallel and Distributed Processing, 1994. Proceedings. Sixth IEEE Symposium on

Conference_Location

Dallas, TX

Print_ISBN

0-8186-6427-4

Type

conf

DOI

10.1109/SPDP.1994.346129

Filename

346129