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, φ, ⊕), where Q is a set of queries, A is a set of items, D is a set of solutions, φ: Q×A→D is a function, and ⊕ is a commutative and associative binary operator over D. The input to the MQ problem consists of a sequence Q=⟨q₁,q₂…,q_m⟩ of m queries from Q and of a sequence A=⟨a₁,a₂,…a_n⟩ of n items from A. The goal is to compute, for every query q_i (1⩽i⩽m) its solution defined as φ(q_i,A)=φ(q _i,a₁)⊕φ(q_i,a₂ )⊕···⊕φ(q_i,a_n ). We begin by discussing a generic algorithm that solves a large class of MQ problems in O(√m+f(n)) time on a reconfigurable mesh of size √n×√n, where f(n) is the time necessary to compute the expression d₁ ⊕ d₂ ⊕···⊕ d_n with d_i ∈ 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 √n×√n. Given a set A of n points and a set Q of m (m⩽n) points in the plane, our algorithm reports, in O(√m+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 Ω(√n) time on a reconfigurable mesh of size √n×√n. Finally, we prove an Ω(√m+g(n)) time lower bound for nontrivial MQ problems, where g(n) is the lower bound for evaluating the expression d₁ ⊕ d₂ ⊕···⊕ d_n with d_i ∈ D, on a reconfigurable mesh of size √n×√n