AN OPTIMAL PARALLEL ALGORITHM FOR BUILDING A DATA STRUCTURE FOR PLANAR POINT LOCATION

被引：6

作者：

COLE, R

ZAJICEK, O

机构：

[1] Courant Institute of Mathematical Sciences, New York University, New York, NY 10012

来源：

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING | 1990年 / 8卷 / 03期

基金：

美国国家科学基金会;

关键词：

Approximate Parallel Scheduling - Parallel Algorithms;

D O I：

10.1016/0743-7315(90)90103-V

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Using a modification of the Approximate Parallel Scheduling of R. Cole and U. Vishkin (SIAM J. Comput. 17, 11988),128-142), we give an optimal parallel algorithm for generating a linear size data structure for planar point location that supports an O(log n) query time. Our algorithm runs on a CREW PRAM in time O(log n) using n log n processors. © 1990.

引用

页码：280 / 285

页数：6

共 9 条

[1]

Aggarwal A., 1985, 26th Annual Symposium on Foundations of Computer Science (Cat. No.85CH2224-4), P468, DOI 10.1109/SFCS.1985.42

[2]

ATALLAH MJ, 1988, 28TH P IEEE ANN S F, P151

[3] APPROXIMATE PARALLEL SCHEDULING .1. THE BASIC TECHNIQUE WITH APPLICATIONS TO OPTIMAL PARALLEL LIST RANKING IN LOGARITHMIC TIME [J].

COLE, R ;

VISHKIN, U .

SIAM JOURNAL ON COMPUTING, 1988, 17 (01) :128-142

[4]

COLE R, IN PRESS INFORMATION

[5]

DADOUN N, 1987, 3RD P ANN S COMP GEO, P205

[6]

GOLDBERG AV, 1987, 19TH P ANN ACM S THE, P315

[7]

HAGERUP T, 1987, ICALP, P304

[8] OPTIMAL SEARCH IN PLANAR SUBDIVISIONS [J].

KIRKPATRICK, D .

SIAM JOURNAL ON COMPUTING, 1983, 12 (01) :28-35

[9]

[No title captured]

← 1 →