A Time-Optimal Multiple Search Algorithm on Enhanced Meshes,with Applications |
| |
Affiliation: | 1. Department of Tourism and Recreation, University of Physical Education, 31-571, Cracow, Poland;2. Institute of Landscape Development, Recreation and Conservation Planning, Department of Landscape, Spatial and Infrastructure Sciences, University of Natural Resources and Life Sciences (BOKU), 1190, Vienna, Austria;3. Department of Physical Education and Sport, University of Valencia, 46010, Valencia, Spain |
| |
Abstract: | Given a sorted sequence A = a1, a2, ..., an of items from a totally ordered universe, along with an arbitrary sequence Q = q1, q2, ..., qm (1 ≤ m ≤ n) of queries, the multiple search problem involves computing for every qj (1 ≤ j ≤ m) the unique ai for which ai−1 ≤ qj < ai. In this paper we propose a time-optimal algorithm to solve the multiple search problem on meshes with multiple broadcasting. More specifically, on a formula] × formula] mesh with multiple broadcasting, our algorithm runs in formula] 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. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|