Enclosing a Set of Objects by Two Minimum Area Rectangles

In this paper, we face the problem of computing an enclosing pair of axis-parallel rectangles of a set of polygonal objects in the plane, serving as a simple container. We propose anO(nα(n)log n) worst-case time algorithm, where α( ) is the inverse Ackermann's function, for finding, given a setMof points, segments and polygons defined bynvertices, a pair of axis-parallel rectangles (s, t) such thats∪tencloses all objects inMand area(s)+area(t) is minimum. The algorithm works inO(nα(n) log log n) worst-case space. Moreover, we prove an Ω(n log n) lower bound for the one-dimensional version of the problem. We also show that for the special case of enclosing a set of polygons with axis-parallel sides, our algorithm runs in optimal worst-case timeO(n log n), using worst-case spaceO(n log log n).     

Finding intersection of rectangles by range search

Three related rectangle intersection problems in k-dimensional space are considered: (1) find the intersections of a rectangle with a given set of rectangles, (2) find the intersecting pairs of rectangles as they are inserted into or deleted from an existing set of rectangles, and (3) find the intersecting pairs of a given set of rectangles. By transforming these problems into range search problems, one need not divide the intersection problem into two subproblems, namely, the edge-intersecting problem and the containment problem, as done by many previous studies. Furthermore, this approach can also solve these subproblems separately, if required. For the first problem the running time is O((log n)^2k−1 + s), where s is the number of intersecting pairs of rectangles. For the second problem the time needed to generate and maintain n rectangles is O(n(log n)^2k) and the time for each query is O((log n)^2k−1 + s). For the third problem the total time is O(n log n + n(log n)^2(k−1) + s) for k ≥ 1.     

R/S统计量重对数律的精确收敛速度

Let{Xn;n≥1}be a sequence of i.i.d, random variables with finite variance,Q（n）be the related R/S statistics. It is proved that lim ε↓0 ε^2 ∑n=1 ^8 n log n/1 P{Q（n）≥ε√2n log log n}=2/1 EY^2,where Y=sup0≤t≤1B（t）-inf0≤t≤sB（t）,and B（t） is a Brownian bridge.     

An optimal contour algorithm for iso-oriented rectangles

Given a set of n iso-oriented rectangles in 2-space we describe an algorithm which determines the contour of their union in O(n log n + p) time and O(n + p) space, where p is the number of edges in the contour. This performance is time-optimal. The space requirements are the same as in the best previously known algorithm. We achieve this by introducing a new data structure, the contracted segment tree, which is a non-trivial modification of the well known segment tree. If only the pieces of the contour are to be reported then this approach yields a time- and space-optimal algorithm.     

Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane

An intersection graph of rectangles in the (x, y)-plane with sides parallel to the axes is obtained by representing each rectangle by a vertex and connecting two vertices by an edge if and only if the corresponding rectangles intersect. This paper describes algorithms for two problems on intersection graphs of rectangles in the plane. One is an O(n log n) algorithm for finding the connected components of an intersection graph of n rectangles. This algorithm is optimal to within a constant factor. The other is an O(n log n) algorithm for finding a maximum clique of such a graph. It seems interesting that the maximum clique problem is polynomially solvable, because other related problems, such as the maximum stable set problem and the minimum clique cover problem, are known to be NP-complete for intersection graphs of rectangles. Furthermore, we briefly show that the k-colorability problem on intersection graphs of rectangles is NP-complete.     

Hypercube orientations with only two in-degrees

We consider the problem of orienting the edges of the n-dimensional hypercube so only two different in-degrees a and b occur. We show that this can be done, for two specified in-degrees, if and only if obvious necessary conditions hold. Namely, we need 0?a,b?n and also there exist non-negative integers s and t so that s+t=n² and as+bt=n²n−1. This is connected to a question arising from constructing a strategy for a “hat puzzle”.     

Ruin Probabilities for Risk Models with Ordered Claim Arrivals

Recently, Lefèvre and Picard (Insur Math Econ 49:512–519, 2011) revisited a non-standard risk model defined on a fixed time interval [0,t]. The key assumption is that, if n claims occur during [0,t], their arrival times are distributed as the order statistics of n i.i.d. random variables with distribution function F _t (s), 0?≤?s?≤?t. The present paper is concerned with two particular cases of that model, namely when F _t (s) is of linear form (as for a (mixed) Poisson process), or of exponential form (as for a linear birth process with immigration or a linear death-counting process). Our main purpose is to obtain, in these cases, an expression for the non-ruin probabilities over [0,t]. This is done by exploiting properties of an underlying family of Appell polynomials. The ultimate non-ruin probabilities are then derived as a limit.     

