货郎担问题最优并行启发式算法

本文给出了满足三角不等式的货郎担问题的并行启发式算法，在ＳＩＭＤ ＣＲＥＶ ＰＲＡＭ并行机上该算法使用Ｏ（ｎ＾３／ｌｏｇ＾２ｎ）台处理器需Ｏ熄ｌｏｇ＾２ｎ）时间，这里ｎ是给定城市的个数，因而该并行算法是最优的。     

并行归并排序算法

构造效率为Ｏ（１）的并行算法是一个引人注目的问题。［１］和［２］分别提出了并行度为Ｏ（ｌｏｇｎ）和Ｏ（ｎ＾１／２）的、效率为Ｏ（１）的并行排序算法。本文提出一种新的并行排序算法，其效率为Ｏ（１），而并行步数小于［１］和［２］的算法的并行步数。经过改进后，在保持效率为Ｏ（１）的情况下，可进一步将并行度扩大到Ｏ（ｎ＾１／２ｌｏｇ ｎ）。     

一个多元选择算法

本文基于数排序的思想，从高位关键字开始，对ｍ位关键字的ｎ个记录进行扫描，给出了一个多元选择算法，算法的最坏复杂度为Ｏ（ｍ（ｎ＋ｒ）），但平均复杂度为Ｏ（ｎ＋ｒ）。     

可重构造的网孔机器上的k-选择

对于一个 ｍ ×ｎ（ｍ ≤ｋ）的列有序矩阵,文中在 ｎ × ｎ 可重构造的网孔机器上提出了一个并行 ｋ选择算法,其时间复杂度为 Ｏ（ｌｏｇ２ｍ ＋ ｌｏｇｍ ｌｏｇ２ ｎ＋ ｌｏｇ３ ｎ）,而对于一般的ｌ元集,文中在相同的模型下提出了一个时间复杂度为 Ｏ ｌｏｇ２ ｌｎ ＋ ｌｏｇ ｌｎ ｌｏｇ２ ｎ＋ ｌｏｇ３ｎ＋ ｌｎ ｌｏｇ ｌｎ 的并行 ｋ选择算法．当时 ｌ≥ Ｏ（ｎｌｏｇ３ｎ／ｌｏｇ ｌｏｇｎ,该时间复杂度为 Ｏ ｌｎ ｌｏｇ ｌｎ ．特别地,当ｌ＝ Ｏ（ｎ１＋ ε）（ε＞ ０ 为常数）,则时间复杂度为 Ｏ ｌｎ ｌｏｇｎ ．此时达到的加速比为 ｎ／ｌｏｇｎ．     

几何算法求解货郎担问题

本文提出求解货郎担问题的一种几何算法。它的时间复杂性为：Ｏ（ｎ＾３／ｍ）次比较，Ｏ（ｎ＾２）次乘法，其中ｎ，ｍ分别是点集的点数和凸包顶点数。     

一种求简单多边形凸包的最优算法

计算一般多边形凸包的算法时间复杂度为Ｏ（ｎ＾２）。     

简单多边形凸单元剖分的编码算法

本文通过对凹对分类编码的研究，提出了一种复杂度为Ｏ（ｎ＋Ｎ＾２）的简单多边形的凸单元剖分算法。     

最短路径重构算法

研究了在Ｎ个顶点的图中，仅给出了所有顶点对之间最短路径距离矩阵，而计算任两顶点间最短路径问题。这种算法因没有利用原始图中有关边的信息，被称为重构算法。本研究取得了如下成果：①在单一的顶点对之间最短路径重构的时间复杂度为Ｏ（ｎｌｏｇｎ）；②在所有顶点对之间的最短路径重构的时间复杂度为Ｏ（ｎ＾３）；③在带有ｎ／ｌｏｇｎ个处理器的独占读写并行随机访问器上，单一顶点对之间的最短路径重构时间复杂度为Ｏ（（ｌ     

