New Constructions of Weak ε-Nets

A finite set $N \subset \R^d$ is a {\em weak $\eps$-net} for an $n$-point set $X\subset \R^d$ (with respect to convex sets) if $N$ intersects every convex set $K$ with $|K\,\cap\,X|\geq \eps n$. We give an alternative, and arguably simpler, proof of the fact, first shown by Chazelle et al., that every point set $X$ in $\R^d$ admits a weak $\eps$-net of cardinality $O(\eps^{-d}\polylog(1/\eps))$. Moreover, for a number of special point sets (e.g., for points on the moment curve), our method gives substantially better bounds. The construction yields an algorithm to construct such weak $\eps$-nets in time $O(n\ln(1/\eps))$.     

Quasi-Monte Carlo integration over

In this paper we show that a wide class of integrals over with a probability weight function can be evaluated using a quasi-Monte Carlo algorithm based on a proper decomposition of the domain and arranging low discrepancy points over a series of hierarchical hypercubes. For certain classes of power/exponential decaying weights the algorithm is of optimal order.

     

An Identity Relating Moments of Functionals of Convex Hulls

Denote by $K_n$ the convex hull of $n$ independent random points distributed uniformly in a convex body $K$ in $\R^d$, by $V_n$ the volume of $K_n$, by $D_n$ the volume of $K\backslash K_n$, and by $N_n$ the number of vertices of $K_n$. A well-known identity due to Efron relates the expected volume ${\it ED}_n$---and thus ${\it EV}_n$---to the expected number ${\it EN}_{n+1}$. This identity is extended from expected values to higher moments. The planar case of the arising identity for the variances provides in a simple way the corrected version of a central limit theorem for $D_n$ by Cabo and Groeneboom ($K$ being a convex polygon) and an improvement of a central limit theorem for $D_n$ by Hsing ($K$ being a circular disk). Estimates of $\var D_n$ ($K$ being a two-dimensional smooth convex body) and $\var N_n$ ($K$ being a $d$-dimensional smooth convex body, $d\geq 4$) are obtained. The identity for moments of arbitrary order shows that the distribution of $N_n$ determines ${\it EV}_{n-1}, {\it EV}_{n-2}^2,\dots, {\it EV}_{d+1}^{n-d-1}$. Reversely it is proved that these $n-d-1$ moments determine the distribution of $N_n$ entirely. The resulting formula for the probability that $N_n=k\ (k=d+1,\dots , n)$ appears to be new for $k\geq d+2$ and yields an answer to a question raised by Baryshnikov. For $k=d+1$ the formula reduces to an identity which has been repeatedly pointed out.     

Global convergence of an isentropic Euler-Poisson system in $\R^+ \times \R^d$

We prove the global-in-time convergence of an Euler-Poisson system near a constant equilibrium state in the whole space $\R^d$, as physical parameters tend to zero. The result follows from the uniform global existence of smooth solutions by means of energy estimates together with compactness arguments. For this purpose, we establish uniform estimates for $\dive \,u$ and $\curle \,u$ instead of $\nabla u$.     

多维非退化扩散过程的象集与图集的一致Packing维数

设B(t)=(B(t))=(B1(t),B2(t),…,BN(t))为N维Brown运动,设α(x)=(αij(x),1(≤)I(≤)d,1(≤)j(≤)N),β(x)=(βi(x),1(≤)I(≤)d),x∈Rd,1(≤)d(≤)N,α(x)和β(x)有界连续和满足Lipchitz条件,且存在常数c0＞0,使得对每个x∈Rd,a(x)=α(x)α(x)*的每个特征根都不小于c0.设dX(t)=α(X(t))dB(t) β(X(t))dt,设d(≥)3.可以证明P(ωDimX(E,ω)=DimGRX(E,ω)=2DimE,(A)E∈B[0,∞))=1.这里X(E,ω)={X(t,ω)t∈E},GRX(E,ω)={(t,X(t,ω))t∈E},DimF表示F的Packing维数.     

非退化扩散过程的水平集和极集

设X(t)(t∈R )是一个d维非退化扩散过程．本文得到了比原有结果更一般的非退化扩散过程极性的充分条件,证明了对任意u∈Rd,紧集E(0, ∞),有若d=1,则对任意紧集F(?)R, 若d≥2,则对任意紧集E ∈(0, ∞), 其中B(Rd)为Rd上的Borel σ-代数,dim和Dim分别表示Hausdorff维数和Packing 维数．     

Tverberg-Type Theorems for Separoids

