On good morphisms of exact triangles

In a triangulated category, cofibre fill-ins always exist. Neeman showed that there is always at least one “good” fill-in, i.e., one whose mapping cone is exact. Verdier constructed a fill-in of a particular form in his proof of the $4\times 4$ lemma, which we call “Verdier good”. We show that for several classes of morphisms of exact triangles, the notions of good and Verdier good agree. We prove a lifting criterion for commutative squares in terms of (Verdier) good fill-ins. Using our results on good fill-ins, we also prove a pasting lemma for homotopy cartesian squares.     

An improved simulated annealing algorithm for bandwidth minimization

In this paper, a simulated annealing algorithm is presented for the bandwidth minimization problem for graphs. This algorithm is based on three distinguished features including an original internal representation of solutions, a highly discriminating evaluation function and an effective neighborhood. The algorithm is evaluated on a set of 113 well-known benchmark instances of the literature and compared with several state-of-the-art algorithms, showing improvements of some previous best results.     

On deformations of triangulated models

This paper is the first part of a project aimed at understanding deformations of triangulated categories, and more precisely their dg and _A∞$A_{\infty }$ models, and applying the resulting theory to the models occurring in the Homological Mirror Symmetry setup. In this first paper, we focus on models of derived and related categories, based upon the classical construction of twisted objects over a dg or _A∞$A_{\infty }$-algebra. For a Hochschild 2 cocycle on such a model, we describe a corresponding “curvature compensating” deformation which can be entirely understood within the framework of twisted objects. We unravel the construction in the specific cases of derived _A∞$A_{\infty }$ and abelian categories, homotopy categories, and categories of graded free qdg-modules. We identify a purity condition on our models which ensures that the structure of the model is preserved under deformation. This condition is typically fulfilled for homotopy categories, but not for unbounded derived categories.     

Cohomology theories in triangulated categories

Let C be a triangulated category with a proper class E of triangles.We prove that there exists an Avramov–Martsinkovsky type exact sequence in C,which connects E-cohomology,E-Tate cohomology and E-Gorenstein cohomology.     

Formal completions and idempotent completions of triangulated categories of singularities

The main goal of this paper is to prove that the idempotent completions of triangulated categories of singularities of two schemes are equivalent if the formal completions of these schemes along singularities are isomorphic. We also discuss Thomason's theorem on dense subcategories and a relation to the negative K-theory.     

Computing generalized higher-order Voronoi diagrams on triangulated surfaces

We present an algorithm for computing exact shortest paths, and consequently distance functions, from a generalized source (point, segment, polygonal chain or polygonal region) on a possibly non-convex triangulated polyhedral surface. The algorithm is generalized to the case when a set of generalized sites is considered, providing their distance field that implicitly represents the Voronoi diagram of the sites. Next, we present an algorithm to compute a discrete representation of the distance function and the distance field. Then, by using the discrete distance field, we obtain the Voronoi diagram of a set of generalized sites (points, segments, polygonal chains or polygons) and visualize it on the triangulated surface. We also provide algorithms that, by using the discrete distance functions, provide the closest, furthest and k-order Voronoi diagrams and an approximate 1-Center and 1-Median.     

n-tribonacci triangles and applications

In this note we introduce n-tribonacci triangle, which is similar to Pascal's triangle, to derive an explicit formula for the tribonacci numbers by using some properties of our triangle.     

Packing similar triangles into a triangle

There exists a triangle T and a number \frac{1}{2}$$ " align="middle" border="0"> such that any sequence of triangles similar to T with total area not greater than times the area of T can be packed into T.     

Locally finite triangulated categories

A k-linear triangulated category is called locally finite provided for any indecomposable object Y in . It has Auslander–Reiten triangles. In this paper, we show that if a (connected) triangulated category has Auslander–Reiten triangles and contains loops, then its Auslander–Reiten quiver is of the form :

Full-size image (<1K)

By using this, we prove that the Auslander–Reiten quiver of any locally finite triangulated category is of the form , where Δ is a Dynkin diagram and G is an automorphism group of . For most automorphism groups G, the triangulated categories with as their Auslander–Reiten quivers are constructed. In particular, a triangulated category with as its Auslander–Reiten quiver is constructed.     

Non-hamiltonian triangulations with distant separating triangles

