An improved hypercube bound for multisearching and its applications

Authors
Citation
Mj. Atallah, An improved hypercube bound for multisearching and its applications, INT J C GEO, 9(1), 1999, pp. 29-38
Citations number
12
Categorie Soggetti
Engineering Mathematics
Journal title
INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS
ISSN journal
02181959 → ACNP
Volume
9
Issue
1
Year of publication
1999
Pages
29 - 38
Database
ISI
SICI code
0218-1959(199902)9:1<29:AIHBFM>2.0.ZU;2-H
Abstract
We give a result that implies an improvement by a factor of log log n in th e hypercube bounds for the geometric problems of batched planar point locat ion, trapezoidal decomposition, and polygon triangulation. The improvements are achieved through a better solution to the multisearch problem on a hyp ercube, a parallel search problem where the elements in the data structure S to be searched are totally ordered, but where it is not possible to compa re in constant time any two given queries q and q'. Whereas the previous be st solution to this problem took O(log n(log log n)(3)) time on an n-proces sor hypercube, the solution given here takes O(log n(log log n)(2)) time on an n-processor hypercube. The hypercube model for which we claim our bound s is the standard one, SIMD, with O(1) memory registers per processor, and with one-port communication. Each register can store O(log n) bits, so that a processor knows its ID.