Cuttings for Disks and Axis-Aligned Rectangles in Three-Space

We present new asymptotically tight bounds on cuttings, a fundamental data structure in computational geometry. For n objects in space and a parameter r∈?, a $\frac{1}{r}We present new asymptotically tight bounds on cuttings, a fundamental data structure in computational geometry. For n objects in space and a parameter r∈ℕ, a \frac1r\frac{1}{r} -cutting is a covering of the space with simplices such that the interior of each simplex intersects at most n/r objects. For n pairwise disjoint disks in ℝ³ and a parameter r∈ℕ, we construct a \frac1r\frac{1}{r} -cutting of size O(r ²). For n axis-aligned rectangles in ℝ³, we construct a \frac1r\frac{1}{r} -cutting of size O(r ^3/2). As an application related to multi-point location in three-space, we present tight bounds on the cost of spanning trees across barriers. Given n points and a finite set of disjoint disk barriers in ℝ³, the points can be connected with a straight line spanning tree such that every disk is stabbed by at most O(?n)O(\sqrt{n}) edges of the tree. If the barriers are axis-aligned rectangles, then there is a straight line spanning tree such that every rectangle is stabbed by O(n ^1/3) edges. Both bounds are best possible.     

Second‐order properties of the point process of nodes in a stationary Voronoi tessellation

