A Trace Bound for the Hereditary Discrepancy

Let A be the incidence matrix of a set system with m sets and n points, m ≤ n , and let t= \mathop \rm tr M , where M= A ^T A . Finally, let σ = \mathop \rm tr M ² be the sum of squares of the elements of M . We prove that the hereditary discrepancy of the set system is at least . This general trace bound allows us to resolve discrepancy-type questions for which spectral methods had previously failed. Also, by using this result in conjunction with the spectral lemma for linear circuits, we derive new complexity bounds for range searching. We show that the (red—blue) discrepancy of the set system formed by n points and n lines in the plane is Ω(n ^1/6 ) in the worst case and always ¹ \tilde O(n ^1/6 ) . We give a simple explicit construction of n points and n halfplanes with hereditary discrepancy \tildeΩ(n ^1/4 ) . We show that in any dimension d= Ω( log n/\kern -1ptlog log n ) , there is a set system of n points and n axis-parallel boxes in \bf R ^d with discrepancy n ^{Ω(1/\kern -1pt log log n)} . Applying these discrepancy results together with a new variation of the spectral lemma, we derive a lower bound of Ω(nlog n) on the arithmetic complexity of off-line range searching for points and lines (for nonmonotone circuits). We also prove a lower bound of Ω(nlog n/\kern -1ptlog log n) on the complexity of orthogonal range searching in any dimension Ω(log n/\kern -1ptlog log n) . ¹ We use the notation \tilde O(m) and \tilde Ω(m) as shorthand for O(mlog ^c m) and Ω(m/\kern -1ptlog ^c m) , respectively, for some constant c>0 . Received April 5, 2000, and in revised form October 17, 2000. Online publication June 22, 2001.     

Approximation Algorithms for Minimum-Width Annuli and Shells

Let S be a set of n points in \re ^d . The ``roundness' of S can be measured by computing the width ω ^* =ω ^* (S) of the thinnest spherical shell (or annulus in \re ² ) that contains S . This paper contains two main results related to computing an approximation of ω ^* : (i) For d=2 , we can compute in O(n log n) time an annulus containing S whose width is at most 2ω ^* (S) . We extend this algorithm, so that, for any given parameter ε >0 , an annulus containing S whose width is at most (1+ε )ω ^* is computed in time O(n log n + n/ε ² ) . (ii) For d \geq 3 , given a parameter ε > 0 , we can compute a shell containing S of width at most (1+ε)ω ^* either in time O ( n / ε ^d ) log ( \Delata / ω ^* ε ) or in time O ( n / ε ^d-2 ) log n + 1 / εlog \Delata / ω ^* ε , where Δ is the diameter of S . Received July 6, 1999, and in revised form April 17, 2000. Online publication August\/ 11, 2000.     

Pipes, Cigars, and Kreplach: the Union of Minkowski Sums in Three Dimensions

Let Ω be a set of pairwise-disjoint polyhedral obstacles in R ³ with a total of n vertices, and let B be a ball in R ³. We show that the combinatorial complexity of the free configuration space F of B amid Ω:, i.e., (the closure of) the set of all placements of B at which B does not intersect any obstacle, is O(n ^2+ε ), for any ε >0; the constant of proportionality depends on ε. This upper bound almost matches the known quadratic lower bound on the maximum possible complexity of F . The special case in which Ω is a set of lines is studied separately. We also present a few extensions of this result, including a randomized algorithm for computing the boundary of F whose expected running time is O(n ^2+ε ). Received July 6, 1999, and in revised form April 25, 2000. Online publication August 18, 2000.     

The complexity and depth of Boolean circuits for multiplication and inversion in some fields <Emphasis Type="Italic">GF</Emphasis>(2<Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>)

Let n = (p − 1) · p ^k , where p is a prime number such that 2 is a primitive root modulo p, and 2 ^p−1 − 1 is not a multiple of p ². For a standard basis of the field GF(2 ⁿ ), a multiplier of complexity O(log log p)n log n log log _p n and an inverter of complexity O(log p log log p)n log n log log _p n are constructed. In particular, in the case p = 3 the upper bound

Multigrid methods for the computation of singular solutions and stress intensity factors II: Crack singularities

We consider the Poisson equation −Δu=f with homogeneous Dirichlet boundary condition on a two-dimensional polygonal domain Ω with cracks. Multigrid methods for the computation of singular solutions and stress intensity factors using piecewise linear functions are analyzed. The convergence rate for the stress intensity factors is whenfεL ²(Ω) and whenfεH ¹(Ω). The convergence rate in the energy norm is in the first case and in the second case. The costs of these multigrid methods are proportional to the number of elements in the triangulation. The general case wherefεH ^m (Ω) is also discussed. The work of the first author was partially supported by NSF under grant DMS-96-00133     

