Optimal parallel algorithms for point-set and polygon problems
Optimal parallel algorithms for point-set and polygon problems
复制标题
点集和多边形问题的最优并行算法
作者：
R. Cole;M. Goodrich
在本文中，我们给出了一些问题的并行算法上定义的点集和多边形。所有算法都具有最优的T（n）* P（n）乘积，其中T（n）是时间复杂度，P（n）是处理器数，并且是针对EREW PRAM或CREW PRAM模型的。我们的算法提供了并行的类似物，众所周知的现象，从顺序计算几何，如事实上，多边形的问题往往可以更有效地解决比点集问题，最近邻问题可以解决，而无需明确构建Voronoi图。
In this paper we give parallel algorithms for a number of problems defined on point sets and polygons. All our algorithms have optimalT(n) * P(n) products, whereT(n) is the time complexity andP(n) is the number of processors used, and are for the EREW PRAM or CREW PRAM models. Our algorithms provide parallel analogues to well-known phenomena from sequential computational geometry, such as the fact that problems for polygons can oftentimes be solved more efficiently than point-set problems, and that nearest-neighbor problems can be solved without explicitly constructing a Voronoi diagram.