Optimal Computing the Chessboard Distance Transform on Parallel Processing Systems

Thedistance transform(DT) is an image computation tool which can be used to extract the information about the shape and the position of the foreground pixels relative to each other. It converts a binary image into a grey-level image, where each pixel has a value corresponding to the distance to the nearest foreground pixel. The time complexity for computing the distance transform is fully dependent on the different distance metrics. Especially, the more exact the distance transform is, the worse execution time reached will be. Nowadays, quite often thousands of images are processed in a limited time. It seems quite impossible for a sequential computer to do such a computation for the distance transform in real time. In order to provide efficient distance transform computation, it is considerably desirable to develop a parallel algorithm for this operation. In this paper, based on the diagonal propagation approach, we first provide anO(N²) time sequential algorithm to compute thechessboard distance transform(CDT) of anN×Nimage, which is a DT using the chessboard distance metrics. Based on the proposed sequential algorithm, the CDT of a 2D binary image array of sizeN×Ncan be computed inO(logN) time on the EREW PRAM model usingO(N²/logN) processors,O(log logN) time on the CRCW PRAM model usingO(N²/log logN) processors, andO(logN) time on the hypercube computer usingO(N²/logN) processors. Following the mapping as proposed by Lee and Horng, the algorithm for the medial axis transform is also efficiently derived. The medial axis transform of a 2D binary image array of sizeN×Ncan be computed inO(logN) time on the EREW PRAM model usingO(N²/logN) processors,O(log logN) time on the CRCW PRAM model usingO(N²/log logN) processors, andO(logN) time on the hypercube computer usingO(N²/logN) processors. The proposed parallel algorithms are composed of a set of prefix operations. In each prefix operation phase, only increase (add-one) operation and minimum operation are employed. So, the algorithms are especially efficient in practical applications.     

A more efficient algorithm for the min-plus multiplication

The (min, + ) product C of two n × n matrices A and B is defined as C _ij = min_1≦k≦n A _ik + B _kj . This paper presents an algorithm to compute the (min, +) product of two n × n matrices. The algorithm follows the approach described by Fredman, but is faster than Fredman's own algorithm: its time complexity is either O(n ³/√log₂ n) or even O(n ^2.5√log₂ n), if one adheres to the uniform-cost RAM model faithfully.

This result implies the existence of O(n ³/√log₂ n) algorithms for the problems that (min, +) matrix multiplication is equivalent to, such as the all-pairs shortest paths problem.

As the presented algorithm uses operations on sets, the formal analysis of its time complexity raises a few interesting questions about the applicability of the standard RAM complexity model.     

An optimal parallel algorithm for triangulating a set of points in the plane

This paper presents an optimal parallel algorithm for triangulating an arbitrary set ofn points in the plane. The algorithm runs inO(logn) time usingO(n) space andO(_n) processors on a Concurrent-Read, Exclusive-Write Parallel RAM model (CREW PRAM). The parallel lower bound on triangulation is (logn) time so the best possible linear speedup has been achieved. A parallel divide-and-conquer technique of subdividing a problem into subproblems is employed.     

Improved time and space bounds for Boolean matrix multiplication

Summary Using modular arithmetic we obtain the following improved bounds on the time and space complexities for n × n Boolean matrix multiplication: O(n ^log ₂ ⁷ lognlogloglognloglogloglogn) bit operations and O(n ²loglog n) bits of storage on a logarithmic cost RAM having no multiply or divide instruction; O(n ^log ₂ ⁷(logn)^2–1/2log ₂ ⁷(loglog n)^1/2log ₂ ^7–1) bit operations and O(n ²log n) bits of storage on a RAM which can use indirect addressing for table lookups. The first algorithm can be realized as a Boolean circuit with O(n ^log ₂ ⁷lognlogloglognloglogloglogn) gates. Whenever n×n arithmetic matrix multiplication can be performed in less than O(n ^log ₂ ⁷) arithmetic operations, our results have corresponding improvements.This work was supported in part by the Office of Naval Research under contract N00014-67-0204-0063, by the National Research Council of Canada under grant A4307, and by the National Science Foundation under grants MCS76-17321 and GJ-43332     

Efficient parallel and sequential algorithms for 4-coloring perfect planar graphs

