Name
Title | ||
|---|---|---|
Optimal Algorithms for the Multiple Query Problem on Reconfigurable Meshes, with Applications |
Abstract | ||
|---|---|---|
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 ({\cal{Q}}, {\cal{A}}, {\cal{D}}, \phi, \oplus), where {\cal{Q}} is a set of queries, {\cal{A}} is a set of items, \cal D is a set of solutions, \phi:{\cal{Q}}\times {\cal{A}}\rightarrow {\cal{D}} is a function, and \oplus is a commutative and associative binary operator over \cal D. The input to the MQ problem consists of a sequence Q=\langle q_1, q_2, \ldots, q_m\rangle of m queries from {\cal{Q}} and of a sequence A=\langle a_1, a_2, \ldots a_n\rangle of n items from {\cal{A}}. The goal is to compute, for every query q_i (1\leq i\leq m) its solution defined as \phi(q_i,A) = \phi(q_i,a_1)\oplus \phi(q_i,a_2) \oplus \cdots \oplus \phi(q_i,a_n). We begin by discussing a generic algorithm that solves a large class of MQ problems in O(\sqrt{m}+f(n)) time on a reconfigurable mesh of size \sqrt{n}\times \sqrt{n}, where f(n) is the time necessary to compute the expression d_1 \oplus d_2\oplus \cdots \oplus d_n with d_i\in{\cal{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 \sqrt{n}\times\sqrt{n}. Given a set A of n points and a set Q of m(m\leq n) points in the plane, our algorithm reports, in O(\sqrt{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 \Omega(\sqrt{n}) time on a reconfigurable mesh of size \sqrt{n}\times\sqrt{n}. Finally, we prove an \Omega(\sqrt{m}+g(n)) time lower bound for nontrivial MQ problems, where g(n) is the lower bound for evaluating the expression d_1 \oplus d_2\oplus \cdots \oplus d_n with d_i\in{\cal{D}}, on a reconfigurable mesh of size \sqrt{n}\times\sqrt{n}. |
Year | DOI | Venue |
|---|---|---|
2001 | 10.1109/71.954618 | IEEE Trans. Parallel Distrib. Syst. |
Keywords | Field | DocType |
convex hull,reconfigurable meshes,cal d,oplus d_n,mq problem,optimal algorithms,mq framework,multiple point location problem,multiple query problem,nontrivial mq problem,expression d_1,reconfigurable mesh,image processing,point location,navigation,algorithm design and analysis,database design,pattern recognition,computational geometry,application software,generic algorithm,parallel algorithms,computer vision,robotics,lower bound,database management systems,morphology | Reconfigurable mesh,Polygon mesh,Computer science,Upper and lower bounds,Computational geometry,Convex hull,Algorithm,Real-time computing,Omega | Journal |
Volume | Issue | ISSN |
12 | 9 | 1045-9219 |
Citations | PageRank | References |
2 | 0.37 | 17 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| venkatavasu bokka | 1 | 35 | 3.37 |
| Koji Nakano | 2 | 1165 | 118.13 |
| Stephen Olariu | 3 | 125 | 8.24 |
| James L. Schwing | 4 | 402 | 34.25 |
| Larry Wilson | 5 | 127 | 8.72 |