An improvement of fixed point algorithms by using a good triangulation

We consider measures for triangulations ofR ⁿ. A new measure is introduced based on the ratio of the length of the sides and the content of the subsimplices of the triangulation. In a subclass of triangulations, which is appropriate for computing fixed points using simplicial subdivisions, the optimal one according to this measure is calculated and some of its properties are given. It is proved that for the average directional density this triangulation is optimal (within the subclass) asn goes to infinity. Furthermore, we compare the measures of the optimal triangulation with those of other triangulations. We also propose a new triangulation of the affine hull of the unit simplex. Finally, we report some computational experience that confirms the theoretical results.     

Simplices and Spectra of Graphs

In this note we show that the (n−2)-dimensional volumes of codimension 2 faces of an n-dimensional simplex are algebraically independent quantities of the volumes of its edge-lengths. The proof involves computation of the eigenvalues of Kneser graphs. We also show examples of families of simplices (of dimension 4 or greater) which show that the set of (n−2)-dimensional volumes of (n−2)-dimensional faces of a simplex do not determine its volume.     

Retract-collapsible graphs and invariant subgraph properties

A (finite or infinite) graph G is retract-collapsible if it can be dismantled by deleting systematically at each step every vertex that is strictly dominated, in such a way that the remaining subgraph is a retract of G, and so as to get a simplex at the end. A graph is subretract-collapsible if some graph obtained by planting some rayless tree at each of its vertices is retract-collapsible. It is shown that the subretract-colapsible graphs are cop-win; and that a ball-Helly graph is subretract-collapsible if and only if it has no isometric infinite paths (thus in particular if it has no infinite paths, or if it is bounded). Several fixed subgraph properties are proved. In particular, if G is a subretract-collapsible graph, and f a contraction from G into G, then (i) if G has no infinite simplices, then f(S) = S for some simplex S of G; and (ii) if the dismantling of G can be achieved in a finite number of steps and if some family of simplices of G has a compacity property, then there is a simplex S of G such that f(S) ? S. This last result generalizes a property of bounded ball-Helly graphs. © 1995 John Wiley & Sons, Inc.     

The complex of maximal lattice free simplices

The simplicial complexK(A) is defined to be the collection of simplices, and their proper subsimplices, representing maximal lattice free bodies of the form (x: Axb), withA a fixed generic (n + 1) ×n matrix. The topological space associated withK(A) is shown to be homeomorphic to ⁿ , and the space obtained by identifying lattice translates of these simplices is homeorphic to then-torus.Corresponding author.The first author was partially supported by Hungarian NSF grants 1907 and 1909, and also by U.S. NSF grant CCR-9111491. The research of the second author was supported by DMS9103608 and the third author by NSF grant SES9121936.     

Delaunay configurations and multivariate splines: A generalization of a result of B. N. Delaunay

In the 1920s, B. N. Delaunay proved that the dual graph of the Voronoi diagram of a discrete set of points in a Euclidean space gives rise to a collection of simplices, whose circumspheres contain no points from this set in their interior. Such Delaunay simplices tessellate the convex hull of these points. An equivalent formulation of this property is that the characteristic functions of the Delaunay simplices form a partition of unity. In the paper this result is generalized to the so-called Delaunay configurations. These are defined by considering all simplices for which the interiors of their circumspheres contain a fixed number of points from the given set, in contrast to the Delaunay simplices, whose circumspheres are empty. It is proved that every family of Delaunay configurations generates a partition of unity, formed by the so-called simplex splines. These are compactly supported piecewise polynomial functions which are multivariate analogs of the well-known univariate B-splines. It is also shown that the linear span of the simplex splines contains all algebraic polynomials of degree not exceeding the degree of the splines.

     

Large Cells in Poisson–Delaunay Tessellations

It is proved that the shape of the typical cell of a Delaunay tessellation, derived from a stationary Poisson point process in d-dimensional Euclidean space, tends to the shape of a regular simplex, given that the volume of the typical cell tends to infinity. This follows from an estimate for the probability that the typical cell deviates by a given amount from regularity, given that its volume is large. As a tool for the proof, a stability result for simplices is established.     

Weighted projective spaces and reflexive simplices

 We derive a classification algorithm for reflexive simplices in arbitrary fixed dimension. It is based on the assignment of a weight Q ? ℕ ⁿ⁺¹ to an integral n-simplex, the construction, up to an isomorphism, of all simplices with given weight Q, and the characterization in terms of the weight as to when a simplex with reduced weight is reflexive. This also yields a convex-geometric reproof of the characterization in terms of weights for weighted projective spaces to have at most Gorenstein singularities. Received: 30 March 1999 / Revised version: 18 October 2001     

