Scalable 2D Convex Hull and Triangulation Algorithms for Coarse Grained Multicomputers

In this paper we describe scalable parallel algorithms for building the convex hull and a triangulation ofncoplanar points. These algorithms are designed for thecoarse grained multicomputermodel:pprocessors withO(n/p)⪢O(1) local memory each, connected to some arbitrary interconnection network. They scale over a large range of values ofnandp, assuming only thatn⩾p^1+ε(ε>0) and require timeO((T_sequential/p)+T_s(n, p)), whereT_s(n, p) refers to the time of a global sort ofndata on approcessor machine. Furthermore, they involve only a constant number of global communication rounds. Since computing either 2D convex hull or triangulation requires timeT_sequential=Θ(n log n) these algorithms either run in optimal time,Θ((n log n)/p), or in sort time,T_s(n, p), for the interconnection network in question. These results become optimal whenT_sequential/pdominatesT_s(n, p) or for interconnection networks like the mesh for which optimal sorting algorithms exist.     

Exponentiation modulo a polynomial for data security

This paper describes some properties of exponentiation modulo a polynomial and suggests its use for encryption in a mode that can be cryptanalyzed in approximatelyO(pd ³) time, whered is the size of the message frame andp is the prime modulo which the rankwise computations are carried out. While for sufficiently largepd (～10⁵) this appears to provide a one-way function which can be used in a public-key cryptosystem, we show that since encryption/ decryption effort is defined inO(d ² logpd log logp) time, a practical application of the proposed algorithm would be either in a secret key or in a tamper-proof, hardwired secret polynomial system.     

L 1 shortest paths among polygonal obstacles in the plane

We present an algorithm for computingL ₁ shortest paths among polygonal obstacles in the plane. Our algorithm employs the “continuous Dijkstra” technique of propagating a “wavefront” and runs in timeO(E logn) and spaceO(E), wheren is the number of vertices of the obstacles andE is the number of “events.” By using bounds on the density of certain sparse binary matrices, we show thatE =O(n logn), implying that our algorithm is nearly optimal. We conjecture thatE =O(n), which would imply our algorithm to be optimal. Previous bounds for our problem were quadratic in time and space. Our algorithm generalizes to the case of fixed orientation metrics, yielding anO(n?^?1/2 log² n) time andO(n?^?1/2) space approximation algorithm for finding Euclidean shortest paths among obstacles. The algorithm further generalizes to the case of many sources, allowing us to compute anL ₁ Voronoi diagram for source points that lie among a collection of polygonal obstacles.     

Path-distance heuristics for the Steiner problem in undirected networks

An integrative overview of the algorithmic characteristics of three well-known polynomialtime heuristics for the undirected Steiner minimum tree problem:shortest path heuristic (SPH),distance network heuristic (DNH), andaverage distance heuristic (ADH) is given. The performance of thesesingle-pass heuristics (and some variants) is compared and contrasted with several heuristics based onrepetitive applications of the SPH. It is shown that two of these repetitive SPH variants generate solutions that in general are better than solutions obtained by any single-pass heuristic. The worst-case time complexity of the two new variants isO(pn ³) andO(p ³ n ²), while the worst-case time complexity of the SPH, DNH, and ADH is respectivelyO(pn ²),O(m + n logn), andO(n ³) wherep is the number of vertices to be spanned,n is the total number of vertices, andm is the total number of edges. However, use of few simple tests is shown to provide large reductions of problem instances (both in terms of vertices and in term of edges). As a consequence, a substantial speed-up is obtained so that the repetitive variants are also competitive with respect to running times.     

Practical constructive schemes for deterministic shared-memory access

We present three explicit schemes for distributingM variables amongN memory modules, whereM=Θ(N ^1.5),M = Θ(N ²), andM=Θ(N ³), respectively. Each variable is replicated into a constant number of copies stored in distinct modules. We show thatN processors, directly accessing the memories through a complete interconnection, can read/write any set ofN variables in worst-case timeO (N ^1/3),O(N ^1/2), andO(N ^2/3), respectively for the three schemes. The access times for the last two schemes are optimal with respect to the particular redundancy values used by such schemes. The address computation can be carried out efficiently by each processor without recourse to a complete memory map and requiring onlyO(1) internal storage.     

Path-matching problems

