Hierarchical Convex Approximation of 3D Shapes for Fast Region Selection

Given a 3D solid model S represented by a tetrahedral mesh, we describe a novel algorithm to compute a hierarchy of convex polyhedra that tightly enclose S. The hierarchy can be browsed at interactive speed on a modern PC and it is useful for implementing an intuitive feature selection paradigm for 3D editing environments. Convex parts often coincide with perceptually relevant shape components and, for their identification, existing methods rely on the boundary surface only. In contrast, we show that the notion of part concavity can be expressed and implemented more intuitively and efficiently by exploiting a tetrahedrization of the shape volume. The method proposed is completely automatic, and generates a tree of convex polyhedra in which the root is the convex hull of the whole shape, and the leaves are the tetrahedra of the input mesh. The algorithm proceeds bottom‐up by hierarchically clustering tetrahedra into nearly convex aggregations, and the whole process is significantly fast. We prove that, in the average case, for a mesh of n tetrahedra O(n log² n) operations are sufficient to compute the whole tree.     

Faddeev Random Phase Approximation for molecules

The Faddeev Random Phase Approximation is a Green?s function technique that makes use of Faddeev-equations to couple two-particle–one-hole and two-hole–one-particle excitations to the single-particle spectrum. Solving these equations implies an infinite partial summation of the perturbation expansion of the self energy. This method goes beyond the third-order Algebraic Diagrammatic Approximation by treating both the particle–hole and particle–particle interactions at the Random Phase Approximation-level. This paper presents the first results of our calculations for diatomic molecules.     

Nonrigid Matching of Undersampled Shapes via Medial Diffusion

We introduce medial diffusion for the matching of undersampled shapes undergoing a nonrigid deformation. We construct a diffusion process with respect to the medial axis of a shape, and use the quantity of heat diffusion as a measure which is both tolerant of missing data and approximately invariant to nonrigid deformations. A notable aspect of our approach is that we do not define the diffusion on the shape's medial axis, or similar medial representation. Instead, we construct the diffusion process directly on the shape. This permits the diffusion process to better capture surface features, such as varying spherical and cylindrical parts, as well as combine with other surface‐based diffusion processes. We show how to use medial diffusion to detect intrinsic symmetries, and for computing correspondences between pairs of shapes, wherein shapes contain substantial missing data.     

Random 2 XORSAT Phase Transition

We consider the 2-XOR satisfiability problem, in which each instance is a formula that is a conjunction of Boolean equations of the form x ⊕ y=0 or x ⊕ y=1. Formula of size m on n Boolean variables are chosen uniformly at random from among all ((n(n-1)) || (m)){n(n-1)\choose m} possible choices. When c<1/2 and as n tends to infinity, the probability p(n,m=cn) that a random 2-XOR formula is satisfiable, tends to the threshold function exp (c/2)⋅(1−2c)^1/4. This gives the asymptotic behavior of random 2-XOR formula in the SAT/UNSAT subcritical phase transition. In this paper, we first prove that the error term in this subcritical region is O(n ⁻¹). Then, in the critical region c=1/2, we prove that p(n,n/2)=Θ(n ^−1/12). Our study relies on the symbolic method and analytical tools coming from generating function theory which also enable us to describe the evolution of n^1/12 p(n,\fracn2(1+mn^-1/3))n^{1/12}\ p(n,\frac{n}{2}(1+\mu n^{-1/3})) as a function of μ. Thus, we propose a complete picture of the finite size scaling associated to the subcritical and critical regions of 2-XORSAT transition.     

基于分解的多值模型的逼近关系

多值模型可用于对包含不确定与不一致信息的软件系统进行建模与验证。提出了采用基于分解的方式来刻画多值模型之间的逼近关系,这为采用抽象方法解决模型检测时所产生的状态爆炸问题奠定了理论基础。为此,首先给出了多值模型分解为多个三值模型的方法,并且证明了任意μ演算公式在多值模型上的检测结果等于在分解后所有三值模型上的检测结果的合并。进一步,由三值模型上的混合模拟关系给出了多值模型间逼近关系的结构定义,并证明对于任意给定的两个满足逼近关系的多值模型,μ演算公式在其上的检测结果在信息序关系上得以保持。     