Hamiltonian decompositions of complete regular s-partite graphs

In this paper we give a procedure by which Hamiltonian decompositions of the s-partite graph K_n,n,…,n, where (s − 1)n is even, can be constructed. For 2t⩽s, 1⩽a₁⩽…⩽a_t⩽n, we find conditions which are necessary and sufficient for a decomposition of the edge-set of K_a1a2…,a_t into (s − 1)n/2 classes, each class consisting of disjoint paths, to be extendible to a Hamiltonian decomposition of the complete s-partite graph K_rmn,n,…,n so that each of the classes forms part of a Hamiltonian cycle.     

Increasing the convergence rate of series

This paper deals with the question of obtaining from the sequence {s_n} of partial sums of a convergent series s a new sequence {t_n} which converges to the same limit s as s_n, but more rapidly. When the general term u_n of the series s possesses certain types of expansion involving inverse powers of n, it is shown how t_n is obtained by adding a fixed number of terms to s_n. When the series s is convergent, these terms tend to zero as n tends to infinity, but they are such as to make t_n much more rapidly convergent to s—in fact we can make the convergence rate as great as we wish. Explicit general formulas are obtained for a wide range of important series.     

Local times for two-parameter Lévy processes

In this article we study the problem of existence of jointly continuous local time for two-parameter Lévy processes. Here, ‘local time’ is understood in the sense of occupation density, kand by 2-parameter Lévy process we mean a process X = {X_z: z ? [0, +∞)²} with independent and stationary increments (over rectangles of the type (s, s′] × (t, t′]). We prove that if X is $\text{R}$-valued and its lower index is greater than one, then a jointly continuous (at least outside {(x,s,t): x = 0}) local time can be obtained via Berman's method. Also, we extend to 2-parameter processes a result of Getoor and Kesten for usual Lévy processes. Implications in terms of ‘approximate local growth’ of X are stated.     

The Ramsey number R(3, t) has order of magnitude t2/log t

The Ramsey number R(s, t) for positive integers s and t is the minimum integer n for which every red-blue coloring of the edges of a complete n-vertex graph induces either a red complete graph of order s or a blue complete graph of order t. This paper proves that R(3, t) is bounded below by (1 – o(1))t/²/log t times a positive constant. Together with the known upper bound of (1 + o(1))t²/log t, it follows that R(3, t) has asymptotic order of magnitude t²/log t. © 1995 John Wiley & Sons, Inc.     

Conjectured statistics for the q,t-Catalan numbers

We introduce the distribution function F_n(q,t) of a pair of statistics on Catalan words and conjecture F_n(q,t) equals Garsia and Haiman's q,t-Catalan sequence C_n(q,t), which they defined as a sum of rational functions. We show that F_n,s(q,t), defined as the sum of these statistics restricted to Catalan words ending in s ones, satisfies a recurrence relation. As a corollary we are able to verify that F_n(q,t)=C_n(q,t) when t=1/q. We also show the partial symmetry relation F_n(q,1)=F_n(1,q). By modifying a proof of Haiman of a q-Lagrange inversion formula based on results of Garsia and Gessel, we obtain a q-analogue of the general Lagrange inversion formula which involves Catalan words grouped according to the number of ones at the end of the word.     

On the resolvent of the Laplacian on functions for degenerating surfaces of finite geometry

We consider families (Yn) of degenerating hyperbolic surfaces. The surfaces are geometrically finite of fixed topological type. Let Zn be the Selberg Zeta function of Yn, and let zn be the contribution of the pinched geodesics to Zn. Extending a result of Wolpert's, we prove that Zn(s)/zn(s) converges to the Zeta function of the limit surface if Re(s)>1/2. The technique is an examination of resolvent of the Laplacian, which is composed from that for elementary surfaces via meromorphic Fredholm theory. The resolvent ⁻¹(Δn−t) is shown to converge for all t∉[1/4,∞). We also use this property to define approximate Eisenstein functions and scattering matrices.     

Conditions for the convergence in distribution of maxima of stationary normal processes

The asymptotic distribution of the maximum M_n=max_1?t?nξ_t in a stationary normal sequence ξ₁,ξ,… depends on the correlation r_t between ξ₀ and ξ_t. It is well known that if r_t log t → 0 as t → ∞ or if Σr²_t<∞, then the limiting distribution is the same as for a sequence of independent normal variables. Here it is shown that this also follows from a weaker condition, which only puts a restriction on the number of t-values for which rt log t islarge. The condition gives some insight into what is essential for this asymptotic behaviour of maxima. Similar results are obtained for a stationary normal process in continuous time.     