快速分布式数据库数据分布模型求解算法

针对我们提出的以最小代价为目标的分布式数据库数据分布模型，进行适当的数据分组，并对部份组进行排序，使单目运算，双目运算的计算复杂度分别提高了Ｏ（ｎ）和Ｏ（ｎ＾２）。更新运算分解后计算复杂度提高Ｏ（ｎ）。     

像素阵列转化为S树的并行算法及其实现

本文提出了一种从像素阵列到Ｓ树转换的并行法及其在曙光１０００上的具体实现。它是采用叶码和树码相结合的方法对图像进行压缩编码的。这是一种对大型图像的有效表示方法，对图像的存储也十分有效。该算法首先采用模拟遍历线性树的方法把二值图像转换成ＦＤ位置码，然后再把ＦＤ位置码转化成Ｓ树。同以往的树形编码相比Ｓ树具有较高的压缩比、较好的压缩速度。该算法串行时间复杂度是Ｏ（ｎ＾２），用Ｐ个处理器可在Ｏ（ｎ＾２／Ｐ     

Efficient parallel algorithms for distance maps of 2D binary images using an optical bus

Computing a distance map (distance transform) is an operation that converts a 2D image consisting of black and white pixels to an image where each pixel has a value or a pair of coordinates that represents the distance to or location of the nearest black pixel. It is a basic operation in image processing and computer vision fields, and is used for expanding, shrinking, thinning, segmentation, clustering, computing shape, object reconstruction, etc. This paper examines the possibility of implementing the problem of finding a distance map for an image efficiently using an optical bus. The computational model considered is the linear array with a reconfigurable pipelined bus system (LARPBS), which has been introduced recently based on current electronic and optical technologies. It is shown that the problem for an n /spl times/ n image can be implemented in O(log n log log n) bus cycles deterministically or in O(log n) bus cycles with high probability on an LARPBS with n/sup 2/ processors. We also show that the problem can be solved in O(log log n) bus cycles deterministically or in O(l) bus cycles with high probability on an LARPBS with n/sup 3/ processors. Scalability of the algorithms is also discussed briefly. The algorithm compares favorably to the best known parallel algorithms for the same problem in the literature.     

Engineering the Divide-and-Conquer Closest Pair Algorithm

We improve the famous divide-and-conquer algorithm by Bentley and Shamos for the planar closest-pair problem. For n points on the plane, our algorithm keeps the optimal O（n log n） time complexity and, using a circle-packing property, computes at most 7n/2 Euclidean distances, which improves Ge et al.＇s bound of （3n log n）/2 Euclidean distances. We present experimental results of our comparative studies on four different versions of the divide-and-conquer closest pair algorithm and propose two effective heuristics.     

Scalable and efficient parallel algorithms for Euclidean distance transform on the LARPBS model

A parallel algorithm for Euclidean distance transform (EDT) on linear array with reconfigurable pipeline bus system (LARPBS) is presented. For an image with n/spl times/n pixels, the algorithm can complete EDT transform in O(n log n/c(n) log d(n)) time using n/spl middot/d(n)/spl middot/c(n) processors, where c(n) and d(n) are parameters satisfying 1/spl les/c(n)/spl les/n, and 1相似文献   

Euclidean distance transform for binary images on reconfigurable mesh-connected computers.

The distance calculation in an image is a basic operation in computer vision, pattern recognition, and robotics. Several parallel algorithms have been proposed for calculating the Euclidean distance transform (EDT). Recently, Chen and Chuang proposed a parallel algorithm for computing the EDT on mesh-connected SIMD computers (1995). For an nxn image, their algorithm runs in O(n) time on a two-dimensional (2-D) nxn mesh-connected processor array. In this paper, we propose a more efficient parallel algorithm for computing the EDT on a reconfigurable mesh model. For the same problem, our algorithm runs in O(log(2)n) time on a 2-D nxn reconfigurable mesh. Since a reconfigurable mesh uses the same amount of VLSI area as a plain mesh of the same size does when implemented in VLSI, our algorithm improves the result in [3] significantly.     