Orthocentric simplices and their centers

A simplex is said to be orthocentric if its altitudes intersect in a common point, called its orthocenter. In this paper it is proved that if any two of the traditional centers of an orthocentric simplex (in any dimension) coincide, then the simplex is regular. Along the way orthocentric simplices in which all facets have the same circumradius are characterized, and the possible barycentric coordinates of the orthocenter are described precisely. In particular these barycentric coordinates are used to parametrize the shapes of orthocentric simplices. The substantial, but widespread, literature on orthocentric simplices is briefly surveyed in order to place the new results in their proper context, and some of the previously known results are given with new proofs from the present perspective.     

Simplicial grid refinement: on Freudenthal's algorithm and the optimal number of congruence classes

Summary. In the present paper we investigate Freudenthal's simplex refinement algorithm which can be considered to be the canonical generalization of Bank's well known red refinement strategy for triangles. Freudenthal's algorithm subdivides any given (n)-simplex into subsimplices, in such a way that recursive application results in a stable hierarchy of consistent triangulations. Our investigations concentrate in particular on the number of congruence classes generated by recursive refinements. After presentation of the method and the basic ideas behind it, we will show that Freudenthal's algorithm produces at most n!/2 congruence classes for any initial (n)-simplex, no matter how many subsequent refinements are performed. Moreover, we will show that this number is optimal in the sense that recursive application of any affine invariant refinement strategy with sons per element results in at least n!/2 congruence classes for almost all (n)-simplices. Received February 23, 1998/ Revised version received December 9, 1998 / Published online January 27, 2000     

Simplices of Maximal Volume or Minimal Total Edge Length in Hyperbolic Space

In this paper, we are mainly concerned with n-dimensional simplicesin hyperbolic space Hⁿ. We will also consider simplices withideal vertices, and we suggest that the reader keeps the Poincaréunit ball model of hyperbolic space in mind, in which the sphereat infinity Hⁿ() corresponds to the bounding sphere of radius1. It is known that all hyperbolic simplices (even the idealones) have finite volume. However, explicit calculation of theirvolume is generally a very difficult problem (see, for example,[1] or [16]). Our first theorem states that, amongst all simplicesin a closed geodesic ball, the simplex of maximal volume isregular. We call a simplex regular if every permutation of itsvertices can be realized by an isometry of Hⁿ. A correspondingresult for simplices in the sphere has been proved by Böröczky[4].     

The analysis of a nested dissection algorithm

Summary Nested dissection is an algorithm invented by Alan George for preserving sparsity in Gaussian elimination on symmetric positive definite matrices. Nested dissection can be viewed as a recursive divide-and-conquer algorithm on an undirected graph; it usesseparators in the graph, which are small sets of vertices whose removal divides the graph approximately in half. George and Liu gave an implementation of nested dissection that used a heuristic to find separators. Lipton and Tarjan gave an algorithm to findn ^1/2-separators in planar graphs and two-dimensional finite element graphs, and Lipton, Rose, and Tarjan used these separators in a modified version of nested dissection, guaranteeing bounds ofO (n logn) on fill andO(n ^3/2) on operation count. We analyze the combination of the original George-Liu nested dissection algorithm and the Lipton-Tarjan planar separator algorithm. This combination is interesting because it is easier to implement than the Lipton-Rose-Tarjan version, especially in the framework of existïng sparse matrix software. Using some topological graph theory, we proveO(n logn) fill andO(n ^3/2) operation count bounds for planar graphs, twodimensional finite element graphs, graphs of bounded genus, and graphs of bounded degree withn ^1/2-separators. For planar and finite element graphs, the leading constant factor is smaller than that in the Lipton-Rose-Tarjan analysis. We also construct a class of graphs withn ^1/2-separators for which our algorithm does not achieve anO(n logn) bound on fill.The work of this author was supported in part by the Hertz Foundation under a graduate fellowship and by the National Science Foundation under Grant MCS 82-02948The work of this author was supported in part by the National Science Foundation under Grant MCS 78-26858 and by the Office of Naval Research under Contract N00014-76-C-0688     

An Arbitrary Starting Variable Dimension Algorithm for Computing an Integer Point of a Simplex

An arbitrary starting variable dimension algorithm is proposed to compute an integer point of an n-dimensional simplex. It is based on an integer labeling rule and a triangulation of Rⁿ. The algorithm consists of two interchanging phases. The first phase of the algorithm is a variable dimension algorithm, which generates simplices of varying dimensions,and the second phase of the algorithm forms a full-dimensional pivoting procedure, which generates n-dimensional simplices. The algorithm varies from one phase to the other. When the matrix defining the simplex is in the so-called canonical form, starting at an arbitrary integer point, the algorithm within a finite number of iterations either yields an integer point of the simplex or proves that no such point exists.     