Precise asymptotics in the law of the iterated logarithm*

Let X₁, X₂, ... be i.i.d. random variables with EX₁ = 0 and positive, finite variance σ², and set S_n = X₁ + ... + X_n. For any α > −1, β > −1/2 and for κ_n(ε) a function of ε and n such that κ_n(ε) log log n → λ as n ↑ ∞ and , we prove that

On a method for interpolating functions on chaotic nets

Supposem, n ∈ℕ,m≡n (mod 2),K(x)=|x| ^m form odd,K(x)=|x| ^m In |x| form even (x∈ℝ ⁿ ),P is the set of real polynomials inn variables of total degree ≤m/2, andx ₁,...,x _N ∈ℝ ⁿ . We construct a function of the form

A sparse graph almost as good as the complete graph on points inK dimensions

A setV ofn points ink-dimensional space induces a complete weighted undirected graph as follows. The points are the vertices of this graph and the weight of an edge between any two points is the distance between the points under someL _p metric. Let ε≤1 be an error parameter and letk be fixed. We show how to extract inO(n logn+ε ^−k log(1/ε)n) time a sparse subgraphG=(V, E) of the complete graph onV such that: (a) for any two pointsx, y inV, the length of the shortest path inG betweenx andy is at most (1+∈) times the distance betweenx andy, and (b)|E|=O(ε^−k n).     

Sufficient conditions on the existence of trapped modes in problems of the linear theory of surface waves

An asymptotic model is found for the Neumann problem for the second-order differential equation with piecewise constant coefficients in a composite domain Ω∪ω, which are small, of order ε, in the subdomain ω. Namely, a domain Ω(ε) with a singular perturbed boundary is constructed, the solution for which provides a two-term asymptotic, that is, of increased accuracy O(ε²| log ε|^3/2), approximation to the restriction to Ω of the solution of the original problem. As opposed to other singularly perturbed problems, in the case of contrasting stiffness, the modeling requires the construction of a contour ∂Ω(ε) with ledges, i.e., with boundary fragments of curvature O(ε⁻¹). Bibliography: 33 titles.     

The Discrepancy of Boxes in Higher Dimension

We prove that the red—blue discrepancy of the set system formed by n points and n axis-parallel boxes in <bo>R</bo> ^d can be as high as n ^Ω(1) in any dimension d= Ω(log n) . This contrasts with the fixed-dimensional case d=O(1) , where the discrepancy is always polylogarithmic. More generally we show that in any dimension 1<d= O(log n) the maximum discrepancy is 2 ^Ω(d) . Our result also leads to a new lower bound on the complexity of off-line orthogonal range searching. This is the problem of summing up weights in boxes, given n weighted points and n boxes in <bo>R</bo> ^d . We prove that the number of arithmetic operations is at least Ω(nd+ nlog log n) in any dimension d=O(log n) . Received June 30, 2000, and in revised form November 9, 2000. Online publication April 6, 2001.     

Asymptotic behaviour of the phase in non-smooth obstacle scattering

In this paper, we study the asymptotic behaviour of the scattering phases(λ) of the Dirichlet Laplacian associated with obstacle , where Ω is a bounded open subset of ℝ ⁿ (n≥2) with non-smooth boundary ∂Ω and connected complement Ω _e =ℝ ⁿ . We can prove that if Ω satisfies a certain geometrical condition, then

Graphs whose every transitive orientation contains almost every relation

Given a graphG onn vertices and a total ordering ≺ ofV(G), the transitive orientation ofG associated with ≺, denotedP(G; ≺), is the partial order onV(G) defined by settingx<y inP(G; ≺) if there is a pathx=x ₁ x ₂…x _r=y inG such thatx ₁ ≺x _j for 1≦i<j≦r. We investigate graphsG such that every transitive orientation ofG contains ₂ ⁿ −o(n ²) relations. We prove that almost everyG _n,p satisfies this requirement if , but almost noG _n,p satisfies the condition if (pn log log logn)/(logn log logn) is bounded. We also show that every graphG withn vertices and at mostcn logn edges has some transitive orientation with fewer than ₂ ⁿ −δ(c)n ² relations. Partially supported by MCS Grant 8104854.     

The corona theorem on the complement of certain square cantor sets

Let K be a square Cantor set, i.e., the Cartesian product K = E × E of two linear Cantor sets. Let δ _n denote the proportion of the intervals removed in the nth stage of the construction of E. It is shown that if $ \delta _n = o(\frac{1} {{\log \log n}}) $ \delta _n = o(\frac{1} {{\log \log n}}) , then the corona theorem holds on the domain Ω = ℂ^* \ K.     

