Circles through two points that always enclose many points

This paper proves that any set of n points in the plane contains two points such that any circle through those two points encloses at least points of the set. The main ingredients used in the proof of this result are edge counting formulas for k-order Voronoi diagrams and a lower bound on the minimum number of semispaces of size at most k.Work on this paper by the first author has been supported by Amoco Fnd. Fac. Dev. Comput. Sci. 1-6-44862 and by the National Science Foundation under Grant CCR-8714565, by the second author has been partially supported by the Digital Equipment Corporation, by the fourth author has been partially supported by the Office of Naval Research under Grant N00014-86K-0416.     

Algorithms for flows with parametric capacities

We consider the problem of finding maximal flows with respect to capacities which are linear functions of a parametert [0,T]. Since this problem is a special case of a parametric linear program the classichorizontal approach can be applied in which optimal solutions are computed for successive subintervals of [0,T]. We discuss an alternative algorithm which approximates in each iteration the optimal solution for allt [0,T]. Thisvertical algorithm is a labeling type algorithm where the flow variables are piecewise linear functions. Flow augmentations are done alongconditional flow augmenting paths which can be found by modified path algorithms. The vertical algorithm can be used to solve the parametric flow problem optimally as well as to compute a good approximation for allt if the computation of the optimal solution turns out to be too time consuming.Partially supported by NSF Grants ECS-8412926 and INT-8521433, and NATO Grant RG 85/0240.     

A fourth order method for a singular two-point boundary value problem

Recently, Chawla et al. described a second order finite difference method for the class of singular two-point boundary value problems:

Invariant submanifolds and properCR foliations on a para-coKählerian manifold with concircular structure vector field

After recalling the basic properties of para-coKählerian manifolds \(\tilde M\) with concircular structure vector field ξ, the infinitesimal auto morphismsX of the structure 1-form \(\tilde \eta \) are considered. One of the results is that the Lie derivative of all powers of the structure 2-form \(\tilde \Omega ,\) i.e. \(\mathcal{L}x\tilde \Omega ^p ;p = 1,...,m,\) is exterior recurrent. Further two types of horizontal distributionsD _n which are normal to ξ. IfD _t (resp.D _n ) is involutive, the corresponding leafM _t (resp.M _n ) is a minimal submanifold of \(\tilde M\) . FurtherM _n is a symplectic submanifold and ξ is an umbilical normal section ofM _n . Finally proper immersion \(M \to \tilde M\) are discussed, whereM is aCR-sub-manifold whose horizontal distribution isD _t . It is shown that the vertical distribution is involutive, and the restriction of ξ toM is an symptotic direction. Some interesting special cases are treated.     

On characterizing the bivariate exponential and geometric distributions

In this note, a characterization of the Gumbel's bivariate exponential distribution based on the properities of the conditional moments is discussed. The result forms a sort of bivariate analogue of the characterization of the univariate exponential distribution given by Sahobov and Geshev (1974) (cited in Lau and Rao ((1982), Sankhy Ser. A, 44, 87)). A discrete version of the property provides a similar conclusion relating to a bivariate geometric distribution.     

On a characteristic of random matrices connected with unconditional convergence almost everywhere

В статье рассматрива ются множестваM _N , 1≦N<∞ всех систем функций Φ={?(x)} _j ^=1/N , заданных на [0,1] с где (ε _{i, j} ) _{i, j} ^=1/N — матрица с э лементами ± 1. Изучаетс я поведение наМ _N функц ии $$\alpha _N (\Phi ) = \mathop {\sup }\limits_\sigma \mathop {\sup }\limits_{\sum a_j^2 = 1} (\int\limits_0^1 {\mathop {\sup }\limits_{1 \leqq k \leqq N} (\sum\limits_{j = 1}^k {a_j \varphi _{\sigma (j)} (x)} } )^2 dx)^{1/2} $$ гдеσ: {1, ...,N}?{1, ...,N}. Дока зьгаается, что сущест вуют абсолютные постоянн ыеc ₃,c ₄>0,y ₀>1, такие, что для любог оN=1,2, ... иy>y ₀ $$\mu _N (\{ \Phi \in {\rm M}_{\rm N} :\alpha _N (\Phi )/\left\| \Phi \right\| > y\} ) \leqq c_3 \exp [ - \exp (c_4 y)N]$$ гдеμ _N — мера наM _N с µ _N ({Ф}) = 2^?N2 дл я любой системыΦ∈M     

A finitely convergent “row-action” method for the convex feasibility problem

We present a modification of the Cyclic Subgradient Projection (CSP) method by Censor and Lent, which solves the convex feasibility problem in a finite number of steps when a Slater type condition holds, while preserving its row-action properties. A linear rate of convergence for the CSP method is established assuming the same hypothesis.Research partially supported by CNPq, under Grant No. 301699/81.     

Oscillatory Perturbations of Linear Problems at Resonance

This paper is concerned with a study of bounded perturbations of resonant linear problems. It follows from our results that for certain types of bounded domains Ω ? Rⁿ, n ≥ 2, the Dirichlet problem $\matrix{\Delta u+\lambda_{1}u+g(u)=h(x),\ \ \ x\in\Omega\cr \quad\quad\quad\quad\quad\quad u=0,\ \ \ x\in\partial\Omega,}$ has infinitely many positive solutions, in case λ₁ is the principal eigenvalue of ?Δ subject to trivial Dirichlet boundary conditions, g is a nontrivial periodic nonlinearity of zero mean and ∫_03A9h(x)?(x)dx = 0, where ? is an eigenfunction corresponding to λ₁.     

Superbranching processes and projections of random Cantor sets

We study sequences (X ₀, X ₁, ...) of random variables, taking values in the positive integers, which grow faster than branching processes in the sense that , for m, n0, where the X _n (m, i) are distributed as X _n and have certain properties of independence. We prove that, under appropriate conditions, X _n ^1/n almost surely and in L ¹, where =sup E(X _n )^1/n . Our principal application of this result is to study the Lebesgue measure and (Hausdorff) dimension of certain projections of sets in a class of random Cantor sets, being those obtained by repeated random subdivisions of the M-adic subcubes of [0, 1] ^d . We establish a necessary and sufficient condition for the Lebesgue measure of a projection of such a random set to be non-zero, and determine the box dimension of this projection.Work done partly whilst visiting Cornell University with the aid of a Fulbright travel grant