We present an efficient algorithm for 4-coloring perfect planar graphs. The best previously known algorithm for this problem takesO(n ^3/2) sequential time, orO(log⁴ n) parallel time withO(n³) processors. The sequential implementation of our algorithm takesO(n logn) time. The parallel implementation of our algorithm takesO(log³ n) time withO(n) processors on a PRAM.     

Efficient parallel and sequential algorithms for 4-coloring perfect planar graphs

We present an efficient algorithm for 4-coloring perfect planar graphs. The best previously known algorithm for this problem takesO(n ^3/2) sequential time, orO(log⁴ n) parallel time withO(n³) processors. The sequential implementation of our algorithm takesO(n logn) time. The parallel implementation of our algorithm takesO(log³ n) time withO(n) processors on a PRAM.

     

Towards optimal range medians

We consider the following problem: Given an unsorted array of n elements, and a sequence of intervals in the array, compute the median in each of the subarrays defined by the intervals. We describe a simple algorithm which needs O(nlogk+klogn) time to answer k such median queries. This improves previous algorithms by a logarithmic factor and matches a comparison lower bound for k=O(n). The space complexity of our simple algorithm is O(nlogn) in the pointer machine model, and O(n) in the RAM model. In the latter model, a more involved O(n) space data structure can be constructed in O(nlogn) time where the time per query is reduced to O(logn/loglogn). We also give efficient dynamic variants of both data structures, achieving O(log²n) query time using O(nlogn) space in the comparison model and O((logn/loglogn)²) query time using O(nlogn/loglogn) space in the RAM model, and show that in the cell-probe model, any data structure which supports updates in O(log^O(1)n) time must have Ω(logn/loglogn) query time.Our approach naturally generalizes to higher-dimensional range median problems, where element positions and query ranges are multidimensional—it reduces a range median query to a logarithmic number of range counting queries.     

Labeling Schemes for Dynamic Tree Networks

Distance labeling schemes are composed of a marker algorithm for labeling the vertices of a graph with short labels, coupled with a decoder algorithm allowing one to compute the distance between any two vertices directly from their labels (without using any additional information). As applications for distance labeling schemes concern mainly large and dynamically changing networks, it is of interest to study distributed dynamic labeling schemes. The current paper considers the problem on dynamic trees, and proposes efficient distributed schemes for it. The paper first presents a labeling scheme for distances in the dynamic tree model, with amortized message complexity O(log² n) per operation, where n is the size of the tree at the time the operation takes place. The protocol maintains O(log² n) bit labels. This label size is known to be optimal even in the static scenario. A more general labeling scheme is then introduced for the dynamic tree model, based on extending an existing static tree labeling scheme to the dynamic setting. The approach fits a number of natural tree functions, such as distance, separation level, and flow. The main resulting scheme incurs an overhead of an O(log n) multiplicative factor in both the label size and amortized message complexity in the case of dynamically growing trees (with no vertex deletions). If an upper bound on n is known in advance, this method yields a different tradeoff, with an O(log² n/log log n) multiplicative overhead on the label size but only an O(log n/log log n) overhead on the amortized message complexity. In the fully dynamic model the scheme also incurs an increased additive overhead in amortized communication, of O(log² n) messages per operation.     

An optimal speed-up parallel algorithm for triangulating simplicial point sets in space

Previous research on developing parallel triangulation algorithms concentrated on triangulating planar point sets.O(log³ n) running time algorithms usingO(n) processors have been developed in Refs. 1 and 2. Atallah and Goodrich⁽³⁾ presented a data structure that can be viewed as a parallel analogue of the sequential plane-sweeping paradigm, which can be used to triangulate a planar point set inO(logn loglogn) time usingO(n) processors. Recently Merks⁽⁴⁾ described an algorithm for triangulating point sets which runs inO(logn) time usingO(n) processors, and is thus optimal. In this paper we develop a parallel algorithm for triangulating simplicial point sets in arbitrary dimensions based on the idea of the sequential algorithm presented in Ref. 5. The algorithm runs inO(log² n) time usingO(n/logn) processors. The algorithm hasO(n logn) as the product of the running time and the number of processors; i.e., an optimal speed-up.     

Fast computation of smallest enclosing circle with center on a query line segment