The notion of matching in graphs is generalized in this paper to a set of paths rather than to a set of edges. The generalized problem, which we call thepath-matching problem, is to pair the vertices of an undirected weighted graph such that the paths connecting each pair are subject to certain objectives and/or constraints. This paper concentrates on the case where the paths are required to be edge-disjoint and the objective is to minimize the maximal cost of a path in the matching (i.e., the bottleneck version). Other variations of the problem are also mentioned. Two algorithms are presented to find the best matching under the constraints listed above for trees. Their worst-case running times areO(n logd logw), whered is the maximal degree of a vertex,w is the maximal cost of an edge, andn is the size of the tree, andO(n ²), respectively. The problem is shown to be NP-complete for general graphs. Applications of these problems are also discussed.     

Circulant block-factorization preconditioning of anisotropic elliptic problems

The recently introduced circulant block-factorization preconditioners are studied in this paper. The general approach is first formulated for the case of block-tridiagonal sparse matrices. Then an estimate of the condition number of the preconditioned matrix for a model anisotropic Dirichlet boundary value problem is derived in the formκ<√2ε(n+1)+2, whereN=n ² is the size of the discrete problem, andε stands for the ratio of the anisotropy. Various numerical tests demonstrating the behavior of the circulant block-factorization preconditioners for anisotropic problems are presented.     

On Steiner minimal trees withL p distance

LetL _p be the plane with the distanced _p (A ₁ ,A ₂ ) = (¦x ₁ ?x ₂¦ ^p + ¦y₁ ?y ₂¦^p)^/1p wherex _i andy _i are the cartesian coordinates of the pointA _i . LetP be a finite set of points inL _p . We consider Steiner minimal trees onP. It is proved that, for 1 <p < ∞, each Steiner point is of degree exactly three. Define the Steiner ratio ? _p to be inf{L _s (P)/L _m (P)¦P?L _p } whereL _s (P) andL _m (P) are lengths of the Steiner minimal tree and the minimal spanning tree onP, respectively. Hwang showed ?₁ = 2/3. Chung and Graham proved ?₂ > 0.842. We prove in this paper that ?{∞} = 2/3 and √(√2/2)?₁?₂ ≤ ?_p ≤ √3/2 for anyp.     

Randomized parallel list ranking for distributed memory multiprocessors

We present a randomized parallel list ranking algorithm for distributed memory multiprocessors, using a BSP type model. We first describe a simple version which requires, with high probability, log(3p)+log ln(n)=Õ(logp+log logn) communication rounds (h-relations withh=Õ(n/p)) andÕ(n/p)) local computation. We then outline an improved version that requires high probability, onlyr?(4k+6) log(2/3p)+8=Õ(k logp) communication rounds wherek=min{i?0 |ln(i+1)n?(2/3p)²ⁱ⁺¹}. Notekn) is an extremely small number. Forn andp?4, the value ofk is at most 2. Hence, for a given number of processors,p, the number of communication rounds required is, for all practical purposes, independent ofn. Forn?1, 500,000 and 4?p?2048, the number of communication rounds in our algorithm is bounded, with high probability, by 78, but the actual number of communication rounds observed so far is 25 in the worst case. Forn?10010100 and 4?p?2048, the number of communication rounds in our algorithm is bounded, with high probability, by 118; and we conjecture that the actual number of communication rounds required will not exceed 50. Our algorithm has a considerably smaller member of communication rounds than the list ranking algorithm used in Reid-Miller’s empirical study of parallel list ranking on the Cray C-90.⁽¹⁾ To our knowledge, Reid-Miller’s algorithm⁽¹⁾ was the fastest list ranking implementation so far. Therefore, we expect that our result will have considerable practical relevance.     

An iterative solver for a mixed variable variational formulation of the (first) biharmonic problem

The coupled system of equations resulting from a mixed variable formulation of the biharmonic problem is solved by a preconditioned conjugate gradient method. The preconditioning matrix is based on an incomplete factorization of a positive definite operator similar to the 13-point difference approximation of the biharmonic operator.The first iterate is already quite accurate even if the initial approximation is not. Hence, often a small number of iterations will suffice to get an accurate enough solution. For smaller iteration errors the number of iterations grows as O(h^?1), h → 0, where h is an average mesh-size parameter.     

An optimal visibility graph algorithm for triangulated simple polygons