基因组Translocation排序问题的改进多项式算法

该文给出基因组Transhocation排序问题的一个改进多项式算法，原算法所有存储空间O（n)，时间复杂度为O(n^3)，文中改进算法仍采用O(n)存储空间，时间复杂度为O(n^2logn),具体地，将计算Translocation距离的时间复杂度由O(n^3)改进为O(n^2),将计算Translocation序列的时间复杂度由O(n^3)改进为O(n^2logn).     

三维欧氏距离变换的一种新方法

常见的三维距离变换算法大都是对城市街区、棋盘等二维近似欧氏距离变换算法的三维扩展,得到的依然是近似欧氏距离.提出一种新的三维欧氏距离变换算法,可以得到完全欧氏距离,时间复杂度为O(n3logn).将该算法应用于三维医学CT图像内部软组织的显示,取得了较好的效果.     

基于围线分层扫描的完全欧氏距离变换算法

围线扫描欧氏距离变换算法是一种快速的完全欧氏距离变换算法,其时间复杂度达到最优,但需在围线区域进行全局搜索,计算时间并未优化。针对此问题,提出了一种基 于围线分层扫描的完全欧氏距离算法。该算法首先根据中心像素的围线性质对二值图像像素点进行重新分类,然后按照围线区域像素与中心像素的空间关系,对中心像素的围线区 域进行分层搜索,并给出了搜索的终止条件。该算法保持了最优的时间复杂度,可通过定量分析单个像素的计算时间来证明其计算时间已得到优化。实验结果表明,该算法能够得到 准确的欧氏距离图像,且运行速度快。     

基于围线扫描的快速完全欧氏距离变换算法

欧几里德距离变换（EDT）是为由黑白像素构成的二值图像中所有像素找到距离其最近的黑色像素,并计算它们之间的欧几里德距离,目前广泛地应用于图像分析和计算机视觉等领域.本文采用基于围线扫描的思想,提出了一个在二值图像中进行完全欧氏距离变换的算法.算法首先将二值图像中的像素进行分类,对那些本身既不是特征像素且其4-邻域内也没有特征像素的点作上标记,然后对这些标记的像素自内向外进行围线扫描,搜索与它最近的黑点并计算它们的欧氏距离.算法能够计算精确的欧氏距离.同时对算法的时间复杂度进行了简单的分析,并给出了程序实现中得到的一些实验数据,结果表明该算法运算速度快,时空需求在当前的硬件环境下令人满意,是一种有效的和有着巨大实际应用价值的距离变换算法.     

Efficient EREW PRAM algorithms for parentheses-matching

We present four polylog-time parallel algorithms for matching parentheses on an exclusive-read and exclusive-write (EREW) parallel random-access machine (PRAM) model. These algorithms provide new insights into the parentheses-matching problem. The first algorithm has a time complexity of O(log² n) employing O(n/(log n)) processors for an input string containing n parentheses. Although this algorithm is not cost-optimal, it is extremely simple to implement. The remaining three algorithms, which are based on a different approach, achieve O(log n) time complexity in each case, and represent successive improvements. The second algorithm requires O(n) processors and working space, and it is comparable to the first algorithm in its ease of implementation. The third algorithm uses O(n/(log n)) processors and O(n log n) space. Thus, it is cost-optimal, but uses extra space compared to the standard stack-based sequential algorithm. The last algorithm reduces the space complexity to O(n) while maintaining the same processor and time complexities. Compared to other existing time-optimal algorithms for the parentheses-matching problem that either employ extensive pipelining or use linked lists and comparable data structures, and employ sorting or a linked list ranking algorithm as subroutines, the last two algorithms have two distinct advantages. First, these algorithms employ arrays as their basic data structures, and second, they do not use any pipelining, sorting, or linked list ranking algorithms