Optimal algorithms for the multiple query problem on reconfigurable meshes, with applications
The main contribution of this work is to show that a number of fundamental and seemingly unrelated problems in database design, pattern recognition, robotics, computational geometry, and image processing can be solved simply and elegantly by stating them as instances of a unifying algorithmic framework that we call the Multiple Query problem. The Multiple Query problem (MQ, for short) is a 5-tuple (Q,A,D,phi,circle plus), where Q is a set of queries, A is a set of items, D is a set of solutions, phi : Q x A --> D is a function, and circle plus is a commutative and associative binary operator over D. The input to the MQ problem consists of a sequence Q = (q(1),q(2),...,q(m) ) of m queries from Q and of a sequence A = (a(1),a(2,)...a(n)) of n items from A. The goal is to compute, for every query q(i) (I less than or equal to i less than or equal to m) its solution defined as phi (q(b),A) = phi (q(i),a(2)) circle plus ... circle plus phi (q(i),a(n)). We begin by discussing a generic algorithm that solves a large class of MQ problems in O(rootm + f(n)) time on a reconfigurable mesh of size rootn x rootn, where f (n) is the time necessary to compute the expression d(1) circle plus d(2) circle plus (...) circle plus d(n) with d(n) is an element of D on such a platform. We then go on to show that the MQ framework affords us an optimal algorithm for the multiple point location problem on a reconfigurable mesh of size rootn x rootn. Given a set A of n points and a set Q of m (m less than or equal to n) points in the plane, our algorithm reports, in O(rootm + log log n) time, all points of Q that lie inside the convex hull of A. Quite surprisingly, our algorithm solves the multiple point location problem without computing the convex hull of A which, in itself, takes Omega(rootn) time on a reconfigurable mesh of size rootn x rootn. Finally, we prove an Omega(rootm + g(n)) time lower bound for nontrivial MQ problems, where g(n) is the lower bound for evaluating the expression d(1) circle plus d(2) circle plus (...) d(n) with d(1) is an element of D-1 on a reconfigurable mesh of size rootn x rootn.
reconfigurable mesh database design pattern recognition robotics computational geometry image processing query processing morphology parallel algorithms