Let $S$ be a $d$-dimensional separoid of $(k-1)(d+1)+1$ convex sets in some "large-dimensional" Euclidean space $\E^N$. We prove a theorem that can be interpreted as follows: if the separoid $S$ can be mapped with a monomorphism to a $d$-dimensional separoid of points $P$ in general position, then there exists a $k$-colouring $\varsigma\colon \ S\to K_k$ such that, for each pair of colours $i,j\in K_k$, the convex hulls of their preimages do intersect---they are not separated. Here, by a monomorphism we mean an injective function such that the preimage of separated sets are separated. In a sense, this result is "dual" to the Hadwiger-type theorems proved by Goodman and Pollack (1988) and Arocha et al. (2002). We also introduce $\T(k,d)$, the minimum number $n$ such that all $d$-dimensional separoids of order at least $n$ can be $k$-coloured as before. By means of examples and explicit colourings, we show that for all $k>2$ and $d>0$, \[(k-1)(d+1)+1<\T(k,d)<{k\choose2}(d+1)+1.\] Furthermore, by means of a probabilistic argument, we show that for each $d$ there exists a constant $C=C(d)$ such that for all $k$, $\T(k,d)\leq Ck\log k$.     

SINGULAR BOUNDARY PROPERTIES OF HARMONIC FUNCTIONS AND FRACTAL ANALYSIS

ＳＩＮＧＵＬＡＲＢＯＵＮＤＡＲＹＰＲＯＰＥＲＴＩＥＳＯＦＨＡＲＭＯＮＩＣＦＵＮＣＴＩＯＮＳＡＮＤＦＲＡＣＴＡＬＡＮＡＬＹＳＩＳＷＥＮＺＨＩＹＩＮＧＺＨＡＮＧＹＩＰＩＮＧＭａｎｕｓｃｒｉｐｔｒｅｃｅｉｖｅｄＪａｎｕａｒｙ１１，１９９５．Ｒｅｖｉ...     

A Partitioned Version of the Erdös–Szekeres Theorem for Quadrilaterals

We prove a partitioned version of the Erdös–Szekeres theorem for the case $k = 4$: any finite set $X \subset \bbbr^2$ of points in general position can be partitioned into sets $X_0, X_{ij}$ where $i=1,2,3,4$ and $j=1,\ldots,26$, so that $|X_{1j}|=|X_{2j}|=|X_{3j}|=|X_{4j}|$, $|X_0|\leq 4$ and for all $j$ every transversal $\{x_1,x_2,x_3,x_4\}$, $x_1 \in X_{1j}, x_2 \in X_{2j},x_3 \in X_{3j}, x_4 \in X_{4j}$, is in convex position. In order to prove this, we show another theorem, the partitioned version of the same type lemma, which was proved by Bárány and Valtr.     

Disjoint empty convex pentagons in planar point sets

In this paper we obtain the first non-trivial lower bound on the number of disjoint empty convex pentagons in planar points sets. We show that the number of disjoint empty convex pentagons in any set of n points in the plane, no three on a line, is at least $\left\lfloor {\tfrac{{5n}} {{47}}} \right\rfloor $ . This bound can be further improved to $\tfrac{{3n - 1}} {{28}} $ for infinitely many n.     

Banach空间中有限个增生算子公共零点的带误差项的迭代逼近

令E为实一致凸Banach空间,满足Opial条件或其范数是Frechet可微的.令为增生算子,满足值域条件且为非空闭凸子集且满足 .将引入新的带误差项的迭代算法并证明迭代序列弱收敛于{Ai}ki=1的公共零点.     

On Distinct Distances from a Vertex of a Convex Polygon

Given a set P of n points in convex position in the plane, we prove that there exists a point such that the number of distinct distances from p is at least The best previous bound, from 1952, is due to Moser.     

Spaces of type BLO for non-doubling measures

The spaces of type BLO for the positive Radon measures satisfying a growth condition on are introduced. It is shown that some properties which hold for the classical space BLO when is a doubling measure remain valid for the spaces of type BLO introduced in this paper, without assuming doubling.

     

No Helly Theorem for Stabbing Translates by Lines in R<Superscript>3</Superscript>

For each $n>2$ we construct a convex body $K\subset {\Bbb R}^3$ and a finite family ${\cal F}$ of disjoint translates of $K$ such that any $n-1$ members ${\cal F}$ admit a line transversal, but ${\cal F}$ has no line transversal.     

逼近Banach空间中渐近非扩张映象的不动点

