Twofold adaptive partition of unity implicits

Partition of Unity Implicits (PUI) has been recently introduced for surface reconstruction from point clouds. In this work, we propose a PUI method that employs a set of well-observed solutions in order to produce geometrically pleasant results without requiring time consuming or mathematically overloaded computations. One feature of our technique is the use of multivariate orthogonal polynomials in the least-squares approximation, which allows the recursive refinement of the local fittings in terms of the degree of the polynomial. However, since the use of high-order approximations based only on the number of available points is not reliable, we introduce the concept of coverage domain. In addition, the method relies on the use of an algebraically defined triangulation to handle two important tasks in PUI: the spatial decomposition and an adaptive polygonization. As the spatial subdivision is based on tetrahedra, the generated mesh may present poorly-shaped triangles that are improved in this work by means a specific vertex displacement technique. Furthermore, we also address sharp features and raw data treatment. A further contribution is based on the PUI locality property that leads to an intuitive scheme for improving or repairing the surface by means of editing local functions.

Conformal deformation of equilibrium measures in normal random ensembles

We investigate the eigenvalue statistics of ensembles of normal random matrices when their order N tends to infinite. In the model, the eigenvalues have uniform density within a region determined by a simple analytic polynomial curve. We study the conformal deformations of equilibrium measures of normal random ensembles to the real line and give sufficient conditions for it to weakly converge to a Wigner measure.

How complex a dynamical network can be?

Positive Lyapunov exponents measure the asymptotic exponential divergence of nearby trajectories of a dynamical system. Not only they quantify how chaotic a dynamical system is, but since their sum is an upper bound for the rate of information production, they also provide a convenient way to quantify the complexity of a dynamical network. We conjecture based on numerical evidences that for a large class of dynamical networks composed by equal nodes, the sum of the positive Lyapunov exponents is bounded by the sum of all the positive Lyapunov exponents of both the synchronization manifold and its transversal directions, the last quantity being in principle easier to compute than the latter. As applications of our conjecture we: (i) show that a dynamical network composed of equal nodes and whose nodes are fully linearly connected produces more information than similar networks but whose nodes are connected with any other possible connecting topology; (ii) show how one can calculate upper bounds for the information production of realistic networks whose nodes have parameter mismatches, randomly chosen: (iii) discuss how to predict the behavior of a large dynamical network by knowing the information provided by a system composed of only two coupled nodes. (C) 2011 Elsevier B.V. All rights reserved.

Minimum cycle cover and Chinese postman problems on mixed graphs with bounded tree-width

Let M = (V, E, A) be a mixed graph with vertex set V, edge set E and arc set A. A cycle cover of M is a family C = {C(1), ... , C(k)} of cycles of M such that each edge/arc of M belongs to at least one cycle in C. The weight of C is Sigma(k)(i=1) vertical bar C(i)vertical bar. The minimum cycle cover problem is the following: given a strongly connected mixed graph M without bridges, find a cycle cover of M with weight as small as possible. The Chinese postman problem is: given a strongly connected mixed graph M, find a minimum length closed walk using all edges and arcs of M. These problems are NP-hard. We show that they can be solved in polynomial time if M has bounded tree-width. (C) 2008 Elsevier B.V. All rights reserved.

Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation

We investigate several two-dimensional guillotine cutting stock problems and their variants in which orthogonal rotations are allowed. We first present two dynamic programming based algorithms for the Rectangular Knapsack (RK) problem and its variants in which the patterns must be staged. The first algorithm solves the recurrence formula proposed by Beasley; the second algorithm - for staged patterns - also uses a recurrence formula. We show that if the items are not so small compared to the dimensions of the bin, then these algorithms require polynomial time. Using these algorithms we solved all instances of the RK problem found at the OR-LIBRARY, including one for which no optimal solution was known. We also consider the Two-dimensional Cutting Stock problem. We present a column generation based algorithm for this problem that uses the first algorithm above mentioned to generate the columns. We propose two strategies to tackle the residual instances. We also investigate a variant of this problem where the bins have different sizes. At last, we study the Two-dimensional Strip Packing problem. We also present a column generation based algorithm for this problem that uses the second algorithm above mentioned where staged patterns are imposed. In this case we solve instances for two-, three- and four-staged patterns. We report on some computational experiments with the various algorithms we propose in this paper. The results indicate that these algorithms seem to be suitable for solving real-world instances. We give a detailed description (a pseudo-code) of all the algorithms presented here, so that the reader may easily implement these algorithms. (c) 2007 Elsevier B.V. All rights reserved.

Packing triangles in low degree graphs and indifference graphs

We consider the problems of finding the maximum number of vertex-disjoint triangles (VTP) and edge-disjoint triangles (ETP) in a simple graph. Both problems are NP-hard. The algorithm with the best approximation ratio known so far for these problems has ratio 3/2 + epsilon, a result that follows from a more general algorithm for set packing obtained by Hurkens and Schrijver [On the size of systems of sets every t of which have an SDR, with an application to the worst-case ratio of heuristics for packing problems, SIAM J. Discrete Math. 2(1) (1989) 68-72]. We present improvements on the approximation ratio for restricted cases of VTP and ETP that are known to be APX-hard: we give an approximation algorithm for VTP on graphs with maximum degree 4 with ratio slightly less than 1.2, and for ETP on graphs with maximum degree 5 with ratio 4/3. We also present an exact linear-time algorithm for VTP on the class of indifference graphs. (C) 2007 Elsevier B.V. All rights reserved.

Symmetry breaking in the genetic code: Finite groups