Here we propose an efficient algorithm for computing the smallest enclosing circle whose center is constrained to lie on a query line segment. Our algorithm preprocesses a given set of n points P={p₁,p₂,…,pn} such that for any query line or line segment L, it efficiently locates a point c on L that minimizes the maximum distance among the points in P from c. Roy et al. [S. Roy, A. Karmakar, S. Das, S.C. Nandy, Constrained minimum enclosing circle with center on a query line segment, in: Proc. of the 31st Mathematical Foundation of Computer Science, 2006, pp. 765-776] have proposed an algorithm that solves the query problem in O(log²n) time using O(nlogn) preprocessing time and O(n) space. Our algorithm improves the query time to O(logn); but the preprocessing time and space complexities are both O(n²).     

虫孔路由Mesh上的连通分量算法及其应用

用倍增技术在带有Wormhole路由技术的n×n二维网孔机器上提出了时间复杂度为O(log²n)的连通分量和传递闭包并行算法,并在此基础上提出了一个时间复杂度为O(log³n)的最小生成树并行算法.这些都改进了Store-and-Forward路由技术下的时间复杂度下界O(n).同其他运行在非总线连接分布式存储并行计算机上的算法相比,此连通分量和传递闭包算法的时间复杂度是最优的.     

Sieve algorithms for perfect power testing

A positive integern is a perfect power if there exist integersx andk, both at least 2, such thatn=x ^k . The usual algorithm to recognize perfect powers computes approximatekth roots forklog ₂ n, and runs in time O(log³ n log log logn).First we improve this worst-case running time toO(log³ n) by using a modified Newton's method to compute approximatekth roots. Parallelizing this gives anNC ² algorithm.Second, we present a sieve algorithm that avoidskth-root computations by seeing if the inputn is a perfectkth power modulo small primes. Ifn is chosen uniformly from a large enough interval, the average running time isO(log² n).Third, we incorporate trial division to give a sieve algorithm with an average running time ofO(log² n/log² logn) and a median running time ofO(logn).The two sieve algorithms use a precomputed table of small primes. We give a heuristic argument and computational evidence that the largest prime needed in this table is (logn)^1+O(1); assuming the Extended Riemann Hypothesis, primes up to (logn)^2+O(1) suffice. The table can be computed in time roughly proportional to the largest prime it contains.We also present computational results indicating that our sieve algorithms perform extremely well in practice.This work forms part of the second author's Ph.D. thesis at the University of Wisconsin-Madison, 1991. This research was sponsored by NSF Grants CCR-8552596 and CCR-8504485.     

Visibility between two edges of a simple polygon

One of the most recurring themes in many computer applications such as graphics automated cartography, image processing and robotics is the notion of visibility. We are concerned with the visibility between two edges of a simplen-vertex polygon. Four natural definitions of edge-to-edge visibility are proposed. There existO(nlogn) algorithms and complicatedO(nlog logn) algorithms to solve this problem partially and indirectly. A linear running time, and thus optimal algorithm is presented to determine edge-to-edge visibility under any of the four definitions. This simple, efficient, and direct algorithm without computing the triangulation of the simple polygon also identifies the visibility region if it exists.     

网格多处理机的一种改进的子网分配算法

子网分配问题是指识别并分配一个空闲的、满足指定大小要求的节点机.首先,提出了网格结构中一种新的具有O(N²_a·1og₂N_a)时间复杂度的空闲子网搜索算法,它优于现有的O(N³_a)时间复杂度的搜索算法.然后,用该算法对基于保留因子的最佳匹配类子网分配算法——RF(reservation factor)算法进行了改进,得到了     

Fast algorithms for the dominating set problem on permutation graphs

AnO(n log logn) (resp.O(n² log² n)) algorithm is presented to solve the minimum cardinality (resp. weight) dominating set problem on permutation graphs, assuming the input is a permutation. The best-known previous algorithm was given by FÄrber and Keil, where they use dynamic programming to get anO(n² (resp.O(n³)) algorithm. Our improvement is based on the following three factors: (1) an observation on the order among the intermediate terms in the dynamic programming, (2) a new construction formula for the intermediate terms, and (3) efficient data structures for manipulating these terms.This research was supported in part by the National Science Foundation under Grant CCR-8905415 to Northwestern University.     

The complexity of on-line simulations between multidimensional turing machines and random access machines

To study different implementations of arrays, we present four results on the time complexities of on-line simulations between multidimensional Turing machines and random access machines (RAMs). First, everyd-dimensional Turing machine of time complexityt can be simulated by a log-cost RAM running inO(t(logt)^1–(1/d)(log logt)^1/d) time. Second, everyd-dimensional Turing machine of time complexityt can be simulated by a unit-cost RAM running inO(t/(logt)^1/d) time, provided that the input length iso(t/(logt)^1/d). Third, there is a log-cost RAMR of time complexityO(n), wheren is the input length, such that, for anyd-dimensional Turing machineM that simulatesR on-line,M requires (n ^{1 + (1/d)})/(logn(log logn)^{1 + (1/d)})) time. Fourth, every unit-cost RAM of time complexityt can be simulated by ad-dimensional Turing machine inO(t ²(logt)^1/2) time ifd = 2, and inO(t ²) time ifd 3. This result uses the weight-balanced trees of Nievergelt and Reingold.This paper was prepared while M. C. Loui was visiting the National Science Foundation in Washington, DC, and the Institute for Advanced Computer Studies, University of Maryland, College Park, MD. The views, opinions, and conclusions in this paper are those of the authors and should not be construed as an official position of the National Science Foundation, Department of Defense, U.S. Air Force, or any other U.S. government agency. The research of M. C. Loui was supported by the National Science Foundation under Grant CCR-8922008.     

