In the paper we give a complete classification of 2-dimensional evolution algebras over algebraically closed fields, we compare the list of representatives of the isomorphism classes with that of obtained earlier by t...
详细信息
This paper addresses the problem of piecewise linear approximation of implicit surfaces. We first give a criterion ensuring that the zero-set of a smooth function and the one of a piecewise linear approximation of it ...
详细信息
This paper addresses the problem of piecewise linear approximation of implicit surfaces. We first give a criterion ensuring that the zero-set of a smooth function and the one of a piecewise linear approximation of it are isotopic. Then, we deduce from this criterion an implicit surface meshing algorithm certifying that the output mesh is isotopic to the actual implicit surface. This is the first algorithm achieving this goal in a provably correct way.
The authors extend R.B. Boppana's results (1989) in two ways. They first show that his two lower bounds hold for general read-once formulae, not necessarily monotone, that may even include exclusive-or gates. They...
This paper addresses the problem of jointly clustering two segmentations of closely correlated images. We focus in particular on the application of reconstructing neuronal structures in over-segmented electron microsc...
详细信息
This paper addresses the problem of jointly clustering two segmentations of closely correlated images. We focus in particular on the application of reconstructing neuronal structures in over-segmented electron microscopy images. We formulate the problem of co-clustering as a quadratic semi-assignment problem and investigate convex relaxations using semidefinite and linear programming. We further introduce a linear programming method with manageable number of constraints and present an approach for learning the cost function. Our method increases computational efficiency by orders of magnitude while maintaining accuracy, automatically finds the optimal number of clusters, and empirically tends to produce binary assignment solutions. We illustrate our approach in simulations and in experiments with real EM data.
We present exact algorithms for finding a solution to the two-dimensional translational containment problem: find translations for k polygons which place them inside a polygonal container without overlApplng. We also ...
详细信息
ISBN:
(纸本)0898713498
We present exact algorithms for finding a solution to the two-dimensional translational containment problem: find translations for k polygons which place them inside a polygonal container without overlApplng. We also give an approximate algorithm: given any ϵ, it finds a set of translations such that no point of any polygon is more than 2ϵ inside the boundary of any other polygon or outside the container. The term &CN denotes a containment problem in which the κ polygons are convex and the container is nonconvex, and fcNN denotes nonconvex polygons and container. The polygons have up to m vertices, and the container has n vertices, where n > m (typically). We give exact algorithms for the following: 2CN in O(mnlogn) time, 3CN in O(m3ralogn) time, and ANN in O((mti)2κ+1LP(2κmn, + k2m2)) time, where LP(a, 6) is the time to solve a linear program with o variables and 6 constraints. We present an approximate algorithm for κNN whose running time is O((1/ϵ)κ log (1/ϵ)κ5slog s), where s is the largest number of vertices of any polygon that can generated by applying a certain set of operations to the input. We have no polynomial bound on s, but, in practice, it is usually not more than quadratic in n.
This paper describes a method for finding the least fixed points of higher-order functions over finite domains using symbolic manipulation. Fixed point finding is an essential component in the calculation of abstract ...
This paper describes a method for finding the least fixed points of higher-order functions over finite domains using symbolic manipulation. Fixed point finding is an essential component in the calculation of abstract semantics of functional programs, providing the foundation for program analyses based on abstract interpretation. Previous methods for fixed point finding have primarily used semantic approaches, which often must traverse large portions of the semantic domain even for simple programs. This paper provides the theoretical framework for a syntax-based analysis that is potentially very fast. The proposed syntactic method is based on an augmented simply typed lambda calculus where the symbolic representation of each function produced in the fixed point iteration is transformed to a syntactic normal form. Normal forms resulting from successive iterations are then compared syntactically to determine their ordering in the semantic domain, and to decide whether a fixed point has been reached. We show the method to be sound, complete and compositional. Examples are presented to show how this method can be used to perform strictness analysis for higher-order functions over non-flat domains. Our method is compositional in the sense that the strictness property of an expression can be easily calculated from those of its sub-expressions. This is contrary to most strictness analysers, where the strictness property of an expression has to be computed anew whenever one of its subexpressions changes. We also compare our approach with recent developments in strictness analysis.
Wireless sensor networks are tightly associated with the underlying environment in which the sensors are deployed. The global topology of the network is of great importance to both sensor network applications and the ...
详细信息
ISBN:
(纸本)1595932860
Wireless sensor networks are tightly associated with the underlying environment in which the sensors are deployed. The global topology of the network is of great importance to both sensor network applications and the implementation of networking functionalities. In this paper we study the problem of topology discovery, in particular, identifying boundaries in a sensor network. Suppose a large number of sensor nodes are scattered in a geometric region, with nearby nodes communicating with each other directly. Our goal is to find the boundary nodes by using only connectivity information. We do not assume any knowledge of the node locations or inter-distances, nor do we enforce that the communication graph follows the unit disk graph model. We propose a simple, distributed algorithm that correctly detects nodes on the boundaries and connects them into meaningful boundary cycles. We obtain as a byproduct the medial axis of the sensor field, which has applications in creating virtual coordinates for routing. We show by extensive simulation that the algorithm gives good results even for networks with low density. We also prove rigorously the correctness of the algorithm for continuous geometric domains. Copyright 2006 ACM.
In order to model the behaviour of open concurrent systems by means of Petri nets, we introduce open Petri nets, a generalization of the ordinary model where some places, designated as open, represent an interface of ...
详细信息
Binary unlabeled ordered trees (further called binary trees) were studied at least since Euler, who enumerated them, The number of such trees with n nodes is now known as the Catalan number. Over the years various int...
详细信息
ISBN:
(纸本)0898715962
Binary unlabeled ordered trees (further called binary trees) were studied at least since Euler, who enumerated them, The number of such trees with n nodes is now known as the Catalan number. Over the years various interesting questions about the statistics of such trees were investigated (e.g., height and path length distributions for a randomly selected tree). Binary trees find an abundance of applications in computerscience. However, recently Seroussi posed a new and interesting problem motivated by information theory considerations: how many binary trees of a given path length (sum of depths) are there? This question arose in the study of universal types of sequences. Seroussi declares that two sequences of length p have the same universal type if they generate the same set of phrases in the incremental parsing of the LempelZiv'78 scheme. (He then proves that sequences of the same type converge to the same empirical distribution.) It turns out that the number of distinct types of sequences of length p corresponds to the number of binary (unlabeled and ordered) trees, Tp, of given path length p (and also the number of different Lempel-Ziv'78 parsings of length p sequences). We first show that the number of binary trees with given path length p is asymptotically equal to Tp ∼ 22p/(log2p). Then we establish various limiting distributions for the number of nodes (number of phrases in the Lempel-Ziv'78 scheme) when a tree is selected randomly among all Tp trees. Throughout, we use methods of analytic algorithmics such as generating functions and complex asymptotics, as well as methods of appliedmath.matics such as the WKB method and matched asymptotics.
暂无评论