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.