Abstract
We give a result that implies an improvement by a factor of log log n
in the hypercube bounds for the geometric problems of batched planar
point location, trapezoidal decomposition, and polygon triangulation.
The improvements are achieved through a better solution to the multisearch
problem on a hypercube, 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 compare in constant time any two given queries q and q'.
Whereas the previous best solution to this problem took O(log n(log log n)^3)
time on an n-processor 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 bounds is the standard one, SIMD, with O(1) memory
registers per processor, and with one-port communication. Each registar
can store O(log n) bits, so that a processor knows its ID.
Keywords
parallel algorithms, hypercube, multisearching, trapezoidal decomposition, point location, polygon triangulation