设E是一致凸Banach空间,C是E的非空闭凸子集, T:C→C是具有不动点的渐近非扩张映象. 该文证明了, 在某些适当的条件下, 由下列修改了的Ishikawa迭代程序所定义的序列{x\-n},\$\$x\-\{n+1\}=t\-nT\+n(s\-nT\+nx\-n+(1-s\-n)x\-n)+(1-t\-n)x\-n,\$\$弱收敛到T的不动点, 其中{t\-n},{s\-n}是区间\[0,1\]中满足某些限制的实数列.     

A Theorem on the Convexity of Planar Bezier Curves of Degree n

The puppose of this paper is to prove the following Theorem. If the polygon $\[{P_0}{P_1} \cdots {P_n}{P_0}\]$ formed by the characteristic polygon $\[{P_0}{P_1} \cdots {P_n}{P_0}\]$ of a planar Bezier curve is convex,then so is the Bezier curve. In the case that the angle of rotation from $\[\mathop {{P_0}P{}_1}\limits^ \to \]$ to $\[\mathop {{P_{n - 1}}P{}_n}\limits^ \to \]$ is not larger than \pi,we obtained the theorem by using certain properties of Bernstein polynomials.On the contrary,if the above angle of rotation is larger than \pi,then we cut the oringinal Bezier curve into two new Bezier curves,and prove that the new corresponding characteristic polygons are convex and angles of rotation betweenthe first edge and last edge of the both polygons are not larger than \pi,so that we reduce the latter case into the former discussed case.The theoremis proved. In the present paper we also discuss the distribution of the singular points and inflection points of a planar cubic Bezier curve in detais,and thence give a classification of planar cubic Bezier curves. This paper is prepared under the guidance of Professor Su Buchin.     

RELU DEEP NEURAL NETWORKS AND LINEAR FINITE ELEMENTS

In this paper, we investigate the relationship between deep neural networks (DNN) with rectified linear unit (ReLU) function as the activation function and continuous piecewise linear (CPWL) functions, especially CPWL functions from the simplicial linear finite element method (FEM). We first consider the special case of FEM. By exploring the DNN representation of its nodal basis functions, we present a ReLU DNN representation of CPWL in FEM. We theoretically establish that at least $2$ hidden layers are needed in a ReLU DNN to represent any linear finite element functions in $\Omega \subseteq \mathbb{R}^d$ when $d\ge2$. Consequently, for $d=2,3$ which are often encountered in scientific and engineering computing, the minimal number of two hidden layers are necessary and sufficient for any CPWL function to be represented by a ReLU DNN. Then we include a detailed account on how a general CPWL in $\mathbb R^d$ can be represented by a ReLU DNN with at most $\lceil\log_2(d+1)\rceil$ hidden layers and we also give an estimation of the number of neurons in DNN that are needed in such a representation. Furthermore, using the relationship between DNN and FEM, we theoretically argue that a special class of DNN models with low bit-width are still expected to have an adequate representation power in applications. Finally, as a proof of concept, we present some numerical results for using ReLU DNNs to solve a two-point boundary problem to demonstrate the potential of applying DNN for numerical solution of partial differential equations.     

An efficient improvement of gift wrapping algorithm for computing the convex hull of a finite set of points in ℝ n $\mathbb {R}^{n}$

Numerical Algorithms - In this paper, we present an efficient improvement of gift wrapping algorithm for determining the convex hull of a finite set of points in $\mathbb {R}^{n}$ space, applying...     

Approximate Lie $\ast$-Derivations on $\rho$-complete Convex Modular algebras

In this paper, we obtain generalized Hyers--Ulam stability results of a $(m,n)$-Cauchy-Jensen functional equation associated with approximate Lie $*$-derivations on $\rho$-complete convex modular $*$-algebras $\chi_\rho$ with $\Delta_\mu$-condition on the convex modular $\rho$.     

Bounded approximation properties in non‐archimedean Banach spaces

Some non‐archimedean bounded approximation properties are introduced and studied in this paper. As an application, an affirmative answer is given, for non‐spherically complete base fields, to the following problem, posed in 13 , p. 95: Does there exist an absolutely convex edged set B in a non‐archimedean locally convex space such that its closure $\overline{B}Some non‐archimedean bounded approximation properties are introduced and studied in this paper. As an application, an affirmative answer is given, for non‐spherically complete base fields, to the following problem, posed in 13 , p. 95: Does there exist an absolutely convex edged set B in a non‐archimedean locally convex space such that its closure $\overline{B}$ is not edged?