PRAM和LARPBS模型上有向序列翻转距离并行算法

分别在两种重要并行计算模型中给出计算有向基因组排列的反转距离新的并行算法.基于Hannenhalli和Pevzner理论,分3个主要部分设计并行算法:构建断点图、计算断点图中圈数、计算断点图中障碍的数目.在CREW-PRAM模型上,算法使用O(n²)处理器,时间复杂度为O(log²n);在基于流水光总线的可重构线性阵列系统(linear array with a reconfigurable pipelined bus system, LARPBS)模型上,算法使用O(n³)处理器,计算时间复杂度为O(logn).     

On Parallel Selection and Searching in Partial Orders: Sorted Matrices

Parallel algorithms for the problems of selection and searching on sorted matrices are formulated. The selection algorithm takesO(lognlog lognlog*n) time withO(n/lognlog*n) processors on an EREW PRAM. This algorithm can be generalized to solve the selection problem on a set of sorted matrices. The searching algorithm takesO(log logn) time withO(n/log logn) processors on a Common CRCW PRAM, which is optimal. We show that no algorithm using at mostnlog^cnprocessors,c≥ 1, can solve the matrix search problem in time faster than Ω(log logn) and that Ω(logn) steps are needed to solve this problem on any model that does not allow concurrent writes.     

An efficient parallel algorithm for shortest paths in planar layered digraphs

Computing shortest paths in a directed graph has received considerable attention in the sequential RAM model of computation. However, developing a polylog-time parallel algorithm that is close to the sequential optimal in terms of the total work done remains an elusive goal. We present a first step in this direction by giving efficient parallel algorithms for shortest paths in planar layered digraphs.We show that these graphs admit special kinds of separators calledone- way separators which allow the paths in the graph to cross it only once. We use these separators to give divide- and -conquer solutions to the problem of finding the shortest paths between any two vertices. We first give a simple algorithm that works in the CREW model and computes the shortest path between any two vertices in ann-node planar layered digraph in timeO(log² n) usingn/logn processors. We then use results of Aggarwal and Park [1] and Atallah [4] to improve the time bound toO(log² n) in the CREW model andO(logn log logn) in the CREW model. The processor bounds still remain asn/logn for the CREW model andn/log logn for the CRCW model.Support for the first and third authors was provided in part by a National Science Foundation Presidential Young Investigator Award CCR-9047466 with matching funds from IBM, by NSF Research Grant CCR-9007851, by Army Research Office Grant DAAL03-91-G-0035, and by the Office of Naval Research and the Advanced Research Projects Agency under Contract N00014-91-J-4052, ARPA, Order 8225. Support for the second author was provided in part by NSF Research Grant CCR-9007851, by Army Research Office Grant DAAL03-91-G-0035, and by the Office of Naval Research and the Advanced Research Projects Agency under Contract N00014-91-J-4052 and ARPA Order 8225.     

Parallel construction of a suffix tree with applications

Many string manipulations can be performed efficiently on suffix trees. In this paper a CRCW parallel RAM algorithm is presented that constructs the suffix tree associated with a string ofn symbols inO(logn) time withn processors. The algorithm requires Θ(n ²) space. However, the space needed can be reduced toO(n ^1+?) for any 0< ? ≤1, with a corresponding slow-down proportional to 1/?. Efficient parallel procedures are also given for some string problems that can be solved with suffix trees.