最小封堵圈的扩张算法设计

在发生突发事件之后,及时制定有效的封堵方案才能掌握抓捕嫌疑犯的主动权.提出了对逃跑罪犯实施完全封堵的最小包围圈的计算机算法,通过规则图形的仿真演示,验证了该算法的正确性.最后以某市案发时候的警力分布和交通图作为实例,模拟了对嫌疑犯实施封堵时计算最小包围圈的最优方案.结果证明该算法具有简洁、可靠的优点.     

一些组合地图新算法的实现

本文主要讨论组合地图列举问题.刘的一部专著中提出了一个判定两个地图是否同构的算法.该算法的时间复杂度为O(m2),其中m为下图的规模.在此基础上,本文给出一个用于地图列举以及进而计算任意连通下图的地图亏格分布的通用算法.本文所得结果比之前文献中所给结果更优.     

On the Constructive Algorithm for Stability Analysis of an Equilibrium Point of a Periodic Hamiltonian System with Two Degrees of Freedom in the Second-order Resonance Case

This paper is concerned with a nonautonomous Hamiltonian system with two degrees of freedom whose Hamiltonian is a 2π-periodic function of time and analytic in a neighborhood of an equilibrium point. It is assumed that the system exhibits a secondorder resonance, i. e., the system linearized in a neighborhood of the equilibrium point has a double multiplier equal to ?1. The case of general position is considered when the monodromy matrix is not reduced to diagonal form and the equilibrium point is linearly unstable. In this case, a nonlinear analysis is required to draw conclusions on the stability (or instability) of the equilibrium point in the complete system.In this paper, a constructive algorithm for a rigorous stability analysis of the equilibrium point of the above-mentioned system is presented. This algorithm has been developed on the basis of a method proposed in [1]. The main idea of this method is to construct and normalize a symplectic map generated by the phase flow of a Hamiltonian system.It is shown that the normal form of the Hamiltonian function and the generating function of the corresponding symplectic map contain no third-degree terms. Explicit formulae are obtained which allow one to calculate the coefficients of the normal form of the Hamiltonian in terms of the coefficients of the generating function of a symplectic map.The developed algorithm is applied to solve the problem of stability of resonant rotations of a symmetric satellite.     

基于颜色和方向特征区域对比度的显著性检测模型

视觉显著性检测是很多计算机视觉任务的重要步骤,提出了一种基于颜色、方向特征和空间位置关系相结合的区域对比显著性检测算法.首先用基于图论的算法将图像分割成若干区域,结合区域间颜色特征和空间对比度计算出颜色显著图.同时采用基于纹理特征的算法分割图像,通过方向特征和空间对比度得到方向显著图.最后将二者结合得到最终显著图.在国际现有公开测试集上进行仿真实验,并与其它显著性检测方法进行对比,检测结果更加准确、合理,证明此算法切实可行.     

On the reconstruction of Dirichlet-to-Neumann map in inverse scattering problems with stability estimates

Consider the determination of Dirichlet-to-Neumann (D-to-N) map from the far-field pattern in inverse scattering problems, which is the key step in some recently developed inversion schemes such as probe method. Essentially, this problem is related to the reconstruction of the scattered wave from its far-field data. We firstly prove the well-known uniqueness result of the D-to-N map from the far-field pattern using a new scheme based on the mixed reciprocity principle. The advantage of this new proof scheme is that it provides an efficient algorithm for computing the D-to-N map, avoiding the numerical differentiation for the scattered wave. Then combining with the classical potential theory, a simple and feasible regularizing reconstruction scheme for the D-to-N map is proposed. Finally the stability estimate for the reconstruction with noisy input data is rigorously analyzed.     

Computing the Writhing Number of a Polygonal Knot

The writhing number measures the global geometry of a closed space curve or knot. We show that this measure is related to the average winding number of its Gauss map. Using this relationship, we give an algorithm for computing the writhing number for a polygonal knot with n edges in time roughly proportional to n^1.6. We also implement a different, simple algorithm and provide experimental evidence for its practical efficiency.     

