On the performance of peeling algorithms

The peeling of a d-dimensional set of points is usually performed with successive calls to a convex hull algorithm; the optimal worst-case convex hull algorithm, known to have an O(n^˙ Log (n)) execution time, may give an O(n^˙n^˙ Log (n)) to peel all the set; an O(n^˙n) convex hull algorithm, m being the number of extremal points, is shown to peel every set with an O(n-n) time, and proved to be optimal; an implementation of this algorithm is given for planar sets and spatial sets, but the latter give only an approximate O(n^˙n) performance.     

TERNARY OPERATIONS AS PRIMITIVE NOTIONS FOR PLANE GEOMETRY II

We proved in the first part [1] that plane geometry over Pythagorean fields is axiomatizable by quantifier-free axioms in a language with three individual constants, one binary and three ternary operation symbols. In this paper we prove that two of these operation symbols are superfluous.     

On the Spectral Radius of Trees with the Given Diameter d

Let T denote a tree with the diameter d(d≥2) and order n. Let P^*d,r,n-d-1denote the tree obtained by identifying the rth vertex of path Pd l and the center of starKl,K1,n-d-1, where r = r(d) is the integer part about d 2/2. Then p(T)≤ p(P^*d,r,n-d-1), andequality holds if and only if T≌P^*d,r,n-d-1     

Polynomial-time approximation schemes for packing and piercing fat objects

We consider two problems: given a collection of n fat objects in a fixed dimension, (1) ( packing) find the maximum subcollection of pairwise disjoint objects, and (2) ( piercing) find the minimum point set that intersects every object. Recently, Erlebach, Jansen, and Seidel gave a polynomial-time approximation scheme (PTAS) for the packing problem, based on a shifted hierarchical subdivision method. Using shifted quadtrees, we describe a similar algorithm for packing but with a smaller time bound. Erlebach et al.'s algorithm requires polynomial space. We describe a different algorithm, based on geometric separators, that requires only linear space. This algorithm can also be applied to piercing, yielding the first PTAS for that problem.     

介质光波导的数值计算及近似方法

综述介质光波导中模式分析方法的最新进展。着重分析严格的数值分析方法及近似方法最近的研究进展。依据方法的计算精确度、计算效率和计算复杂度等因素．对有限元法和有限差分法这两种数值分析方法以及有效指数法和频谱指数法等近似方法进行讨论。论述磁光波导的分析方法。     

Heat Kernel Asymptotics of Zaremba Boundary Value Problem

The Zaremba boundary-value problem is a boundary value problem for Laplace-type second-order partial differential operators acting on smooth sections of a vector bundle over a smooth compact Riemannian manifold with smooth boundary but with discontinuous boundary conditions, which include Dirichlet boundary conditions on one part of the boundary and Neumann boundary conditions on another part of the boundary. We study the heat kernel asymptotics of Zaremba boundary value problem. The construction of the asymptotic solution of the heat equation is described in detail and the heat kernel is computed explicitly in the leading approximation. Some of the first nontrivial coefficients of the heat kernel asymptotic expansion are computed explicitly. This revised version was published online in July 2006 with corrections to the Cover Date.     

Dispersion Characteristics of Waveguide Arrays in Optical Spectrum Analyzers

Formulas for calculating the spectral characteristics of waveguide arrays, which are incorporated into waveguide spectrum analyzers based on planar waveguides, channel waveguides, and fiber optical waveguides, are derived taking into account the contribution of both the waveguide dispersion and the material dispersion to the dispersion factor. These formulas are used to study the dependence of the dispersion factor on the waveguide-system parameters for specific models of waveguide arrays. It is shown that consideration of contributions of the waveguide dispersion and material dispersion can affect profoundly the spectral characteristics of waveguide arrays.     

基于Karhunen-Loève变换和小波谱特征矢量量化的三维谱像数据压缩

提出了基于Karhunen Lo埁ｖｅ变换的小波谱特征矢量量化三维谱像数据压缩方法耍幔颍瑁酰睿澹?Lo埁ｖｅ变换 /小波变换 /小波谱特征矢量量化方法应用了Karhunen Lo埁ｖｅ变换的消除谱相关性优良性能 ,应用二维小波变换消除空间相关性 ,在小波变换域内应用二维集分割嵌入块编码和一维谱特征矢量量化对三维谱像数据压缩 ,获得较高的压缩性能。实验结果表明 :Karhunen Lo埁ｖｅ变换 /小波变换 /小波谱特征矢量量化编码比Karhunen Lo埁ｖｅ变换 /小波变换 /改进对块零树编码和Karhunen Lo埁ｖｅ变换 /小波变换 /快速矢量量化编码方法在同样压缩比条件下 ,峰值信噪比提高 2dB和 1dB以上 ,而速度提高了 1.5和 8倍 ,整体压缩性能有较大的提高     

Tail probabilities of the limiting null distributions of the Anderson–Stephens statistics

For the purpose of testing the spherical uniformity based on i.i.d. directional data (unit vectors) z_i, i=1,…,n, Anderson and Stephens (Biometrika 59 (1972) 613–621) proposed testing procedures based on the statistics S_max=max_u S(u) and S_min=min_u S(u), where u is a unit vector and nS(u) is the sum of squares of u′z_i's. In this paper, we also consider another test statistic S_range=S_max−S_min. We provide formulas for the P-values of S_max, S_min, S_range by approximating tail probabilities of the limiting null distributions by means of the tube method, an integral-geometric approach for evaluating tail probability of the maximum of a Gaussian random field. Monte Carlo simulations for examining the accuracy of the approximation and for the power comparison of the statistics are given.     

A Representation of a Family of Secret Sharing Matroids

Deciding whether a matroid is secret sharing or not is a well-known open problem. In Ng and Walker [6] it was shown that a matroid decomposes into uniform matroids under strong connectivity. The question then becomes as follows: when is a matroid m with N uniform components secret sharing? When N = 1, m corresponds to a uniform matroid and hence is secret sharing. In this paper we show, by constructing a representation using projective geometry, that all connected matroids with two uniform components are secret sharing