Multisearch techniques for implementing data structures on a mesh-connected computer

The multisearch problem consists of efficiently performing O(n) search processes on a data structure modeled as a graph G with n constant-degree nodes. Denote by r the length of the longest search path associated with a search process, and assume that the paths are determined "online". In this paper, we solve the multisearch problem in O(√n+r√n/logn time on a √n ×√n mesh-connected computer. For most data structures, the search path traversed when answering one search query has length r = O (log n). For these cases, our algorithm processes O(n) such queries in asymptotically optimal time, O(√n). The classes of graphs considered contain most of the important data structures that arise in practice (ranging from simple trees to Kirkpatrick hierarchical search DAGs). Multisearch is a useful abstraction that models many specific problems and can be used to implement parallel data structures on a mesh. Applications include interval trees and the related multiple interval intersection search, as well as hierarchical representations of polyhedra and its many applications (e.g., lines-polyhedron intersection queries, multiple tangent plane determination, intersecting convex polyhedra, and three-dimensional convex hull).