An Improved Hypercube Bound for Multisearching and its Applications

Get BibTex-formatted data

Download

PDF

Author

Mikhail Atallah

Tech report number

COAST TR 97-23

Entry type

article

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.

Download

PDF

Date

1997 – November

URL

http://web.ebscohost.com/ehost ... ==#db=aph&AN=10236295

Address

West Lafayette, IN 47907-1398

Journal

International Journal on Computational Geometry & Applications

Key alpha

Atallah

Note

COAST Publications

Publication Date

2001-01-01

Keywords

parallel algorithms, hypercube, multisearching, trapezoidal decomposition, point location, polygon triangulation

BibTex-formatted data

To refer to this entry, you may select and copy the text below and paste it into your BibTex document. Note that the text may not contain all macros that BibTex supports.

@Article{ Atallah,
	title = "An Improved Hypercube Bound for Multisearching and its Applications",
	author = "Mikhail Atallah",
	year = "1997",
	month = "November",
	address = "West Lafayette, IN 47907-1398",
	journal = "International Journal on Computational Geometry & Applications",
	note = "COAST Publications",
	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",
	url = "http://web.ebscohost.com/ehost/detail?vid=1&hid=9&sid=99a0287e-e8f1-4c8d-8c09-ba849f925ff1@sessionmgr2&bdata=JnNpdGU9ZWhvc3QtbGl2ZQ==#db=aph&AN=10236295",
}