Characterization and algorithms of curve map graphs

A curve map is a planar map obtained by dividing the Euclidean plane into a finite number of regions by a finite set of two-way infinite Jordan curves (every one dividing the plane in two regions) such that no two curves intersect in more than one point. A line map is a curve map obtained by Jordan curves being all straight lines. A graph is called a curve map graph respectively a line map graph if it is the dual of a curve map respectively of a line map.In this paper we give a characterization of the curve map graphs and we describe a polynomial time algorithm for their recognition.     

Error analysis and preconditioning for an enhanced DtN-FE algorithm for exterior scattering problems

In this paper we present an error analysis for a high-order accurate combined Dirichlet-to-Neumann (DtN) map/finite element (FE) algorithm for solving two-dimensional exterior scattering problems. We advocate the use of an exact DtN (or Steklov–Poincaré) map at an artificial boundary exterior to the scatterer to truncate the unbounded computational region. The advantage of using an exact DtN map is that it provides a transparent condition which does not reflect scattered waves unphysically. Our algorithm allows for the specification of quite general artificial boundaries which are perturbations of a circle. To compute the DtN map on such a geometry we utilize a boundary perturbation method based upon recent theoretical work concerning the analyticity of the DtN map. We also present some preliminary work concerning the preconditioning of the resulting system of linear equations, including numerical experiments.     

Cryptanalyzing a nonlinear chaotic algorithm (NCA) for image encryption

This paper describes the security weakness of a recently proposed image encryption algorithm based on a logistic-like new chaotic map. We show that the chaotic map’s distribution is far from ideal, thus making it a bad candidate as a pseudo-random stream generator. As a consequence, the images encrypted with this algorithm are shown to be breakable through different attacks of variable complexity.     

Steganographic algorithm based on a chaotic map

In this paper, we suggest a new steganographic spatial domain algorithm based on a single chaotic map. Unlike most existing steganographic algorithms, the proposed algorithm uses one chaotic map to determine the pixel position of the host color image, the channel (red, green or blue) and the bit position of the targeted value in which a sensitive information bit can be hidden. Furthermore, this algorithm can be regarded as a variable-sized embedding algorithm. Experimental results demonstrate that this algorithm can defeat many existing steganalytic attacks. In comparison with existing steganographic spatial domain based algorithms, the suggested algorithm is shown to have some advantages over existing ones, namely, larger key space and a higher level of security against some existing attacks.     

An algorithm to solve polyhedral convex set optimization problems

An algorithm which computes a solution of a set optimization problem is provided. The graph of the objective map is assumed to be given by finitely many linear inequalities. A solution is understood to be a set of points in the domain satisfying two conditions: the attainment of the infimum and minimality with respect to a set relation. In the first phase of the algorithm, a linear vector optimization problem, called the vectorial relaxation, is solved. The resulting pre-solution yields the attainment of the infimum but, in general, not minimality. In the second phase of the algorithm, minimality is established by solving certain linear programs in combination with vertex enumeration of some values of the objective map.     

The sphere method and the robustness of the ellipsoid algorithm

We present a method for implementing the ellipsoid algorithm, whose basic iterative step is a linear row manipulation on the matrix of inequalities. This step is somewhat similar to a simplex iteration, and may give a clue to the relation between the two algorithms. Geometrically, the step amounts to performing affine transformations which map the ellipsoids onto a fixed sphere. The method was tried successfully on linear programs with up to 50 variables, some of which required more than 24 000 iterations. Geometrical properties of the iteration suggest that the ellipsoid algorithm is numerically robust, which is supported by our computational experience.     

A Numerical Method for Conformal Mapping

