Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6874784 | Journal of Discrete Algorithms | 2016 | 13 Pages |
Abstract
Given a sequence of n elements from a totally ordered set, and a position in the sequence, the nearest larger neighbor (NLN) query returns the position of the element which is closest to the query position, and is larger than the element at the query position. The problem of finding the nearest larger neighbors of all the elements in a one-dimensional array has attracted interest due to its applications for parenthesis matching and in computational geometry [1], [2], [3]. We consider a data structure version of this problem, which is to preprocess a given sequence of elements to construct a data structure that can answer NLN queries efficiently. We consider time-space tradeoffs for the problem in both the indexing and the encoding models when the input is in a one dimensional array, and also initiate the study of this problem on two-dimensional arrays.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Varunkumar Jayapaul, Seungbum Jo, Rajeev Raman, Venkatesh Raman, Srinivasa Rao Satti,