首页 | 本学科首页   官方微博 | 高级检索  
     


Parallel algorithms for shortest path problems in polygons
Authors:Hossam ElGindy  Michael Goodrich
Affiliation:(1) School of Computer Science, McGill University, H3A 2K6 Montreal, Quebec, Canada;(2) Department of Computer Science, The Johns Hopkins University, Baltimore, Maryland, USA
Abstract:Given ann-vertex simple polygon we address the following problems: (i) find the shortest path between two pointss andd insideP, and (ii) compute the shortestpath tree between a single points and each vertex ofP (which implicitly represents all the shortest paths). We show how to solve the first problem inO(logn) time usingO(n) processors, and the more general second problem inO(log2n) time usingO(n) processors, and the more general second problem inO(log2n) time usingO(n) processors for any simple polygonP. We assume the CREW RAM shared memory model of computation in which concurrent reads are allowed, but no two processors should attempt to simultaneously write in the same memory location. The algorithms are based on the divide-and-conquer paradigm and are quite different from the known sequential algorithmsResearch supported by the Faculty of Graduate Studies and Research (McGill University) grant 276-07
Keywords:Computational Geometry  Parallel algorithms  Simple polygon  Shortest path
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号