Robust Region Detection via Consensus Segmentation of Deformable Shapes

We consider the problem of stable region detection and segmentation of deformable shapes. We pursue this goal by determining a consensus segmentation from a heterogeneous ensemble of putative segmentations, which are generated by a clustering process on an intrinsic embedding of the shape. The intuition is that the consensus segmentation, which relies on aggregate statistics gathered from the segmentations in the ensemble, can reveal components in the shape that are more stable to deformations than the single baseline segmentations. Compared to the existing approaches, our solution exhibits higher robustness and repeatability throughout a wide spectrum of non‐rigid transformations. It is computationally efficient, naturally extendible to point clouds, and remains semantically stable even across different object classes. A quantitative evaluation on standard datasets confirms the potentiality of our method as a valid tool for deformable shape analysis.     

Continuous State Dynamic Programming via Nonexpansive Approximation

This paper studies fitted value iteration for continuous state numerical dynamic programming using nonexpansive function approximators. A number of approximation schemes are discussed. The main contribution is to provide error bounds for approximate optimal policies generated by the value iteration algorithm.      

模拟电路行为级建模的SGWD逼近算法

提出采用一种规范化的香农小波(distributed approximation function, SGWD)逼近算法建立模拟电路单元模块的行为级模型.为降低逼近的边界误差,同时提出了周期性展开和偶对称映射2种预处理算法.周期性展开算法需要对电路模块的原始I/O函数做一定变形,构造出周期函数后再进行逼近;偶对称映射算法则是将I/O函数在边界点处进行偶对称翻转,然后采用SGWD逼近算法建模.与传统的建模方法,如多项式逼近等算法相比,该方法结合了边界误差降低技术的SGWD逼近算法具有更低的计算复杂度,并能达到更高的建模精度.     

人工智能问题中的相变现象研究

在人工智能研究领域的很多问题中存在着相变现象(phase transition)。问题中的某个参数发生较小的变化便会引起问题的某个属性发生突变。相变现象与问题求解结构有很大关系,将从相变现象的发展、相关概念以及相变现象与问题求解的关系等方面对相变现象做全面的论述,提出了有待解决的开放性问题,并对相变现象的研究给以总结和展望。     

Approximation of multidimensional Stefan-like problems via hyperbolic relaxation

An effective time delay in the governing equations, as proposed in [8], is further examined here. The resulting hyperbolic Stefan problem is mainly viewed as a perturbation of the traditional one. Asymptotic energy error estimates are derived for the three physical unknowns (heat flux, temperature and enthalpy) in accordance with various regularity assumptions on the initial data. This paper was partially supported by NSF Grant DMS-8805218 and by MPI (Fondi per la ricerca scientifica) and CNR of Italy.     

基于相变和似然性的多相图像分割方法

Sine- Sinc模型是一种基于材料科学中Modica-Mortola物理相变原理的多相图像分割方法.针对该模型分割结果不完全、易受噪声和亮度不均匀性影响的问题,提出了一个改进的Sine- Exp-Gauss多相图像分割模型.基于Sine-Sinc模型,Sine- Exp-Gauss模型用指数函数代替Sine-Sinc模型的Sinc函数,并从分段常数图像假设推广到高斯分布函数图像假设;模型偏微分方程的数值解采用凸函数分裂方法迭代,获得每个相的局部最优解,同时给出一种标准初始化方法使迭代过程易于收敛到理想局部极小值.与Sine- Sinc模型和偏差矫正模型相比,实验结果证明Sine- Exp-Gauss模型在噪声消除和自偏差矫正方面都更加鲁棒.     

Relating Z and First-Order Logic

Despite being widely regarded as a gloss on first-order logic and set theory, Z has not been found to be very supportive of proof. This paper attempts to distinguish between the different philosophies of proof in Z. It discusses some of the issues which must be addressed in creating a proof technology for Z, namely schemas, undefinedness, and what kind of logic to use. Received February 2000 / Accepted in revised form April 2000     

