๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Constant-time RMESH algorithms for the range minima and co-minima problems

โœ Scribed by Sung Kwon Kim

Book ID
104304633
Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
270 KB
Volume
24
Category
Article
ISSN
0167-8191

No coin nor oath required. For personal study only.

โœฆ Synopsis

We present efficient solutions on an RMESH for the following two problems: i The range ลฝ . minima problem: Given an array of real numbers, A s a , . . . ,a , preprocess A so that, after 1 n ร„ 4 preprocessing, for any two query indices 1 F i F j F n, min a , . . . ,a can be found efficiently. i j ลฝ . ลฝ . ii The range co-minima problem: Given an array of positive integers, B s b , . . . ,b with 1 n b F n for all i, preprocess B so that, after preprocessing, for any two query indices 1 F i F j F n, i ร„ 4 the minimum positive integer not in b , . . . ,b can be found efficiently. In other words, min i j

ร„ร„ 4 ร„ 44 1,2, . . . ,n q 1 y b , . . . ,b is to be found. Our preprocessing algorithms for both problems i j take constant time on an n = n RMESH, and a query can be answered in constant time using a single processor.

๐Ÿ“œ SIMILAR VOLUMES

[IEEE Comput. Soc. Press International S
[IEEE Comput. Soc. Press International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN) - Kanazawa, Japan (14-16 Dec. 1994)] Proceedings of the International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN) - An O(log N log log N) time RMESH algorithm for the simple polygon visibility problem
โœ Sung-Ryul Kim, ; Kunsoo Park, ; Yoo-Kun Cho, ๐Ÿ“‚ Article ๐Ÿ“… 1994 ๐Ÿ› IEEE Comput. Soc. Press โš– 462 KB