LetP be a triangulated simple polygon withn sides. The visibility graph ofP has an edge between every pair of polygon vertices that can be connected by an open segment in the interior ofP. We describe an algorithm that finds the visibility graph ofP inO(m) time, wherem is the number of edges in the visibility graph. Becausem can be as small asO(n), the algorithm improves on the more general visibility algorithms of Asanoet al. [AAGHI] and Welzl [W], which take Θ(n ²) time, and on Suri'sO(m logn) visibility graph algorithm for simple polygons [S].     

The longest common subsequence problem revisited

This paper re-examines, in a unified framework, two classic approaches to the problem of finding a longest common subsequence (LCS) of two strings, and proposes faster implementations for both. Letl be the length of an LCS between two strings of lengthm andn ≥m, respectively, and let s be the alphabet size. The first revised strategy follows the paradigm of a previousO(ln) time algorithm by Hirschberg. The new version can be implemented in timeO(lm · min logs, logm, log(2n/m)), which is profitable when the input strings differ considerably in size (a looser bound for both versions isO(mn)). The second strategy improves on the Hunt-Szymanski algorithm. This latter takes timeO((r +n) logn), wherer≤mn is the total number of matches between the two input strings. Such a performance is quite good (O(n logn)) whenr～n, but it degrades to Θ(mn logn) in the worst case. On the other hand the variation presented here is never worse than linear-time in the productmn. The exact time bound derived for this second algorithm isO(m logn +d log(2mn/d)), whered ≤r is the number ofdominant matches (elsewhere referred to asminimal candidates) between the two strings. Both algorithms require anO(n logs) preprocessing that is nearly standard for the LCS problem, and they make use of simple and handy auxiliary data structures.     

Fully dynamic biconnectivity in graphs

We present an algorithm for maintaining the biconnected components of a graph during a sequence of edge insertions and deletions. It requires linear storage and preprocessing time. The amortized running time for insertions and for deletions isO(m ^2/3 ), wherem is the number of edges in the graph. Any query of the form ‘Are the verticesu andv biconnected?’ can be answered in timeO(1). This is the first sublinear algorithm for this problem. We can also output all articulation points separating any two vertices efficiently. If the input is a plane graph, the amortized running time for insertions and deletions drops toO(√n logn) and the query time isO(log² n), wheren is the number of vertices in the graph. The best previously known solution takes timeO(n ^2/3 ) per update or query.     

Linear solving for sign determination

We give a specific method to solve with quadratic complexity the linear systems arising in known algorithms to deal with the sign determination problem, both in the univariate and multivariate setting. In particular, this enables us to improve the complexity bound for sign determination in the univariate case to O(sd²log³d), where s is the number of polynomials involved and d is a bound for their degree. Previously known complexity results involve a factor of d^2.376.     

Optimal Error Estimates for the Fully Discrete Interior Penalty DG Method for the Wave Equation

In Grote et al. (SIAM J. Numer. Anal., 44:2408–2431, 2006) a symmetric interior penalty discontinuous Galerkin (DG) method was presented for the time-dependent wave equation. In particular, optimal a-priori error bounds in the energy norm and the L ²-norm were derived for the semi-discrete formulation. Here the error analysis is extended to the fully discrete numerical scheme, when a centered second-order finite difference approximation (“leap-frog” scheme) is used for the time discretization. For sufficiently smooth solutions, the maximal error in the L ²-norm error over a finite time interval converges optimally as O(h ^p+1+Δt ²), where p denotes the polynomial degree, h the mesh size, and Δt the time step.     

On counting pairs of intersecting segments and off-line triangle range searching

We describe a method for decomposing planar sets of segments and points. Using this method we obtain new efficientdeterministic algorithms for counting pairs of intersecting segments, and for answering off-line triangle range queries. In particular we obtain the following results:

1. Givenn segments in the plane, the number of pairs of intersecting segments is counted in timeO(n ^1+?+K ^1/3 n ^2/3+?), whereK is the number of intersection points among the segments, and ?>0 is an arbitrarily small constant.
2. Givenn segments in the plane which are colored with two colors, the number of pairs ofbichromatic intersecting segments is counted in timeO(n ^1+?+K _m ^1/3 n ^2/3+?), whereK _m is the number ofmonochromatic intersection points, and ?>0 is an arbitrarily small constant.
3. Givenn weighted points andn triangles on a plane, the sum of weights of points in each triangle is computed in timeO(n ^1+ε+?^1/3 n ^2/3+ε), where ? is the number of vertices in the arrangement of the triangles, and ?>0 is an arbitrarily small constant.