Automated Discovery of Numerical Approximation Formulae via Genetic Programming

This paper describes the use of genetic programming to perform automated discovery of numerical approximation formulae. We present results involving rediscovery of known approximations for Harmonic numbers, discovery of rational polynomial approximations for functions of one or more variables, and refinement of existing approximations through both approximation of their error function and incorporation of the approximation as a program tree in the initial GP population. Evolved rational polynomial approximations are compared to Padé approximations obtained through the Maple symbolic mathematics package. We find that approximations evolved by GP can be superior to Padé approximations given certain tradeoffs between approximation cost and accuracy, and that GP is able to evolve approximations in circumstances where the Padé approximation technique cannot be applied. We conclude that genetic programming is a powerful and effective approach that complements but does not replace existing techniques from numerical analysis.     

正则3-SAT问题的相变现象

通过对3-CNF公式加以限制,要求其中每个变元出现的次数相同,引出正则3-SAT问题。进一步,通过对两种子句产生机制形成的(3,s)-CNF公式进行可满足性观察,发现在规模较小的情况下,正则3-CNF公式比非正则3-CNF公式更容易满足。从而推测与非正则3-SAT问题相比,正则3-SAT问题的相变点有偏移现象。最后,从变元自由度的角度对这一现象给出了定性解释。     

Hardware-Software Collaborative Techniques for Runtime Profiling and Phase Transition Detection

Dynamic optimization relies on runtime profile information to improve the performance of program execution. Traditional profiling techniques incur significant overhead and are not suitable for dynamic optimization. In this paper, a new profiling technique is proposed, that incorporates the strength of both software and hardware to achieve near-zero overhead profiling. The compiler passes profiling requests as a few bits of information in branch instructions to the hardware, and the processor executes profiling operations asynchronously in available free slots or on dedicated hardware. The compiler instrumentation of this technique is implemented using an Itanium research compiler. The result shows that the accurate block profiling incurs very little overhead to the user program in terms of the program scheduling cycles. For example, the average overhead is 0.6% for the SPECint95 benchmarks. The hardware support required for the new profiling is practical. The technique is extended to collect edge profiles for continuous phase transition detection. It is believed that the hardware-software collaborative scheme will enable many profile-driven dynamic optimizations for EPIC processors such as the Itanium processors.     

从混沌到清晰--从品牌创建看网通公司的转型

中国网络通信集团有限公司（简称网通公司）是2002年在对原中国电信公司进行南北拆分的基础上．中国电信的北方10省合并网通控股（小网通）和吉通公司后，重新成立的新公司。依托固话（包括小灵通）和宽带两个主要业务。网通公司进行了艰苦的市场开拓。这时正值中国的电信市场进入品牌经营阶段．同时又逢国际范围内的电信运营商转型时期．     

On First-Order Logic and CPDA Graphs

Higher-order pushdown automata (n-PDA) are abstract machines equipped with a nested ‘stack of stacks of stacks’. Collapsible pushdown automata (n-CPDA) extend these devices by adding ‘links’ to the stack and are equi-expressive for tree generation with simply typed λY terms. Whilst the configuration graphs of HOPDA are well understood, relatively little is known about the CPDA graphs. The order-2 CPDA graphs already have undecidable MSO theories but it was only recently shown by Kartzow (Log. Methods Comput. Sci. 9(1), 2013) that first-order logic is decidable at the second level. In this paper we show the surprising result that first-order logic ceases to be decidable at order-3 and above. We delimit the fragments of the decision problem to which our undecidability result applies in terms of quantifer alternation and the orders of CPDA links used. Additionally we exhibit a natural sub-hierarchy enjoying limited decidability.     

Event-Triggered Distributed Cooperative Learning Algorithms over Networks via Wavelet Approximation

Neural Processing Letters - This paper investigates the problem of event-triggered distributed cooperative learning (DCL) over networks based on wavelet approximation theory, where each node only...