New Similarity Measures between Polylines with Applications to Morphing and Polygon Sweeping

   Abstract. We introduce two new related metrics, the geodesic width and the link width , for measuring the ``distance' between two nonintersecting polylines in the plane. If the two polylines have n vertices in total, we present algorithms to compute the geodesic width of the two polylines in O(n <sup>2</sup> log n) time using O(n <sup>2</sup> ) space and the link width in O(n <sup>3</sup> log n) time using O(n <sup>2</sup> ) working space where n is the total number of edges of the polylines. Our computation of these metrics relies on two closely related combinatorial strutures: the shortest-path diagram and the link diagram of a simple polygon. The shortest-path (resp., link) diagram encodes the Euclidean (resp., link) shortest path distance between all pairs of points on the boundary of the polygon. We use these algorithms to solve two problems: • Compute a continuous transformation that ``morphs' one polyline into another polyline. Our morphing strategies ensure that each point on a polyline moves as little as necessary during the morphing, that every intermediate polyline is also simple and disjoint to any other intermediate polyline, and that no portion of the polylines to be morphed is stretched or compressed by more than a user-defined parameter during the entire morphing. We present an algorithm that computes the geodesic width of the two polylines and utilizes it to construct a corresponding morphing strategy in O(n ² log ² n) time using O(n ² ) space. We also give an O(nlog n) time algorithm to compute a 2-approximation of the geodesic width and a corresponding morphing scheme. • Locate a continuously moving target using a group of guards moving inside a simple polygon. The guards always determine a simple polygonal chain within the polygon, with consecutive guards along the chain being mutually visible. We compute a strategy that sweeps such a chain of guards through the polygon in order to locate a target. We compute in O(n ³ ) time and O(n ² ) working space the minimum number r ^* of guards needed to sweep an n -vertex polygon. We also give an approximation algorithm, using O(n log n) time and O(n) space, to compute an integer r such that max(r - 16, 2)≤ r ^* ≤ r and P can be swept with a chain of r guards.     

Punishing Factors for Finitely Connected Domains

Let Ω and Π be two finitely connected hyperbolic domains in the complex plane \Bbb C{\Bbb C} and let R(z, Ω) denote the hyperbolic radius of Ω at z and R(w, Π) the hyperbolic radius of Π at w. We consider functions f that are analytic in Ω and such that all values f(z) lie in the domain Π. This set of analytic functions is denoted by A(Ω, Π). We prove among other things that the quantities C_n(W,P) := sup_{f ? A(W,P)}sup_{z ? W}\frac|f⁽ⁿ⁾(z)| R(f(z),P)n! (R(z,W))ⁿC_n(\Omega,\Pi)\,:=\,\sup_{f\in A(\Omega,\Pi)}\sup_{z\in \Omega}\frac{\vert f^{(n)}(z)\vert\,R(f(z),\Pi)}{n!\,(R(z,\Omega))^n} are finite for all n ? \Bbb N{n \in {\Bbb N}} if and only if ∂Ω and ∂Π do not contain isolated points.     

Absolutely convergent fourier series. An improvement of the Beurling-Helson theorem

We consider the space A(\mathbbT)A(\mathbb{T}) of all continuous functions f on the circle \mathbbT\mathbb{T} such that the sequence of Fourier coefficients [^(f)] = { [^(f)]( k ), k ? \mathbbZ }\hat f = \left\{ {\hat f\left( k \right), k \in \mathbb{Z}} \right\} belongs to l ¹(ℤ). The norm on A(\mathbbT)A(\mathbb{T}) is defined by || f ||_A(\mathbbT) = || [^(f)] ||_{l¹ (\mathbbZ)}\left\| f \right\|_{A(\mathbb{T})} = \left\| {\hat f} \right\|_{l^1 (\mathbb{Z})}. According to the well-known Beurling-Helson theorem, if f:\mathbbT ? \mathbbT\phi :\mathbb{T} \to \mathbb{T} is a continuous mapping such that || e^inf ||_A(\mathbbT) = O(1)\left\| {e^{in\phi } } \right\|_{A(\mathbb{T})} = O(1), n ∈ ℤ then φ is linear. It was conjectured by Kahane that the same conclusion about φ is true under the assumption that || e^inf ||_A(\mathbbT) = o( log| n | )\left\| {e^{in\phi } } \right\|_{A(\mathbb{T})} = o\left( {\log \left| n \right|} \right). We show that if $\left\| {e^{in\phi } } \right\|_{A(\mathbb{T})} = o\left( {\left( {{{\log \log \left| n \right|} \mathord{\left/ {\vphantom {{\log \log \left| n \right|} {\log \log \log \left| n \right|}}} \right. \kern-\nulldelimiterspace} {\log \log \log \left| n \right|}}} \right)^{1/12} } \right)$\left\| {e^{in\phi } } \right\|_{A(\mathbb{T})} = o\left( {\left( {{{\log \log \left| n \right|} \mathord{\left/ {\vphantom {{\log \log \left| n \right|} {\log \log \log \left| n \right|}}} \right. \kern-\nulldelimiterspace} {\log \log \log \left| n \right|}}} \right)^{1/12} } \right), then φ is linear.     