Slow entropy for some smooth flows on surfaces

We study slow entropy in some classes of smooth mixing flows on surfaces. The flows we study can be represented as special flows over irrational rotations and under roof functions which are C² everywhere except one point (singularity). If the singularity is logarithmic asymmetric (Arnol’d flows), we show that in the scale a_n(t) = n(log n)^t slow entropy equals 1 (the speed of orbit growth is n log n) for a.e. irrational α. If the singularity is of power type (x^?γ, γ ∈ (0, 1)) (Kochergin flows), we show that in the scale a_n(t) = n^t slow entropy equals 1 + γ for a.e. α.We show moreover that for local rank one flows, slow entropy equals 0 in the n(log n)^t scale and is at most 1 for scale n^t. As a consequence we get that a.e. Arnol’d and a.e Kochergin flow is never of local rank one.     

Domino tilings of rectangles with fixed width

Let t(k,n) denote the number of ways to tile a 1 × n rectangle with 1 × 2 rectangles (called dominoes). We show that for each fixed k the sequence t_k=(t(k,0), t(k,1),…) satisfies a difference equation (linear, homogeneous, and with constant coefficients). Furthermore, a computational method is given for finding this difference equation together with the initial terms of the sequence. This gives rise to a new way to compute t(k,n) which differs completely with the known Pfaffian method. The generating function of t_k is a rational function F_k, and F_k is given explicitly for k=1,…,8. We end with some conjectures concerning the form of F_k based on our computations.     

Asymptotic enumeration of dense 0-1 matrices with specified line sums

Let s=(s₁,s₂,…,sm) and t=(t₁,t₂,…,tn) be vectors of non-negative integers with . Let B(s,t) be the number of m×n matrices over {0,1} with jth row sum equal to sj for 1?j?m and kth column sum equal to tk for 1?k?n. Equivalently, B(s,t) is the number of bipartite graphs with m vertices in one part with degrees given by s, and n vertices in the other part with degrees given by t. Most research on the asymptotics of B(s,t) has focused on the sparse case, where the best result is that of Greenhill, McKay and Wang (2006). In the case of dense matrices, the only precise result is for the case of equal row sums and equal column sums (Canfield and McKay, 2005). This paper extends the analytic methods used by the latter paper to the case where the row and column sums can vary within certain limits. Interestingly, the result can be expressed by the same formula which holds in the sparse case.     

A local smoothing estimate for the Schrödinger equation

We show that the Schrödinger operator eitΔ is bounded from Wα,q(Rn) to Lq(Rn×[0,1]) for all α>2n(1/2−1/q)−2/q and q?2+4/(n+1). This is almost sharp with respect to the Sobolev index. We also show that the Schrödinger maximal operator sup0<t<1|eitΔf| is bounded from Hs(Rn) to when s>s₀ if and only if it is bounded from Hs(Rn) to L²(Rn) when s>2s₀. A corollary is that sup0<t<1|eitΔf| is bounded from Hs(R²) to L²(R²) when s>3/4.     

Commutativity in special unitary groups at odd primes

It is a classical result by Bott that SU(s) and SU(t) homotopy commute in SU(n) if and only if s+t?n. We consider the p-localization analog of this problem and give an answer at odd primes.     

Triply-Logarithmic Parallel Upper and Lower Bounds for Minimum and Range Minima over Small Domains

We consider the problem of computing the minimum ofnvalues, and several well-known generalizations [prefix minima, range minima, and all nearest smaller values (ANSV)] for input elements drawn from the integer domain [1···s], wheres ≥ n. In this article we give simple and efficient algorithms for all of the preceding problems. These algorithms all takeO(log log log s) time using an optimal number of processors andO(ns^ε) space (for constant ε < 1) on the COMMON CRCW PRAM. The best known upper bounds for the range minima and ANSV problems were previouslyO(log log n) (using algorithms for unbounded domains). For the prefix minima and for the minimum problems, the improvement is with regard to the model of computation. We also prove a lower bound of Ω(log log n) for domain sizes = 2^{Ω(log n log log n)}. Since, forsat the lower end of this range, log log n = Ω(log log log s), this demonstrates that any algorithm running ino(log log log s) time must restrict the range ofson which it works.