The above bounds depend sublinearly on the number of intersections among input segmentsK (resp.K _m , ?), which is desirable sinceK (resp.K _m , ?) can range from zero toO(n ²). All of the above algorithms use optimal Θ(n) storage. The constants of proportionality in the big-Oh notation increase as ? decreases. These results are based on properties of the sparse nets introduced by Chazelle [Cha3].     

Approximate motion planning and the complexity of the boundary of the union of simple geometric figures

We study rigid motions of a rectangle amidst polygonal obstacles. The best known algorithms for this problem have a running time of Ω(n ²), wheren is the number of obstacle corners. We introduce thetightness of a motion-planning problem as a measure of the difficulty of a planning problem in an intuitive sense and describe an algorithm with a running time ofO((a/b · 1/?_crit + 1)n(logn)²), wherea ≥b are the lengths of the sides of a rectangle and ?_crit is the tightness of the problem. We show further that the complexity (= number of vertices) of the boundary ofn bow ties (see Figure 1) isO(n). Similar results for the union of other simple geometric figures such as triangles and wedges are also presented.     

On the Largest Empty Axis-Parallel Box Amidst n Points

We give the first efficient (1?ε)-approximation algorithm for the following problem: Given an axis-parallel d-dimensional box R in ? ^d containing n points, compute a maximum-volume empty axis-parallel d-dimensional box contained in R. The minimum of this quantity over all such point sets is of the order $\Theta (\frac {1}{n} )$ . Our algorithm finds an empty axis-aligned box whose volume is at least (1?ε) of the maximum in O((8edε ^?2) ^d ?nlog ^d n) time. No previous efficient exact or approximation algorithms were known for this problem for d≥4. As the problem has been recently shown to be NP-hard in arbitrarily high dimensions (i.e., when d is part of the input), the existence of an efficient exact algorithm is unlikely. We also present a (1?ε)-approximation algorithm that, given an axis-parallel d-dimensional cube R in ? ^d containing n points, computes a maximum-volume empty axis-parallel hypercube contained in R. The minimum of this quantity over all such point sets is also shown to be of the order $\Theta (\frac{1}{n} )$ . A faster (1?ε)-approximation algorithm, with a milder dependence on d in the running time, is obtained in this case.     

Implicit midpoint rule and extrapolation to singularly perturbed boundary alue problems

Linear singularly perturbed boundary value probleme εy″?py = f(x), y(0) = y(l) = 0 is solved numerically by reducing to the first order linear system and applying the implicit midpoint rule on equidistant meshes. Using the asymptotic expansion of the global error, the second order of convergence is improved by Richardson extrapolation when h ²≤ε. Some numerical examples are given in illustration of this theory.     

Online capacity maximization in wireless networks

In this paper we study a dynamic version of capacity maximization in the physical model of wireless communication. In our model, requests for connections between pairs of points in Euclidean space of constant dimension d arrive iteratively over time. When a new request arrives, an online algorithm needs to decide whether or not to accept the request and to assign one out of k channels and a transmission power to the request. Accepted requests must satisfy constraints on the signal-to-interference-plus-noise (SINR) ratio. The objective is to maximize the number of accepted requests. Using competitive analysis we study algorithms using distance-based power assignments, for which the power of a request relies only on the distance between the points. Such assignments are inherently local and particularly useful in distributed settings. We first focus on the case of a single channel. For request sets with spatial lengths in [1,Δ] and duration in [1,Γ] we derive a lower bound of Ω(Γ?Δ ^d/2) on the competitive ratio of any deterministic online algorithm using a distance-based power assignment. Our main result is a near-optimal deterministic algorithm that is O(Γ?Δ^(d/2)+ε )-competitive, for any constant ε>0. Our algorithm for a single channel can be generalized to k channels. It can be adjusted to yield a competitive ratio of O(k?Γ ^1/k′?Δ^(d/2k″)+ε ) for any factorization (k′,k″) such that k′?k″=k. This illustrates the effectiveness of multiple channels when dealing with unknown request sequences. In particular, for Θ(log?Γ?log?Δ) channels this yields an O(log?Γ?log?Δ)-competitive algorithm. Additionally, we show how this approach can be turned into a randomized algorithm, which is O(log?Γ?log?Δ)-competitive even for a single channel.