A distance-optimal algorithm for selection on the mesh has proved to be elusive, although distance-optimal algorithms for the related problems of routing and sorting have recently been discovered. In this paper we exp...
详细信息
A distance-optimal algorithm for selection on the mesh has proved to be elusive, although distance-optimal algorithms for the related problems of routing and sorting have recently been discovered. In this paper we explain, using the notion of adaptiveness, why techniques used in the currently best selection algorithms cannot lead to a distance-optimal algorithm. For worst-case inputs we apply new techniques to improve the previous best upper bound of 1.22n of Kaklamanis et al. [7] to 1.15n. This improvement is obtained in part by increasing the adaptiveness of previous algorithms.
This paper gives various (positive and negative) results on the complexity of the problem of computing and approximating mixed volumes of polytopes and more general convex bodies in arbitrary dimension. On the negativ...
详细信息
This paper gives various (positive and negative) results on the complexity of the problem of computing and approximating mixed volumes of polytopes and more general convex bodies in arbitrary dimension. On the negative side, we present several # P-hardness results that focus on the difference of computing mixed volumes versus computing the volume of polytopes. We show that computing the volume of zonotopes is # P-hard (while each corresponding mixed volume can be computed easily) but also give examples showing that computing mixed volumes is hard even when computing the volume is easy. On the positive side, we derive a randomized algorithm for computing the mixed volumes [GRAPHICS] of well-presented convex bodies K(1),...,K(s), where m(1),...,m(s) is an element of N(0) and m(1) greater than or equal to n - psi(n) with psi(n) = o(log n/log log n). The algorithm is an interpolation method based on polynomial-time randomized log algorithms for computing the volume of convex bodies. This paper concludes with applications of our results to various problems in discrete mathematics, combinatorics, computational convexity, algebraic geometry, geometry of numbers, and operations research.
Far a polygon P, the bounded Voronoi diagram of P is a partition of P into regions assigned to the vertices of P. A point p inside P belongs to the region of a vertex v if and only if v is the closest vertex of P visi...
详细信息
Far a polygon P, the bounded Voronoi diagram of P is a partition of P into regions assigned to the vertices of P. A point p inside P belongs to the region of a vertex v if and only if v is the closest vertex of P visible from p. We present a randomized algorithm that builds the bounded Voronoi diagram of a simple polygon in linear expected time. Among other applications, we can construct within the same time bound the generalized Delaunay triangulation of P and the minimal spanning tree on P's vertices that is contained in P.
We describe a randomized parallel algorithm to solve the single function coarsest partition problem. The algorithm runs in O(log n) time using O(n) operations with high probability on the Priority CRCW PRAM. The previ...
详细信息
We describe a robust, dynamic algorithm to compute the arrangement of a set of line segments in the plane, and its implementation. The algorithm is robust because, following Greene(7) and Hobby,(11) it rounds the endp...
详细信息
We describe a robust, dynamic algorithm to compute the arrangement of a set of line segments in the plane, and its implementation. The algorithm is robust because, following Greene(7) and Hobby,(11) it rounds the endpoints and intersections of all line segments to representable points, but in a way that is globally topologically consistent. The algorithm is dynamic because, following Mulmuley,(16) it uses a randomized hierarchy of vertical cell decompositions to make locating points, and inserting and deleting line segments,, efficient. Our algorithm is novel because it marries the robustness of the Greene and Hobby algorithms with Mulmuley's dynamic algorithm in a way that preserves the desirable properties of each.
This paper contains a simple, randomized algorithm for constructing the convex bull of a set of n points in the plane with expected running time O(n log h) where h is the number of points on the convex hull.
This paper contains a simple, randomized algorithm for constructing the convex bull of a set of n points in the plane with expected running time O(n log h) where h is the number of points on the convex hull.
This paper proposes a randomized algorithm for the estimation of the planar motion parameters of a bounded closed set. By randomly searching triangles on two shapes measured at different times, the algorithm solves th...
详细信息
This paper proposes a randomized algorithm for the estimation of the planar motion parameters of a bounded closed set. By randomly searching triangles on two shapes measured at different times, the algorithm solves the rigid motion equation using correspondences between edges of triangles which are detected using a random search and a voting procedure. (C) 1997 Elsevier Science B.V.
We consider the following resource constrained scheduling problem. We are given m identical processors, s resources R-1, ..., R-s with upper bounds b(1), ..., b(s), n independent jobs T-1, ..., T-n of unit length, whe...
详细信息
We consider the following resource constrained scheduling problem. We are given m identical processors, s resources R-1, ..., R-s with upper bounds b(1), ..., b(s), n independent jobs T-1, ..., T-n of unit length, where each job T-j has a start time r(j) is an element of N, requires one processor and an amount R-i(j) is an element of {0, 1} of resource R-i, i = 1, ..., s. The optimization problem is to schedule the jobs at discrete times in N subject to the processor, resource and start-time constraints so that the latest scheduling time is minimum. Multidimensional bin packing is a special case of this problem. Resource constrained scheduling can be relaxed in a natural way when one allows the scheduling of fraction of jobs. Let C-opt (resp. C) be the minimum schedule size for the integral (resp. fractional scheduling). While the computation of C-opt is a NP-hard problem, C can be computed by linear programming in polynomial time. In case of zero start times Rock and Schmidt (1983) showed for the integral problem a polynomial-time approximation within (m/2)C-opt and de la Vega and Lueker (1981), improving a classical result of Garey et al. (1976), gave for every is an element of > 0 a linear time algorithm with an asymptotic approximation guarantee of (s + epsilon)C-opt. The main contributions of this paper include the first polynomial-time algorithm approximating C-opt for every epsilon is an element of(0, 1) within a factor of 1 + epsilon for instances with b(i) = Omega(epsilon(-2)log(Cs)) for all i and m = Omega(epsilon(-2) logC), and a proof that the achieved approximation under the given conditions is best possible, unless P = NP. Furthermore, in some cases we give for every fixed alpha > 1 a parallel 2 alpha-factor approximation algorithm.
In this paper we focus on the problem of designing very fast parallel algorithms for the planar convex hull problem that achieve the optimal O(n log H) work-bound for input size n and output size H. Our algorithms are...
详细信息
In this paper we focus on the problem of designing very fast parallel algorithms for the planar convex hull problem that achieve the optimal O(n log H) work-bound for input size n and output size H. Our algorithms are designed for the arbitrary CRCW PRAM model. We first describe a very simple O(log n log H) time optimal deterministic algorithm for the planar hulls which is an improvement over the previously known Omega(log(2) n) time algorithm for small outputs. For larger values of H, we can achieve a running time of O(log n log log n) steps with optimal work. We also present a fast randomized algorithm that runs in expected time O(log *** log n) and does optimal O(n log H) work. For log H = Omega(log log n), we can achieve the optimal running time of O(log H) while simultaneously keeping the work optimal. When log H is o(log n), our results improve upon the previously best known Theta(log n) expected time randomized algorithm of Ghouse and Goodrich. The randomized algorithms do not assume any input distribution and the running times hold with high probability. (C) 1997 Elsevier Science B.V.
In this paper we study the sorting performance of a 128-processor CRAY T3D and discuss the efficient use of the toroidal network connecting the processors. The problems we consider range from that of sorting one word ...
详细信息
In this paper we study the sorting performance of a 128-processor CRAY T3D and discuss the efficient use of the toroidal network connecting the processors. The problems we consider range from that of sorting one word per processor to sorting the entire memory of the machine, and we give efficient algorithms for each case. In addition, we give both algorithms that make assumptions about the distribution of the data and those that make no assumptions. The clear winner, if data can be assumed to be uniformly distributed, is a method that we call a hash-and-chain sort. The time for this algorithm to sort one million words per processor over 64 processors is less than two seconds, which compares favorably to about four seconds using a 4-processor CRAY C90 and about 17 seconds using a 64-processor Thinking Machines CM-5.
暂无评论