共查询到20条相似文献,搜索用时 0 毫秒
1.
We present parallel algorithms for some fundamental problems in computational geometry which have a running time ofO(logn) usingn processors, with very high probability (approaching 1 asn → ∞). These include planar-point location, triangulation, and trapezoidal decomposition. We also present optimal algorithms for three-dimensional maxima and two-set dominance counting by an application of integer sorting. Most of these algorithms run on a CREW PRAM model and have optimal processor-time product which improve on the previously best-known algorithms of Atallah and Goodrich [5] for these problems. The crux of these algorithms is a useful data structure which emulates the plane-sweeping paradigm used for sequential algorithms. We extend some of the techniques used by Reischuk [26] and Reif and Valiant [25] for flashsort algorithm to perform divide and conquer in a plane very efficiently leading to the improved performance by our approach. 相似文献
2.
We present parallel algorithms for some fundamental problems in computational geometry which have a running time ofO(logn) usingn processors, with very high probability (approaching 1 asn ). These include planar-point location, triangulation, and trapezoidal decomposition. We also present optimal algorithms for three-dimensional maxima and two-set dominance counting by an application of integer sorting. Most of these algorithms run on a CREW PRAM model and have optimal processor-time product which improve on the previously best-known algorithms of Atallah and Goodrich [5] for these problems. The crux of these algorithms is a useful data structure which emulates the plane-sweeping paradigm used for sequential algorithms. We extend some of the techniques used by Reischuk [26] and Reif and Valiant [25] for flashsort algorithm to perform divide and conquer in a plane very efficiently leading to the improved performance by our approach.This is a substantially revised version of the paper that appeared as Optimal Randomized Parallel Algorithms for Computational Geometry in theProceedings of the 16th International Conference on Parallel Processing, St. Charles, Illinois, August 1987.This research was supported by DARPA/ARO Contract DAAL03-88-K-0195, Air Force Contract AFOSR-87-0386, DARPA/ISTO Contracts N00014-88-K-0458 and N00014-91-J-1985, and by NASA Subcontract 550-63 of Primecontract NAS5-30428. 相似文献
3.
We provide optimal parallel solutions to several link-distance problems set in trapezoided rectilinear polygons. All our main parallel algorithms are deterministic and designed to run on the exclusive read exclusive write parallel random access machine (EREW PRAM). LetP be a trapezoided rectilinear simple polygon withn vertices. InO(logn) time usingO(n/logn) processors we can optimally compute:
- Minimum réctilinear link paths, or shortest paths in theL 1 metric from any point inP to all vertices ofP.
- Minimum rectilinear link paths from any segment insideP to all vertices ofP.
- The rectilinear window (histogram) partition ofP.
- Both covering radii and vertex intervals for any diagonal ofP.
- A data structure to support rectilinear link-distance queries between any two points inP (queries can be answered optimally inO(logn) time by uniprocessor).
4.
Olariu S. Schwing J.L. Zhang J. 《Parallel and Distributed Systems, IEEE Transactions on》1992,3(3):364-374
A family of intervals on the real line provides a natural model for a vast number of scheduling and VLSI problems. Recently, a number of parallel algorithms to solve a variety of practical problems on such a family of intervals have been proposed in the literature. The authors develop computational tools and show how they can be used for the purpose of devising cost-optimal parallel algorithms for a number of interval-related problems, including finding a largest subset of pairwise nonoverlapping intervals, a minimum dominating subset of intervals, along with algorithms to compute the shortest path between a pair of intervals and, based on the shortest path, a parallel algorithm to find the center of the family of intervals. More precisely, with an arbitrary family of n intervals as input, all the algorithms run in O (log n ) time using O (n ) processors in the EREW-PRAM model of computation 相似文献
5.
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.The research of R. Cole was supported in part by NSF Grants CCR-8702271, CCR-8902221, and CCR-8906949, by ONR Grant N00014-85-K-0046, and by a John Simon Guggenheim Memorial Foundation fellowship. M. T. Goodrich's research was supported by the National Science Foundation under Grant CCR-8810568 and by the National Science Foundation and DARPA under Grant CCR-8908092. 相似文献
6.
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. 相似文献
7.
Eliezer Dekel Shietung Peng S. Sitharma Lyengar 《International journal of parallel programming》1986,15(6):503-528
We present parallel algorithms for constructing and maintaining balancedm-way search trees. These parallel algorithms have time complexity O(1) for ann processors configuration. The formal correctness of the algorithms is given in detail. 相似文献
8.
Hayashi T. Nakano K. Olariu S. 《Parallel and Distributed Systems, IEEE Transactions on》1998,9(12):1153-1166
Consider a set P of points in the plane sorted by the x-coordinate. A point p in P is said to be a proximate point if there exists a point q on the x-axis such that p is the closest point to q over all points in P. The proximate point problem is to determine all the proximate points in P. Our main contribution is to propose optimal parallel algorithms for solving instances of size n of the proximate points problem. We begin by developing a work-time optimal algorithm running in O(log log n) time and using n/loglogn Common-CRCW processors. We then go on to show that this algorithm can be implemented to run in O(log n) time using n/logn EREW processors. In addition to being work-time optimal, our EREW algorithm turns out to also be time-optimal. Our second main contribution is to show that the proximate points problem finds interesting, and quite unexpected, applications to digital geometry and image processing. As a first application, we present a work-time optimal parallel algorithm for finding the convex hull of a set of n points in the plane sorted by x-coordinate; this algorithm runs in O(log log n) time using n/logn Common-CRCW processors. We then show that this algorithm can be implemented to run in O(log n) time using n/logn EREW processors. Next, we show that the proximate points algorithms afford us work-time optimal (resp, time-optimal) parallel algorithms for various fundamental digital geometry and image processing problems 相似文献
9.
S. G. Akl 《Computing》1984,32(1):1-11
Nonlinear equations are considered, where some input parameters are subjected to errors. By a class of monotone enclosing methods sequences of intervals are constructed, containing for each value of the perturbation parameter at least one zero of the problem. In finite dimensional spaces concrete realizations are given, e. g. of Newton-, Regula falsi- and Jacobi-Newton-type. 相似文献
10.
Parallel updates of minimum spanning trees (MSTs) have been studied in the past. These updates allowed a single change in the underlying graph, such as a change in the cost of an edge or an insertion of a new vertex. Multiple update problems for MSTs are concerned with handling more than one such change. In the sequential case multiple update problems may be solved using repeated applications of an efficient algorithm for a single update. However, for efficiency reasons, parallel algorithms for multiple update problems must consider all changes to the underlying graph simultaneously. In this paper we describe parallel algorithms for updating an MST whenk new vertices are inserted or deleted in the underlying graph, when the costs ofk edges are changed, or whenk edge insertions and deletions are performed. For multiple vertex insertion update, our algorithm achieves time and processor bounds ofO(log n·logk) and nk/(logn·logk), respectively, on a CREW parallel random access machine. These bounds are optimal for dense graphs. A novel feature of this algorithm is a transformation of the previous MST andk new vertices to a bipartite graph which enables us to obtain the above-mentioned bounds. 相似文献
11.
The knapsack problem is well known to be NP-complete. Due to its importance in cryptosystem and in number theory, in the past
two decades, much effort has been made in order to find techniques that could lead to practical algorithms with reasonable
running time. This paper proposes a new parallel algorithm for the knapsack problem where the optimal merging algorithm is
adopted. The proposed algorithm is based on anEREW-SIMD machine with shared memory. It is proved that the proposed algorithm is both optimal and the first without memory conflicts
algorithm for the knapsack problem. The comparisons of algorithm performance show that it is an improvement over the past
researches. 相似文献
12.
13.
《Computers & Mathematics with Applications》2007,53(10):1605-1614
Population initialization is a crucial task in evolutionary algorithms because it can affect the convergence speed and also the quality of the final solution. If no information about the solution is available, then random initialization is the most commonly used method to generate candidate solutions (initial population). This paper proposes a novel initialization approach which employs opposition-based learning to generate initial population. The conducted experiments over a comprehensive set of benchmark functions demonstrate that replacing the random initialization with the opposition-based population initialization can accelerate convergence speed. 相似文献
14.
15.
Feng-Nan Hwang 《Computer Methods in Applied Mechanics and Engineering》2007,196(8):1603-1611
We propose and test a new class of two-level nonlinear additive Schwarz preconditioned inexact Newton algorithms (ASPIN). The two-level ASPIN combines a local nonlinear additive Schwarz preconditioner and a global linear coarse preconditioner. This approach is more attractive than the two-level method introduced in [X.-C. Cai, D.E. Keyes, L. Marcinkowski, Nonlinear additive Schwarz preconditioners and applications in computational fluid dynamics, Int. J. Numer. Methods Fluids, 40 (2002), 1463-1470], which is nonlinear on both levels. Since the coarse part of the global function evaluation requires only the solution of a linear coarse system rather than a nonlinear coarse system derived from the discretization of original partial differential equations, the overall computational cost is reduced considerably. Our parallel numerical results based on an incompressible lid-driven flow problem show that the new two-level ASPIN is quite scalable with respect to the number of processors and the fine mesh size when the coarse mesh size is fine enough, and in addition the convergence is not sensitive to the Reynolds numbers. 相似文献
16.
《Journal of Parallel and Distributed Computing》1988,5(4):421-437
The current ferment in parallel computer architecture has exacerbated the already large problems in developing and testing parallel algorithms. Although only experimentation will identify effective designs, the variety of computing paradigms has precluded development of the (necessary) general environment for parallel programming. We propose an environment design system where design specification is divorced from implementation. Because the design system, Polylith, provides the communication structure of a parallel computation, the computation's individual tasks can be written in one of several relatively portable sequential languages. 相似文献
17.
18.
Santiago Muelas José-María Peña Antonio LaTorre Víctor Robles 《Soft Computing - A Fusion of Foundations, Methodologies and Applications》2010,15(4):713-720
Estimation of distribution algorithms (EDAs) are one of the most promising paradigms in today’s evolutionary computation.
In this field, there has been an incipient activity in the so-called parallel estimation of distribution algorithms (pEDAs).
One of these approaches is the distributed estimation of distribution algorithms (dEDAs). This paper introduces a new initialization
mechanism for each of the populations of the islands based on the Voronoi cells. To analyze the results, a series of different
experiments using the benchmark suite for the special session on Real-parameter Optimization of the IEEE CEC 2005 conference
has been carried out. The results obtained suggest that the Voronoi initialization method considerably improves the performance
obtained from a traditional uniform initialization. 相似文献
19.
The fact that conventional line-drawing algorithms, when applied directly on parallel machines, can lead to very inefficient codes is addressed. It is suggested that instead of modifying an existing algorithm for a parallel machine, a more efficient implementation can be produced by going back to the invariants in the definition. Popular line-drawing algorithms are compared with two alternatives; distance to a line (a point is on the line if sufficiently close to it) and intersection with a line (a point on the line if an intersection point). For massively parallel single-instruction-multiple-data (SIMD) machines (with thousands of processors and up), the alternatives provide viable line-drawing algorithms. Because of the pixel-per-processor mapping, their performance is independent of the line length orientation 相似文献
20.
目前使用遗传算法设计鲁棒控制器时, 都要人为地给定变量搜索空间. 当变量区域不确定时, 采用自适应并行遗传算法设计出最优鲁棒控制器, 该方法根据当前搜索到的各种群最优个体的分布情况, 运用概率统计理论求出变量区域的最小方差无偏估计, 不断缩小不确定的变量搜索区域, 从而逐步达到最优, 并且考虑了种群个体适应度对算法中交叉概率和变异概率的影响. 该方法能设计出简单正则、阶数低的最优鲁棒控制器, 而且仿真结果表明, 这些控制器有效地避免了局部最优, 提高了算法的寻优精度和收敛速度. 相似文献