A Time-Optimal Multiple Search Algorithm on Enhanced Meshes, with Applications

✍ Scribed by D. Bhagavathi; S. Olariu; W. Shen; L. Wilson

• Publisher: Elsevier Science
• Year: 1994
• Tongue: English
• Weight: 739 KB
• Volume: 22
• Category: Article
• ISSN: 0743-7315
• DOI: 10.1006/jpdc.1994.1074

✦ Synopsis

Given a sorted sequence (A=a_{1}, a_{2}, \ldots, a_{n}) of items from a totally ordered universe, along with an arbitrary sequence (Q=q_{1}), (q_{2}, \ldots, q_{m}(1 \leq m \leq n)) of queries, the multiple search problem involves computing for every (q_{j}(1 \leq j \leq m)) the unique (a_{i}) for which (a_{i-1} \leq q_{j}<a_{i}). In this paper we propose a time-optimal algorithm to solve the multiple search problem on meshes with multiple broadcasting. More specifically, on a (\sqrt{n} \times \sqrt{n}) mesh with multiple broadcasting, our algorithm runs in (O(\sqrt{m})) time which is shown to be time-optimal. We also present some surprising applications of the multiple search algorithm to computer graphics, image processing, robotics, and computational geometry. O 1994 Academic Press, Inc.