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.

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.

Skew-symmetric identities of octonions

Quadratic alternative superalgebras are introduced and their super-identities and central functions on one odd generator are described. As a corollary, all multilinear skew-symmetric identities and central polynomials of octonions are classified. (C) 2008 Elsevier B.V. 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.

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.

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.

Nil graded self-similar algebras

In [19], [24] we introduced a family of self-similar nil Lie algebras L over fields of prime characteristic p > 0 whose properties resemble those of Grigorchuk and Gupta-Sidki groups. The Lie algebra L is generated by two derivations v(1) = partial derivative(1) + t(0)(p-1) (partial derivative(2) + t(1)(p-1) (partial derivative(3) + t(2)(p-1) (partial derivative(4) + t(3)(p-1) (partial derivative(5) + t(4)(p-1) (partial derivative(6) + ...))))), v(2) = partial derivative(2) + t(1)(p-1) (partial derivative(3) + t(2)(p-1) (partial derivative(4) + t(3)(p-1) (partial derivative(5) + t(4)(p-1) (partial derivative(6) + ...)))) of the truncated polynomial ring K[t(i), i is an element of N vertical bar t(j)(p) =0, i is an element of N] in countably many variables. The associative algebra A generated by v(1), v(2) is equipped with a natural Z circle plus Z-gradation. In this paper we show that for p, which is not representable as p = m(2) + m + 1, m is an element of Z, the algebra A is graded nil and can be represented as a sum of two locally nilpotent subalgebras. L. Bartholdi [3] andYa. S. Krylyuk [15] proved that for p = m(2) + m + 1 the algebra A is not graded nil. However, we show that the second family of self-similar Lie algebras introduced in [24] and their associative hulls are always Z(p)-graded, graded nil, and are sums of two locally nilpotent subalgebras.

An algebraic theory for generalized Jordan chains and partial signatures in the Lagrangian Grassmannian

We discuss an algebraic theory for generalized Jordan chains and partial signatures, that are invariants associated to sequences of symmetric bilinear forms on a vector space. We introduce an intrinsic notion of partial signatures in the Lagrangian Grassmannian of a symplectic space that does not use local coordinates, and we give a formula for the Maslov index of arbitrary real analytic paths in terms of partial signatures.

Nonhomogeneous subalgebras of Lie and special Jordan superalgebras

We consider polynomial identities satisfied by nonhomogeneous subalgebras of Lie and special Jordan superalgebras: we ignore the grading and regard the superalgebra as an ordinary algebra. The Lie case has been studied by Volichenko and Baranov: they found identities in degrees 3, 4 and 5 which imply all the identities in degrees <= 6. We simplify their identities in degree 5, and show that there are no new identities in degree 7. The Jordan case has not previously been studied: we find identities in degrees 3, 4, 5 and 6 which imply all the identities in degrees <= 6, and demonstrate the existence of further new identities in degree 7. our proofs depend on computer algebra: we use the representation theory of the symmetric group, the Hermite normal form of an integer matrix, the LLL algorithm for lattice basis reduction, and the Chinese remainder theorem. (C) 2009 Elsevier Inc. All rights reserved.

A Character Formula for the Category (O)over-tilde of Modules for Affine sl(2)

One may construct, for any function on the integers, an irreducible module of level zero for affine sl(2) using the values of the function as structure constants. The modules constructed using exponential-polynomial functions realize the irreducible modules with finite-dimensional weight spaces in the category (O) over tilde of Chari. In this work, an expression for the formal character of such a module is derived using the highest weight theory of truncations of the loop algebra.