.png){kind=icon}
返回
Coarse-grained parallel geometric search
.png){kind=icon}
PRE
AI
DOI：10.1006/jpdc.1998.1527.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
We present a parallel algorithm for solving the nest element sea, ch problem on a set of line segments, using a BSP-like model referred to as the com se grained multicomputer (CGM). The algorithm requires O(1) communication rounds (h-relations with h = O(n/p)), O((n/p) log n) local computation, and ((n/p) log p) memory per processor, assuming n/p greater than or equal to p. Our result implies solutions to the point location, trapezoidal decomposition, and polygon triangulation problems. A simplified version for axis-parallel segments requires only O(n/p) memory per processor, and we discuss an implementation of this version. As in a previous paper by Develliers and Fabri (Int. J. Comput. Geom. Appl. 6 (1996), 487-506), our algorithm is based on a distributed implementation of segment trees which are of size O(n log n). This paper improves on op. cit. in several ways: (1) It studies the more general next element search problem which also solves, e.g., planar point location. (2) The algorithms require only O((n/p)log n) local computation instead of O(log p*(n/p) log n). (3) The algorithms require only O((n/p) log p) local memory instead of O((n/p) log n). (C) 1999 Academic Press.
Keyword:
BSP
coarse-grained multicomputer
next element search
planar subdivision search
scalable parallel algorithms
segment tree
simple polygon triangulation
trapezoidal map
期刊
IF:
4
论文数:
3.8K
被引数:
4.8K
机构
暂无机构信息
引用论文
.png){kind=icon}
分享收藏
Fluorescence of 9-anthroic acid and its esters. Environmental effects on excited-state behavior
PREAI
分享收藏
查看更多内容