Bisecton by Global Optimization Revisited

In partitioning methods such as branch and bound for solving global optimization problems, the so-called bisection of simplices and hyperrectangles is used since almost 40 years. Bisections are also of interest in finite-element methods. However, as far as we know, no proof has been given of the optimality of bisections with respect to other partitioning strategies. In this paper, after generalizing the current definition of partition slightly, we show that bisection is not optimal. Hybrid approaches combining different subdivision strategies with inner and outer approximation techniques can be more efficient. Even partitioning a polytope into simplices has important applications, for example in computational convexity, when one wants to find the inequality representation of a polytope with known vertices. Furthermore, a natural approach to the computation of the volume of a polytope P is to generate a simplex partition of P, since the volume of a simplex is given by a simple formula. We propose several variants of the partitioning rules and present complexity considerations. Finally, we discuss an approach for the volume computation of so-called H-polytopes, i.e., polytopes given by a system of affine inequalities. Upper bounds for the number of iterations are presented and advantages as well as drawbacks are discussed.     

Simplices with congruent k-faces

Let S be a non-degenerate simplex in $\mathbb{R}^{2}$. We prove that S is regular if, for some k $\in$ {1,...,n-2}, all its k-dimensional faces are congruent. On the other hand, there are non-regular simplices with the property that all their (n1)-dimensional faces are congruent.     

A Partition Theory of Planar Animals

A dissection of an animal is a partition of its cells into blocks that are themselves animals. The n-rule allows only those dissections with the area of every block a multiple of n. If an animal with area divisible by n has no dissection allowed by the n-rule, then the animal is said to be an n-irreducible. The partition meet of all allowed dissections of a given animal is called the n-dissection residue of that animal. This paper considers only planar animals. All 2-irreducibles are found, and the problem of computing 2-dissection residues is solved. Two theorems on n-irreducibles are proved. One of them states that large n-irreducibles always arise by adding cells to smaller n-irreducibles.     

Graph isomorphism and equality of simplices

We show that the graph isomorphism problem is equivalent to the problem of recognizing equal simplices in ? ⁿ . This result can lead to new methods in the graph isomorphism problem based on geometrical properties of simplices. In particular, relations between several well-known classes of invariants of graphs and geometrical invariants of simplices are established.     

Quivers of semi-maximal rings

In this paper, the set of quivers of semi-maximal rings is investigated. It is proved that the elements of this set are formed by the elements of the set of quivers of tiled orders and that the set of quivers of tiled orders with n vertices is determined by the integer points of a convex polyhedral domain that lie in the nonnegative part of the space . It is also proved that the set of quivers of tiled orders with n vertices contains all simple, oriented, strongly connected graphs with n vertices and n loops, does not contain any graphs with n vertices and n − 1 loops, and contains only a part of the graphs with n vertices and m (m < n − 1) loops. __________ Translated from Fundamentalnaya i Prikladnaya Matematika, Vol. 11, No. 3, pp. 215–223, 2005.     

Hamilton cycle rich two‐factorizations of complete graphs

For all integers n ≥ 5, it is shown that the graph obtained from the n‐cycle by joining vertices at distance 2 has a 2‐factorization is which one 2‐factor is a Hamilton cycle, and the other is isomorphic to any given 2‐regular graph of order n. This result is used to prove several results on 2‐factorizations of the complete graph K_n of order n. For example, it is shown that for all odd n ≥ 11, K_n has a 2‐factorization in which three of the 2‐factors are isomorphic to any three given 2‐regular graphs of order n, and the remaining 2‐factors are Hamilton cycles. For any two given 2‐regular graphs of even order n, the corresponding result is proved for the graph K_n ‐ I obtained from the complete graph by removing the edges of a 1‐factor. © 2004 Wiley Periodicals, Inc.     

On the spectral characterization of some unicyclic graphs

Let H(n;q,n₁,n₂) be a graph with n vertices containing a cycle C_q and two hanging paths P_n1 and P_n2 attached at the same vertex of the cycle. In this paper, we prove that except for the A-cospectral graphs H(12;6,1,5) and H(12;8,2,2), no two non-isomorphic graphs of the form H(n;q,n₁,n₂) are A-cospectral. It is proved that all graphs H(n;q,n₁,n₂) are determined by their L-spectra. And all graphs H(n;q,n₁,n₂) are proved to be determined by their Q-spectra, except for graphs with a being a positive even number and with b≥4 being an even number. Moreover, the Q-cospectral graphs with these two exceptions are given.