In 1996 Böhme, Harant, and Tká? asked whether there exists a non-hamiltonian triangulation with the property that any two of its separating triangles lie at distance at least 1. Two years later, Böhme and Harant answered this in the affirmative, showing that for any non-negative integer $d$ there exists a non-hamiltonian triangulation with seven separating triangles every two of which lie at distance at least $d$. In this note we prove that the result holds if we replace seven with six, remarking that no non-hamiltonian triangulation with fewer than six separating triangles is known.     

The vertex-adjacency dual of a triangulated irregular network has a Hamiltonian cycle

Triangulated irregular networks (TINs) are common representations of surfaces in computational graphics. We define the dual of a TIN in a special way, based on vertex-adjacency, and show that its Hamiltonian cycle always exists and can be found efficiently. This result has applications in transmission of large graphics datasets.     

On the approximation of a smooth surface with a triangulated mesh

We approximate the normals and the area of a smooth surface with the normals and the area of a triangulated mesh whose vertices belong to the smooth surface. Both approximations only depend on the triangulated mesh (which is supposed to be known), on an upper bound on the smooth surface's curvature, on an upper bound on its reach (which is linked to the local feature size) and on an upper bound on the Hausdorff distance between both surfaces.

We show in particular that the upper bound on the error of the normals is better when triangles are right-angled (even if there are small angles). We do not need every angle to be quite large. We just need each triangle of the triangulated mesh to contain at least one angle whose sinus is large enough.     

On smallest triangles

Pick n points independently at random in ?², according to a prescribed probability measure μ, and let Δ ≤ Δ ≤ … be the areas of the () triangles thus formed, in nondecreasing order. If μ is absolutely continuous with respect to Lebesgue measure, then, under weak conditions, the set {n³Δ : i ≥ 1} converges as n → ∞ to a Poisson process with a constant intensity κ(μ). This result, and related conclusions, are proved using standard arguments of Poisson approximation, and may be extended to functionals more general than the area of a triangle. It is proved in addition that if μ is the uniform probability measure on the region S, then κ(μ) ≤ 2/|S|, where |S| denotes the area of S. Equality holds in that κ(μ) = 2/|S| if S is convex, and essentially only then. This work generalizes and extends considerably the conclusions of a recent paper of Jiang, Li, and Vitányi. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 23: 206–223, 2003     

Supermemory descent methods for unconstrained minimization

The supermemory gradient method of Cragg and Levy (Ref. 1) and the quasi-Newton methods with memory considered by Wolfe (Ref. 4) are shown to be special cases of a more general class of methods for unconstrained minimization which will be called supermemory descent methods. A subclass of the supermemory descent methods is the class of supermemory quasi-Newton methods. To illustrate the numerical effectiveness of supermemory quasi-Newton methods, some numerical experience with one such method is reported.The authors are indebted to Dr. H. Y. Huang for his helpful criticism of this paper.     

Directed triangles in directed graphs

We show that each directed graph (with no parallel arcs) on n vertices, each with indegree and outdegree at least n/twhere t=2.888997… contains a directed circuit of length at most 3.     

Empirical minimization

We investigate the behavior of the empirical minimization algorithm using various methods. We first analyze it by comparing the empirical, random, structure and the original one on the class, either in an additive sense, via the uniform law of large numbers, or in a multiplicative sense, using isomorphic coordinate projections. We then show that a direct analysis of the empirical minimization algorithm yields a significantly better bound, and that the estimates we obtain are essentially sharp. The method of proof we use is based on Talagrand's concentration inequality for empirical processes. Research partially supported by NSF under award DMS-0434393. Research partially supported by the Australian Research Council Discovery Porject DP0343616.     

Grouped coordinate minimization using Newton's method for inexact minimization in one vector coordinate

Letf(x,y) be a function of the vector variablesx R ⁿ andy R ^m. The grouped (variable) coordinate minimization (GCM) method for minimizingf consists of alternating exact minimizations in either of the two vector variables, while holding the other fixed at the most recent value. This scheme is known to be locally,q-linearly convergent, and is most useful in certain types of statistical and pattern recognition problems where the necessary coordinate minimizers are available explicitly. In some important cases, the exact minimizer in one of the vector variables is not explicitly available, so that an iterative technique such as Newton's method must be employed. The main result proved here shows that a single iteration of Newton's method solves the coordinate minimization problem sufficiently well to preserve the overall rate of convergence of the GCM sequence.The authors are indebted to Professor R. A. Tapia for his help in improving this paper.