## Abstract

The all nearest smaller values problem is defined as follows. Let A = (a_{1}, a_{2}, a_{n}) be n elements drawn from a totally ordered domain. For each a_{i}, 1 ≤ i ≤ n, find the two nearest elements in A that are smaller than a_{i} (if such exist): the left nearest smaller element a_{j} (with j < i) and the right nearest smaller element a_{k} (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.

Original language | English (US) |
---|---|

Pages (from-to) | 344-370 |

Number of pages | 27 |

Journal | Journal of Algorithms |

Volume | 14 |

Issue number | 3 |

DOIs | |

State | Published - May 1993 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- Control and Optimization
- Computational Mathematics
- Computational Theory and Mathematics