A method is developed for constructing the conformal map ofa distorted region onto a rectangle. A discrete Fourier transformis used to map the boundary of the region onto the boundaryof the rectangle; the resulting equations may be solved usinga fast Fourier transform algorithm. The map for internal pointsmay then be constructed using a standard Laplace equation solver.The method is computationally competitive, and is applicableto field problems, for instance in fluid mechanics.     

Error analysis of an enhanced DtN-FE method for exterior scattering problems

In this work we analyze the convergence of the high-order Enhanced DtN-FEM algorithm, described in our previous work (Nicholls and Nigam, J. Comput. Phys. 194:278–303, 2004), for solving exterior acoustic scattering problems in . This algorithm consists of using an exact Dirichlet-to-Neumann (DtN) map on a hypersurface enclosing the scatterer, where the hypersurface is a perturbation of a circle, and, in practice, the perturbation can be very large. Our theoretical work had shown the DtN map was analytic as a function of this perturbation. In the present work, we carefully analyze the error introduced by virtue of using this algorithm. Specifically, we give a full account of the error introduced by truncating the DtN map at a finite order in the perturbation expansion, and study the well-posedness of the associated formulation. During computation, the Fourier series of the Dirichlet data on the artificial boundary must be truncated. To deal with the ensuing loss of uniqueness of solutions, we propose a modified DtN map, and prove well-posedness of the resulting problem. We quantify the spectral error introduced due to this truncation of the data. The key tools in the analysis include a new theorem on the analyticity of the DtN map in a suitable Sobolev space, and another on the perturbation of non-self-adjoint Fredholm operators.     

Characterization of curve map graphs

In this paper we provide a characterization of curve map graphs as defined by Gavril and Schönheim, and also give a recognition algorithm for them.A curve map graph is the dual of a map obtained by placing a finite number of two-way infinite Jordan curves in the Euclidean plane in such a way that each curve divides the plane into two regions, no two curves intersect in more than one point, and any two curves which intersect at a point cross at that point.Our method is based on Gavril and Schönheim's approach, but corrects several difficulties in their characterization.     

In honour of professor Solomon G. Mikhlin on the occasion of his seventieth birthday

The system identification problem, within the context of this paper, is the determination of an input-output operator A based upon a limited amount of information. We consider the case where A is a linear, time invariant map on an appropriate function space and develop an algorithm for determining A from knowledge of input-output pairs in A.     

Constructing the free erection of a geometry

The set of all erections of a given geometry is a lattice for the geometric weak map order, whose largest element is called the free erection. An algorithm is described for effectively constructing the free erection of any geometry G, and for determining whether a given flat of G is essential.     

The Leibniz formula for the covariant derivative and some of its applications

We obtain a formula for the higher covariant derivatives on the tensor product of vector bundles which is a wide generalization of the classical Leibniz formula. We construct an algorithm for the calculation of the part of the Taylor series of the double exponential map linear with respect to the second variable.     

On the linear classification of even and odd permutation matrices and the complexity of computing the permanent

The problem of linear classification of the parity of permutation matrices is studied. This problem is related to the analysis of complexity of a class of algorithms designed for computing the permanent of a matrix that generalizes the Kasteleyn algorithm. Exponential lower bounds on the magnitude of the coefficients of the functional that classifies the even and odd permutation matrices in the case of the field of real numbers and similar linear lower bounds on the rank of the classifying map for the case of the field of characteristic 2 are obtained.     

One-way hash function construction based on chaotic map network

A novel chaotic hash algorithm based on a network structure formed by 16 chaotic maps is proposed. The original message is first padded with zeros to make the length a multiple of four. Then it is divided into a number of blocks each contains 4 bytes. In the hashing process, the blocks are mixed together by the chaotic map network since the initial value and the control parameter of each tent map are dynamically determined by the output of its neighbors. To enhance the confusion and diffusion effect, the cipher block chaining (CBC) mode is adopted in the algorithm. Theoretic analyses and numerical simulations both show that the proposed hash algorithm possesses good statistical properties, strong collision resistance and high flexibility, as required by practical keyed hash functions.