Cascading Divide-and-Conquer: A Technique for Designing Parallel Algorithms

Get BibTex-formatted data

Author

Mikhail Atallah, Richard Cole, Michael Goodrich

Entry type

techreport

Abstract

Techniques for parallel divide-and-conquer are presented, resulting in improved parallel algorithms for a number of problems. The problems for which improved algorithms are given include segment intersection detection, trapezoidal decomposition, and planar point location. Efficient parallel algorithms are algo given for fractional cascading, three-dimensional maxima, two-set dominance counting, and visibility from a point. All of the algorithms presented run in O (log n) time with either a linear or a sublinear number of processors in the CREW PRAM model.

Date

1989 – 06

Institution

Society for Industrial and Applied Mathematics

Key alpha

Atallah

Number

Pages

499-532

Volume

Publication Date

1989-06-01

Keywords

parallel algoritms, parallel data structures, divide and conquer, computational geometry, fractional cascading, visibility, planar point location, trapezoidal decomposition, dominance, intersection detection

Location

A hard-copy of this is in the Papers Cabinet

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.

@Techreport{ Atallah,
	title = "Cascading Divide-and-Conquer: A Technique for Designing Parallel Algorithms",
	author = "Mikhail Atallah, Richard Cole, Michael Goodrich",
	year = "1989",
	month = "06",
	institution = "Society for Industrial and Applied Mathematics",
	number = "3",
	pages = "499-532",
	volume = "18",
	abstract = "Techniques for parallel divide-and-conquer are presented, resulting in improved parallel algorithms for a number of problems.  The problems for which improved algorithms are given include segment intersection detection, trapezoidal decomposition, and planar point location.  Efficient parallel algorithms are algo given for fractional cascading, three-dimensional maxima, two-set dominance counting, and visibility from a point.  All of the algorithms presented run in O (log n) time with either a linear or a sublinear number of processors in the CREW PRAM model.",
	keywords = "parallel algoritms, parallel data structures, divide and conquer, computational geometry, fractional cascading, visibility, planar point location, trapezoidal decomposition, dominance, intersection detection",
}