Random Subgraphs Of Finite Graphs: III. The Phase Transition For The n-Cube

We study random subgraphs of the n-cube {0,1}ⁿ, where nearest-neighbor edges are occupied with probability p. Let p_c(n) be the value of p for which the expected size of the component containing a fixed vertex attains the value λ2^n/3, where λ is a small positive constant. Let ε=n(p−p_c(n)). In two previous papers, we showed that the largest component inside a scaling window given by |ε|=Θ(2^−n/3) is of size Θ(2^2n/3), below this scaling window it is at most 2(log 2)nε⁻², and above this scaling window it is at most O(ε2ⁿ). In this paper, we prove that for the size of the largest component is at least Θ(ε2ⁿ), which is of the same order as the upper bound. The proof is based on a method that has come to be known as “sprinkling,” and relies heavily on the specific geometry of the n-cube.     

New Similarity Measures between Polylines with Applications to Morphing and Polygon Sweeping

Abstract. We introduce two new related metrics, the geodesic width and the link width , for measuring the ``distance' between two nonintersecting polylines in the plane. If the two polylines have n vertices in total, we present algorithms to compute the geodesic width of the two polylines in O(n <sup>2</sup> log n) time using O(n <sup>2</sup> ) space and the link width in O(n <sup>3</sup> log n) time using O(n <sup>2</sup> ) working space where n is the total number of edges of the polylines. Our computation of these metrics relies on two closely related combinatorial strutures: the shortest-path diagram and the link diagram of a simple polygon. The shortest-path (resp., link) diagram encodes the Euclidean (resp., link) shortest path distance between all pairs of points on the boundary of the polygon. We use these algorithms to solve two problems: • Compute a continuous transformation that ``morphs' one polyline into another polyline. Our morphing strategies ensure that each point on a polyline moves as little as necessary during the morphing, that every intermediate polyline is also simple and disjoint to any other intermediate polyline, and that no portion of the polylines to be morphed is stretched or compressed by more than a user-defined parameter during the entire morphing. We present an algorithm that computes the geodesic width of the two polylines and utilizes it to construct a corresponding morphing strategy in O(n ² log ² n) time using O(n ² ) space. We also give an O(nlog n) time algorithm to compute a 2-approximation of the geodesic width and a corresponding morphing scheme. • Locate a continuously moving target using a group of guards moving inside a simple polygon. The guards always determine a simple polygonal chain within the polygon, with consecutive guards along the chain being mutually visible. We compute a strategy that sweeps such a chain of guards through the polygon in order to locate a target. We compute in O(n ³ ) time and O(n ² ) working space the minimum number r ^* of guards needed to sweep an n -vertex polygon. We also give an approximation algorithm, using O(n log n) time and O(n) space, to compute an integer r such that max(r - 16, 2)≤ r ^* ≤ r and P can be swept with a chain of r guards.     

Semidiscrete and asymptotic approximations for the nonstationary radiative–conductive heat transfer problem in a periodic system of grey heat shields

We consider semidiscrete and asymptotic approximations to a solution to the nonstationary nonlinear initial-boundary-value problem governing the radiative–conductive heat transfer in a periodic system consisting of n grey parallel plate heat shields of width ε = 1/n, separated by vacuum interlayers. We study properties of special semidiscrete and homogenized problems whose solutions approximate the solution to the problem under consideration. We establish the unique solvability of the problem and deduce a priori estimates for the solutions. We obtain error estimates of order O( ?{e} ) O\left( {\sqrt {\varepsilon } } \right) and O(ε) for semidiscrete approximations and error estimates of order O( ?{e} ) O\left( {\sqrt {\varepsilon } } \right) and O(ε ^3/4) for asymptotic approximations. Bibliography: 9 titles.     

On shooting methods for the discrete Helmholtz equation with constant coefficients

Summary The paper is concerned with shooting solvers for the Helmholtz equation with constant coefficients in two dimensions using finite differences for the discretization. Dirichlet boundary conditions are treated though other conditions are possible. Beginning with a single shooting method some recursive multiple shooting methods are developed. It will be shown that the performance of the algorithms may be improved considerably by a redundance-free recursion. The number of operations required for one solution will be computed, but without preparing some matrices which do not depend on the boundary conditions and the inhomogenity. For a square withn×n points the number is of the orderO(n ²⁺⁽ⁿ⁾) with . The method will be compared with a multi-grid program and finally — as an example—a Stokes-solver and some numerical results with the shooting method are given.