In this paper we derive representation formulae for the second factorial moment measure of the point process of nodes and the second moment of the number of vertices of the typical cell associated with a stationary normal Voronoi tessellation in ?^d . In case the Voronoi tessellation is generated by a stationary Poisson process with intensity λ > 0 the corresponding pair correlation function g_V,λ (r) can be expressed by a weighted sum of d +2 (numerically tractable) multiple parameter integrals. The asymptotic variance of the number of nodes in an increasing cubic domain as well as the second moment of the number of vertices of the typical Poisson Voronoi cell are calculated exactly by means of these parameter integrals. The existence of a (d ? 1)st‐order pole of g_V,λ (r) at r = 0 is proved and the exact value of lim_{r →0} r^{d –1} g_V,λ (r) is determined. In the particular cases d = 2 and d = 3 the graph of g_V,1(r) including its local extreme points, the points of level 1 of gV, 1(r) and other characteristics are computed by numerical integration. Furthermore, an asymptotically exact confidence interval for the intensity of nodes is obtained. (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Spectral Algorithms for Tensor Completion

In the tensor completion problem, one seeks to estimate a low‐rank tensor based on a random sample of revealed entries. In terms of the required sample size, earlier work revealed a large gap between estimation with unbounded computational resources (using, for instance, tensor nuclear norm minimization) and polynomial‐time algorithms. Among the latter, the best statistical guarantees have been proved, for third‐order tensors, using the sixth level of the sum‐of‐squares (sos ) semidefinite programming hierarchy. However, the sos approach does not scale well to large problem instances. By contrast, spectral methods—based on unfolding or matricizing the tensor—are attractive for their low complexity, but have been believed to require a much larger sample size. This paper presents two main contributions. First, we propose a new method, based on unfolding, which outperforms naive ones for symmetric k^th‐order tensors of rank r. For this result we make a study of singular space estimation for partially revealed matrices of large aspect ratio, which may be of independent interest. For third‐order tensors, our algorithm matches the sos method in terms of sample size (requiring about rd^3/2 revealed entries), subject to a worse rank condition (r ≪ d^3/4 rather than r ≪ d^3/2). We complement this result with a different spectral algorithm for third‐order tensors in the overcomplete (r ≥ d) regime. Under a random model, this second approach succeeds in estimating tensors of rank d ≤ r ≪ d^3/2 from about rd^3/2 revealed entries. © 2018 Wiley Periodicals, Inc.     

Single step methods for general second order singular initial value problems with spherical symmetry

A one parameter family of self-starting explicit Runge-Kutta-Nyström methods has been obtained for the solution of the general second order singular initial value problem with spherical symmetry of the formu+2r ^–1 u=f(r, u, u),u(0)=A, u(0)=0. The methods are exact foru(r)=r ^–1, l,r, r ²,r ³ andr ⁴.     

Asymptotic analysis and boundary homogenization in linear elasticity

We describe the asymptotic behaviour of the solution of a linear elastic problem posed in a domain of ℝ³, with homogeneous Dirichlet boundary conditions imposed on small zones of size less than ϵ distributed on the boundary of this domain, when the parameter ϵ goes to 0. We use epi‐convergence arguments in order to establish this asymptotic behaviour. We then specialize this general situation to the case of identical strips of size r_ϵ ϵ‐periodically distributed on the lateral surface of an axisymmetric body. We exhibit a critical size of the strips through the limit of the non‐negative quantity −1/(ϵ ln r_ϵ) and we identify the different limit problems according to the values of this limit. Copyright © 2000 John Wiley & Sons, Ltd.     

The Exact Hausdorff Measure Function of the Level Sets of Multi-parameter Symmetric Stable Process

In this paper, we investigate the Hausdorff measure for level sets of N-parameter Rd-valued stable processes, and develop a means of seeking the exact Hausdorff measure function for level sets of N-parameter Rd-valued stable processes. We show that the exact Hausdorff measure function of level sets of N-parameter Rd-valued symmetric stable processes of index α is Ф（r） = r^N-d/α （log log l/r）d/α when Nα 〉 d. In addition, we obtain a sharp lower bound for the Hausdorff measure of level sets of general （N, d, α） strictly stable processes.     

Coloring random graphs online without creating monochromatic subgraphs

Consider the following random process: The vertices of a binomial random graph G_n,p are revealed one by one, and at each step only the edges induced by the already revealed vertices are visible. Our goal is to assign to each vertex one from a fixed number r of available colors immediately and irrevocably without creating a monochromatic copy of some fixed graph F in the process. Our first main result is that for any F and r, the threshold function for this problem is given by p₀(F,r,n) = n^‐1/m*₁(F,r), where m*₁(F,r) denotes the so‐called online vertex‐Ramsey density of F and r. This parameter is defined via a purely deterministic two‐player game, in which the random process is replaced by an adversary that is subject to certain restrictions inherited from the random setting. Our second main result states that for any F and r, the online vertex‐Ramsey density m*₁(F,r) is a computable rational number. Our lower bound proof is algorithmic, i.e., we obtain polynomial‐time online algorithms that succeed in coloring G_n,p as desired with probability 1 ‐ o(1) for any p(n) = o(n^‐1/m*₁(F,r)). © 2012 Wiley Periodicals, Inc. Random Struct. Alg. 44, 419–464, 2014     

Semi-parametric Estimation of the Hölder Exponent of a Stationary Gaussian Process with Minimax Rates

Let (X(t))_t∈[0,1] be a centered Gaussian process with stationary increments such that IE[(X_{u+t-X_u)²] = C|t|^s+r(t). Assume that there exists an extra parameter β > 0 and a polynomial P of degree smaller than s + β such that |r(t)-P(t)| is bounded with respect to |t|^s+β. We consider the problem of estimating the parameter s ∈ (0,2) in the asymptotic framework given by n equispaced observations in [0, 1]. Adding possibly stronger regularity conditions to r, we define classes of such processes over which we show that s cannot be estimated at a better rate than n^{min(1/2, β)}. Then, we study increment (or, more generally, discrete variation) estimators. We obtained precise bounds of the bias of the variance which show that the bias mainly depend on the parameter β and the variance on two terms, one depending on the parameter s and one on some regularity properties of r. A central limit theorem is given when the variance term relying on s dominates the bias and the other variance term. Eventually, we exhibit an estimator which achieves the minimax rate over a wide range of classes for which sufficient regularity conditions are assumed on r. This revised version was published online in August 2006 with corrections to the Cover Date.     

Cutting hyperplanes for divide-and-conquer

Givenn hyperplanes inE ^d, a (1/r)-cutting is a collection of simplices with disjoint interiors, which together coverE ^d and such that the interior of each simplex intersects at mostn/r hyperplanes. We present a deterministic algorithm for computing a (1/r)-cutting ofO(r ^d) size inO(nr ^d–1) time. If we require the incidences between the hyperplanes and the simplices of the cutting to be provided, then the algorithm is optimal. Our method is based on a hierarchical construction of cuttings, which also provides a simple optimal data structure for locating a point in an arrangement of hyperplanes. We mention several other applications of our result, e.g., counting segment intersections, Hopcroft's line/point incidence problem, linear programming in fixed dimension.This research was supported in part by the National Science Foundation under Grant CCR-9002352.     

Finite element method for Grwünwald–Letnikov time-fractional partial differential equation

In this article, we consider the finite element methods (FEM) for Grwünwald–Letnikov time-fractional diffusion equation, which is obtained from the standard two-dimensional diffusion equation by replacing the first-order time derivative with a fractional derivative (of order α, with 0?h ^r+1?+?τ^2-α), where h, τ and r are the space step size, time step size and polynomial degree, respectively. A numerical example is presented to verify the order of convergence.     

Growth and percolation on the uniform infinite planar triangulation

A construction as a growth process for sampling of the uniform in- finite planar triangulation (UIPT), defined in [AnS], is given. The construction is algorithmic in nature, and is an efficient method of sampling a portion of the UIPT.By analyzing the progress rate of the growth process we show that a.s. the UIPT has growth rate r ⁴ up to polylogarithmic factors, in accordance with heuristic results from the physics literature. Additionally, the boundary component of the ball of radius r separating it from infinity a.s. has growth rate r ² up to polylogarithmic factors. It is also shown that the properly scaled size of a variant of the free triangulation of an m-gon (also defined in [AnS]) converges in distribution to an asymmetric stable random variable of type 1/2.By combining Bernoulli site percolation with the growth process for the UIPT, it is shown that a.s. the critical probability p _c = 1/2 and that at p _c percolation does not occur.     

The decomposition numbers of the hecke algebra of typeF 4

LetW be the finite Coxeter group of typeF ₄, andH _r (q) be the associated Hecke algebra, with parameter a prime powerq, defined over a valuation ringR in a large enough extension field ofQ, with residue class field of characteristicr. In this paper, ther-modular decomposition numbers ofH _R (q) are determined for allq andr such thatr does not divideq. The methods of the proofs involve the study of the generic Hecke algebra of typeF ₄ over the ringA = ℤ[u ^1/2,u ^-1/2] of Laurent polynomials in an indeterminateu ^1/2 and its specializations onto the ring of integers in various cyclotomic number fields. Substancial use of computers and computer program systems (GAP, MAPLE, Meat-Axe) has been made.     

Cutting hyperplane arrangements

We consider a collectionH ofn hyperplanes in E ^d (where the dimensiond is fixed). An ε-cutting forH is a collection of (possibly unbounded)d-dimensional simplices with disjoint interors, which cover all E ^d and such that the interior of any simplex is intersected by at mostεn hyperplanes ofH. We give a deterministic algorithm for finding a (1/r)-cutting withO(r ^d ) simplices (which is asymptotically optimal). Forr≤n ^1−σ, where δ>0 is arbitrary but fixed, the running time of this algorithm isO(n(logn) ^O(1) r ^d−1). In the plane we achieve a time boundO(nr) forr≤n ^1−δ, which is optimal if we also want to compute the collection of lines intersecting each simplex of the cutting. This improves a result of Agarwal, and gives a conceptually simpler algorithm. For ann point setX⊆E ^d and a parameterr, we can deterministically compute a (1/r)-net of sizeO(rlogr) for the range space (X, {X ϒ R; R is a simplex}), In timeO(n(logn) ^O(1) r ^d−1 +r ^O(1)). The size of the (1/r)-net matches the best known existence result. By a simple transformation, this allows us to find ε-nets for other range spaces usually encountered in computational geometry. These results have numerous applications for derandomizing algorithms in computational geometry without affecting their running time significantly. A preliminary version of this paper appeared inProceedings of the Sixth ACM Symposium on Computational Geometry, Berkeley, 1990, pp. 1–9. Work on this paper was supported by DIMACS Center.     

The best quadrature based on given Hermite information for the Sobolev class KWr[a, b]

As usual, denote by KW ^r[a, b] the Sobolev class consisting of every function whose (r − 1)th derivative is absolutely continuous on the interval [a, b] and rth derivative is bounded by K a.e. in [a, b]. For a function f ∈ KW ^r [a, b], its values and derivatives up to r − 1 order at a set of nodes x are known. These values are said to be the given Hermite information. This work reports the results on the best quadrature based on the given Hermite information for the class KW ^r [a, b]. Existence and concrete construction issue of the best quadrature are settled down by a perfect spline interpolation. It turns out that the best quadrature depends on a system of algebraic equations satisfied by a set of free nodes of the interpolation perfect spline. From our another new result, it is shown that the system can be converted in a closed form to two single-variable polynomial equations, each being of degree approximately r/2. As a by-product, the best interpolation formula for the class KW ^r [a, b] is also obtained.     

Modeling structural variability in reduced order models of machine tool assembly groups via parametric MOR

We present a parametric model order reduction (PMOR) method applied to a parameter depending generalized state-space system, which describes the evolution of the temperature field on a vertical stand of a machine tool assembly group induced by a moving tool slide. The position of this slide parametrizes the input matrix of the associated system. The main idea is to compute projection matrices V_j, W_j in certain parameter sample points μ_j and concatenate them to the projection bases V, W, respectively, as described in [1]. Instead of using the iterative rational Krylov algorithm (IRKA) to produce the projection matrices in each parameter sample point as suggested there, here we use the well known method of balanced truncation (BT). The numerical results show that for the same reduced order r obtained from V, W ∈ ℝ^n×r, BT produces a parametric reduced order model (ROM) of similar accuracy as IRKA in less time. (© 2013 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

On the regularity of the roots of hyperbolic polynomials

We prove that a hyperbolic monic polynomial whose coefficients are functions of class C ^r of a parameter t admits roots of class C ¹ in t, if r is the maximal multiplicity of the roots as t varies. Moreover, if the coefficients are functions of t of class C ^2r , then the roots may be chosen two times differentiable at every point in t. This improves, among others, previous results of Bronšteĭn, Mandai, Wakabayashi and Kriegl, Losik and Michor.     

Optimal strategy policy in batch arrival queue with server breakdowns and multiple vacations

This paper considers a like-queue production system in which server vacations and breakdowns are possible. The decision-maker can turn a single server on at any arrival epoch or off at any service completion. We model the system by an M^[x]/M/1 queueing system with N policy. The server can be turned off and takes a vacation with exponential random length whenever the system is empty. If the number of units waiting in the system at any vacation completion is less than N, the server will take another vacation. If the server returns from a vacation and finds at least N units in the system, he immediately starts to serve the waiting units. It is assumed that the server breaks down according to a Poisson process and the repair time has an exponential distribution. We derive the distribution of the system size through the probability generating function. We further study the steady-state behavior of the system size distribution at random (stationary) point of time as well as the queue size distribution at departure point of time. Other system characteristics are obtained by means of the grand process and the renewal process. Finally, the expected cost per unit time is considered to determine the optimal operating policy at a minimum cost. The sensitivity analysis is also presented through numerical experiments.     

Counting without sampling: Asymptotics of the log‐partition function for certain statistical physics models

In this article we propose new methods for computing the asymptotic value for the logarithm of the partition function (free energy) for certain statistical physics models on certain type of finite graphs, as the size of the underlying graph goes to infinity. The two models considered are the hard‐core (independent set) model when the activity parameter λ is small, and also the Potts (q‐coloring) model. We only consider the graphs with large girth. In particular, we prove that asymptotically the logarithm of the number of independent sets of any r‐regular graph with large girth when rescaled is approximately constant if r ≤ 5. For example, we show that every 4‐regular n‐node graph with large girth has approximately (1.494…)ⁿ‐many independent sets, for large n. Further, we prove that for every r‐regular graph with r ≥ 2, with n nodes and large girth, the number of proper q ≥ r + 1 colorings is approximately ⁿ, for large n. We also show that these results hold for random regular graphs with high probability (w.h.p.) as well. As a byproduct of our method we obtain simple algorithms for the problem of computing approximately the logarithm of the number of independent sets and proper colorings, in low degree graphs with large girth. These algorithms are deterministic and use certain correlation decay properties for the corresponding Gibbs measures, and its implications to uniqueness of the Gibbs measures on the infinite trees, as well as some simple cavity trick which is well known in the physics and the Markov chain sampling literature.© 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

Hit-and-run mixes fast

It is shown that the “hit-and-run” algorithm for sampling from a convex body K (introduced by R.L. Smith) mixes in time O ^*(n ² R ²/r ²), where R and r are the radii of the inscribed and circumscribed balls of K. Thus after appropriate preprocessing, hit-and-run produces an approximately uniformly distributed sample point in time O ^*(n ³), which matches the best known bound for other sampling algorithms. We show that the bound is best possible in terms of R,r and n. Received January 26, 1998 / Revised version received October 26, 1998?Published online July 19, 1999     

Kakeya-type sets in finite vector spaces

For a finite vector space V and a nonnegative integer r≤dim V, we estimate the smallest possible size of a subset of V, containing a translate of every r-dimensional subspace. In particular, we show that if K⊆V is the smallest subset with this property, n denotes the dimension of V, and q is the size of the underlying field, then for r bounded and r<n≤rq ^r−1, we have |V∖K|=Θ(nq ^n−r+1); this improves the previously known bounds |V∖K|=Ω(q ^n−r+1) and |V∖K|=O(n ² q ^n−r+1).