EFFICIENT PARALLEL RANGE SEARCHING AND PARTITIONING ALGORITHMS*

Abstract

We present an optimal parallel construction of the range tree data structure and use this construction to solve several geometric partitioning problems. In the range tree, we show how to perform a count-mode orthogonal range query in 0(log n) time by a single processor and a report mode orthogonal range query in 0(log n) time using 0(1 + log n) processors, where k is the number of points inside the query range. We consider partitioning problems of the following nature. Given a planar point set S (∣S∣ = ri) a measure μacting on 5 and a pair of values μ1 and μ2,the task is to find a partition of S into two components S₁ and S₂ (S = S₁U S₂) such that μ(S₁) =μ1 for i=1, 2. We consider several measures like diameter under L∞ and l₁ metric; area, perimeter of the smallest enclosing axes-parallel rectangle; and the side length of the smallest enclosing axes-parallel square. All our parallel algorithms foi partitioning problems run in 0(log n) time using 0(n) processors. Our algorithms are designed for the CREW PRAM model of parallel computation.

Keywords:

• Parallel algorithms
• CREW PRAM
• Computational geometry
• Range searching
• Partitioning algorithms
• L∞ and L₁ metric

C.R. Categories:

• B.3.2 [Shared Memory]
• C.1.2 [SIMD processor architecture]
• F.2.2 [Nonnumerical algorithms]
• G.1.0 [Parallel algorithms] 1.3.5 [Geometric algorithms] 1.5.3 [Pattern recognition algorithms]

Notes

*This work was partially supported by a Research Launching Grant of the Faculty of Engineering and Mathematical Sciences, University of Western Australia.

Additional information

Notes on contributors

AMITAVA DATTA

e-mail: [email protected].