首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到10条相似文献,搜索用时 140 毫秒
1.
LetP be a set ofl points in 3-space, and letF be a set ofm opaque rectangular faces in 3-space with sides parallel tox- ory-axis. We present anO(n logn) time andO(n) space algorithm for determining all points inP which are visible from a viewpoint at (0,0,), wheren=l+m. We also present anO(n logn+k) time andO(n) space algorithm for the hidden-line elimination problem for the orthogonal polyhedra together with a viewpoint at (0,0,), wheren is the number of vertices of the polyhedra andk is the number of edge intersections in the projection plane.  相似文献   

2.
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 2 n, and runs in time O(log3 n log log logn).First we improve this worst-case running time toO(log3 n) by using a modified Newton's method to compute approximatekth roots. Parallelizing this gives anNC 2 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(log2 n).Third, we incorporate trial division to give a sieve algorithm with an average running time ofO(log2 n/log2 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.  相似文献   

3.
We give the first efficient parallel algorithms for solving the arrangement problem. We give a deterministic algorithm for the CREW PRAM which runs in nearly optimal bounds ofO (logn log* n) time andn 2/logn processors. We generalize this to obtain anO (logn log* n)-time algorithm usingn d /logn processors for solving the problem ind dimensions. We also give a randomized algorithm for the EREW PRAM that constructs an arrangement ofn lines on-line, in which each insertion is done in optimalO (logn) time usingn/logn processors. Our algorithms develop new parallel data structures and new methods for traversing an arrangement.This work was supported by the National Science Foundation, under Grants CCR-8657562 and CCR-8858799, NSF/DARPA under Grant CCR-8907960, and Digital Equipment Corporation. A preliminary version of this paper appeared at the Second Annual ACM Symposium on Parallel Algorithms and Architectures [3].  相似文献   

4.
The Rectilinear Steiner Arborescence (RSA) problem is Given a setN ofn nodes lying in the first quadrant of E2, find the shortest directed tree rooted at the origin, containing all nodes inN, and composed solely of horizontal and vertical arcs oriented only from left to right or from bottom to top. In this paper we investigate many fundamental properties of the RSA problem, propose anO(n logn)-time heuristic algorithm giving an RSA whose length has an upper bound of twice that of the minimum length RSA, and show that a polynomial-time algorithm that was earlier reported in the literature for this problem is incorrect.  相似文献   

5.
Distance transforms are an important computational tool for the processing of binary images. For ann ×n image, distance transforms can be computed in time (n) on a mesh-connected computer and in polylogarithmic time on hypercube related structures. We investigate the possibilities of computing distance transforms in polylogarithmic time on the pyramid computer and the mesh of trees. For the pyramid, we obtain a polynomial lower bound using a result by Miller and Stout, so we turn our attention to the mesh of trees. We give a very simple (logn) algorithm for the distance transform with respect to theL 1-metric, an (log2 n) algorithm for the transform with respect to theL -metric, and find that the Euclidean metric is much more difficult. Based on evidence from number theory, we conjecture the impossibility of computing the Euclidean distance transform in polylogarithmic time on a mesh of trees. Instead, we approximate the distance transform up to a given error. This works for anyL k -metric and takes time (log3 n).This research was supported by the Deutsche Forschungsgemeinschaft under Grant Al 253/1-1, Schwerpunktprogramm Datenstrukturen und effiziente Algorithmen.  相似文献   

6.
Given an n-node edge-weighted graph and a subset of k terminal nodes, the NP-hard (weighted) Steiner tree problem is to compute a minimum-weight tree which spans the terminals. All the known algorithms for this problem which improve on trivial O(1.62 n )-time enumeration are based on dynamic programming, and require exponential space. Motivated by the fact that exponential-space algorithms are typically impractical, in this paper we address the problem of designing faster polynomial-space algorithms. Our first contribution is a simple O((27/4) k n O(logk))-time polynomial-space algorithm for the problem. This algorithm is based on a variant of the classical tree-separator theorem: every Steiner tree has a node whose removal partitions the tree in two forests, containing at most 2k/3 terminals each. Exploiting separators of logarithmic size which evenly partition the terminals, we are able to reduce the running time to $O(4^{k}n^{O(\log^{2} k)})$ . This improves on trivial enumeration for roughly k<n/3, which covers most of the cases of practical interest. Combining the latter algorithm (for small k) with trivial enumeration (for large k) we obtain a O(1.59 n )-time polynomial-space algorithm for the weighted Steiner tree problem. As a second contribution of this paper, we present a O(1.55 n )-time polynomial-space algorithm for the cardinality version of the problem, where all edge weights are one. This result is based on a improved branching strategy. The refined branching is based on a charging mechanism which shows that, for large values of k, convenient local configurations of terminals and non-terminals exist. The analysis of the algorithm relies on the Measure & Conquer approach: the non-standard measure used here is a linear combination of the number of nodes and number of non-terminals. Using a recent result in Nederlof (International colloquium on automata, languages and programming (ICALP), pp. 713–725, 2009), the running time can be reduced to O(1.36 n ). The previous best algorithm for the cardinality case runs in O(1.42 n ) time and exponential space.  相似文献   