We investigate the possibility of interpreting the degeneracy of the genetic code, i.e., the feature that different codons (base triplets) of DNA are transcribed into the same amino acid, as the result of a symmetry breaking process, in the context of finite groups. In the first part of this paper, we give the complete list of all codon representations (64-dimensional irreducible representations) of simple finite groups and their satellites (central extensions and extensions by outer automorphisms). In the second part, we analyze the branching rules for the codon representations found in the first part by computational methods, using a software package for computational group theory. The final result is a complete classification of the possible schemes, based on finite simple groups, that reproduce the multiplet structure of the genetic code. (C) 2010 Elsevier Ltd. All rights reserved.

Examples of Self-Iterating Lie Algebras, 2

We study properties of self-iterating Lie algebras in positive characteristic. Let R = K[t(i)vertical bar i is an element of N]/(t(i)(p)vertical bar i is an element of N) be the truncated polynomial ring. Let partial derivative(i) = partial derivative/partial derivative t(i), i is an element of N, denote the respective derivations. Consider the operators v(1) = partial derivative(1) + t(0)(partial derivative(2) + t(1)(partial derivative(3) + t(2)(partial derivative(4) + t(3)(partial derivative(5) + t(4)(partial derivative(6) + ...))))); v(2) = partial derivative(2) + t(1)(partial derivative(3) + t(2)(partial derivative(4) + t(3)(partial derivative(5) + t(4)(partial derivative(6) + ...)))). Let L = Lie(p)(v(1), v(2)) subset of Der R be the restricted Lie algebra generated by these derivations. We establish the following properties of this algebra in case p = 2, 3. a) L has a polynomial growth with Gelfand-Kirillov dimension lnp/ln((1+root 5)/2). b) the associative envelope A = Alg(v(1), v(2)) of L has Gelfand-Kirillov dimension 2 lnp/ln((1+root 5)/2). c) L has a nil-p-mapping. d) L, A and the augmentation ideal of the restricted enveloping algebra u = u(0)(L) are direct sums of two locally nilpotent subalgebras. The question whether u is a nil-algebra remains open. e) the restricted enveloping algebra u(L) is of intermediate growth. These properties resemble those of Grigorchuk and Gupta-Sidki groups.

TWISTED CONJUGACY CLASSES IN R. THOMPSON`S GROUP F

In this article, we prove that any automorphism of R. Thompson`s group F has infinitely many twisted conjugacy classes. The result follows from the work of Brin, together with standard facts about R. Thompson`s group F, and elementary properties of the Reidemeister numbers.

Lie properties of crossed products

Let F-sigma(lambda)vertical bar G vertical bar be a crossed product of a group G and the field F. We study the Lie properties of F-sigma(lambda)vertical bar G vertical bar in order to obtain a characterization of those crossed products which are upper (lower) Lie nilpotent and Lie (n, m)-Engel. (C) 2008 Elsevier Inc. All rights reserved.

Crossed products by twisted partial actions and graded algebras

For a twisted partial action e of a group G on an (associative non-necessarily unital) algebra A over a commutative unital ring k, the crossed product A x(Theta) G is proved to be associative. Given a G-graded k-algebra B = circle plus(g is an element of G) B-g with the mild restriction of homogeneous non-degeneracy, a criteria is established for B to be isomorphic to the crossed product B-1 x(Theta) G for some twisted partial action of G on B-1. The equality BgBg-1 B-g = B-g (for all g is an element of G) is one of the ingredients of the criteria, and if it holds and, moreover, B has enough local units, then it is shown that B is stably isomorphic to a crossed product by a twisted partial action of G. (c) 2008 Elsevier Inc. All rights reserved.

Extensions of homogeneous polynomials ON c(0)(l(2)(i))

We show that a 2-homogeneous polynomial on the complex Banach space c(0)(l(2)(i)) is norm attaining if and only if it is finite (i.e, depends only on finite coordinates). As the consequence, we show that there exists a unique norm-preserving extension for norm-attaining 2-homogeneous polynomials on c(0)(l(2)(i)).

Nuclear elements of degree 6 in the free alternative algebra

We construct five new elements of degree 6 in the nucleus of the free alternative algebra. We use the representation theory of the symmetric group to locate the elements. We use the computer algebra system ALBERT and an extension of ALBERT to express the elements in compact form and to show that these new elements are not a consequence of the known clegree-5 elements in the nucleus. We prove that these five new elements and four known elements form a basis for the subspace of nuclear elements of degree 6. Our calculations are done using modular arithmetic to save memory and time. The calculations can be done in characteristic zero or any prime greater than 6, and similar results are expected. We generated the nuclear elements using prime 103. We check our answer using five other primes.

Finite-dimensional non-associative algebras and codimension growth

Let A be a (non-necessarily associative) finite-dimensional algebra over a field of characteristic zero. A quantitative estimate of the polynomial identities satisfied by A is achieved through the study of the asymptotics of the sequence of codimensions of A. It is well known that for such an algebra this sequence is exponentially bounded. Here we capture the exponential rate of growth of the sequence of codimensions for several classes of algebras including simple algebras with a special non-degenerate form, finite-dimensional Jordan or alternative algebras and many more. In all cases such rate of growth is integer and is explicitly related to the dimension of a subalgebra of A. One of the main tools of independent interest is the construction in the free non-associative algebra of multialternating polynomials satisfying special properties. (C) 2010 Elsevier Inc. All rights reserved.

REIDEMEISTER SPECTRUM FOR METABELIAN GROUPS OF THE FORM Q(n) x Z AND Z[1/p](n) x Z, p PRIME

In this paper, we study the Reidemeister spectrum for metabelian groups of the form Q(n) x Z and Z[1/p](n) x Z. Particular attention is given to the R(infinity)-property of a subfamily of these groups.