An improved hypercube bound for multisearching and its applications

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.