7.
S. Arya  M. Smid 《Algorithmica》1997,17(1):33-54
LetS be a set ofn points in ℝ d and lett>1 be a real number. At-spanner forS is a graph having the points ofS as its vertices such that for any pairp, q of points there is a path between them of length at mostt times the Euclidean distance betweenp andq. An efficient implementation of a greedy algorithm is given that constructs at-spanner having bounded degree such that the total length of all its edges is bounded byO (logn) times the length of a minimum spanning tree forS. The algorithm has running timeO (n log d n). Applying recent results of Das, Narasimhan, and Salowe to thist-spanner gives anO(n log d n)-time algorithm for constructing at-spanner having bounded degree and whose total edge length is proportional to the length of a minimum spanning tree forS. Previously, noo(n 2)-time algorithms were known for constructing at-spanner of bounded degree. In the final part of the paper, an application to the problem of distance enumeration is given. This work was supported by the ESPRIT Basic Research Actions Program, under Contract No. 7141 (Project ALCOM II).  相似文献   

8.
We present an optimal parallel algorithm for computing a cycle separator of ann-vertex embedded planar undirected graph inO(logn) time onn/logn processors. As a consequence, we also obtain an improved parallel algorithm for constructing a depth-first search tree rooted at any given vertex in a connected planar undirected graph in O(log2 n) time on n/logn processors. The best previous algorithms for computing depth-first search trees and cycle separators achieved the same time complexities, but withn processors. Our algorithms run on a parallel random access machine that permits concurrent reads and concurrent writes in its shared memory and allows an arbitrary processor to succeed in case of a write conflict.A preliminary version of this paper appeared as Improved Parallel Depth-First Search in Undirected Planar Graphs in theProceedings of the Third Workshop on Algorithms and Data Structures, 1993, pp. 407–420.Supported in part by NSF Grant CCR-9101385.  相似文献   

9.
Thek-compaction problem arises whenk out ofn cells in an array are non-empty and the contents of these cells must be moved to the firstk locations in the array. Parallel algorithms fork-compaction have obvious applications in processor allocation and load balancing;k-compaction is also an important subroutine in many recently developed oped parallel algorithms. We show that any EREW PRAM that solves thek-compaction problem requires time, even if the number of processors is arbitrarily large andk=2. On the CREW PRAM, we show that everyn-processor algorithm fork-compaction problem requires (log logn) time, even ifk=2. Finally, we show thatO(logk) time can be achieved on the ROBUST PRAM, a very weak CRCW PRAM model.  相似文献   

10.
We present anO(nlog2 n) time andO(n) space algorithm for computing the shortest line segment that intersects a set ofn given line segments or lines in the plane. If the line segments do not intersect the algorithm may be trimmed to run inO(nlogn) time. Furthermore, in combination with linear programming the algorithm will also find the shortest line segment that intersects a set ofn isothetic rectangles in the plane inO(nlogk) time, wherek is the combinatorial complexity of the space of transversals andk≤4n. These results find application in: (1) line-fitting between a set ofn data ranges where it is desired to obtain the shortestline-of-fit, (2) finding the shortest line segment from which a convexn-vertex polygon is weakly externally visible, and (3) determing the shortestline-of-sight between two edges of a simplen-vertex polygon, for whichO(n) time algorithms are also given. All the algorithms are based on the solution to a new fundamental geometric optimization problem that is of independent interest and should find application in different contexts as well.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

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