Some 2-isohedral tilings of the plane

In this paper we describe and classify, using adjacency symbols, the 2-isohedral tilings of the plane such that all tiles have four edges and four tiles meet at each vertex. There are 69 such tilings. Since many of these can be constructed by dissecting isohedral tilings appropriately, we show which isohedral tilings are related in this way to these 2-isohedral tilings.     

The classification of 2-isohedral tilings of the plane

Two different methods for enumerating k-isohedral tilings are discussed. One is geometric: by splitting and gluing tiles. The other is combinatorial: by enumerating the appropriate Delaney—Dress symbols. Both methods yield 1270 types of proper 2-isohedral tilings of the plane.     

Vertex-transitive triangulations of compact orientable 2-manifolds

In this note we construct two infinite families of vertex-transitive triangulations of compact orientable 2-manifolds. Included in these families are two of the best known “classical” examples, viz., the triangulation of the genus 3 surface admitting the group PSL(2, 7) and the triangulation of the genus 7 surface admitting SL(2, 8).     

Piecewise linear prewavelets over type-2 triangulations

In this article, we study the construction of piecewise linear prewavelets over type-2 triangulations. Different from a so-called semi-prewavelet approach, we investigate the orthogonal conditions directly and obtain parameterized prewavelets with a smaller support. The conditions for parameterized prewavelet basis on the parameters are also given.     

Clean triangulations

A polyhedron on a surface is called a clean triangulation if each face is a triangle and each triangle is a face. LetS _p (resp.N _p ) be the closed orientable (resp. nonorlentable) surface of genusp. If (S) is the smallest possible number of triangles in a clean triangulation ofS, the results are: (N ₁)=20, (S ₁)=24, lim(S _p )p ^–1=4, lim(N _p )p ^–1=2 forp.     

All orientable 2-manifolds have finitely many minimal triangulations

We show that for every orientable 2-manifold there is a finite set of triangulations from which all other triangulations can be generated by sequences of vertex splittings.     

Variable resolution triangulations

A comprehensive study of multiresolution decompositions of planar domains into triangles is given. A general model is introduced, called a Multi-Triangulation (MT), which is based on a collection of fragments of triangulations arranged into a directed acyclic graph. Different decompositions of a domain can be obtained by combining different fragments of the model. Theoretical results on the expressive power of the MT are given. An efficient algorithm is proposed that can extract a triangulation from the MT, whose level of detail is variable over the domain according to a given threshold function. The algorithm works in linear time, and the extracted representation has minimum size among all possible triangulations that can be built from triangles in the MT, and that satisfy the given level of detail. Major applications of these results are in real-time rendering of complex surfaces, such as topographic surfaces in flight simulation.     

Essential coverings and triangulations

Sunto In questo lavoro si danno condizioni sufficienti per un ricoprimento di una varietà differenziabile V affinchè il suo nerbo abbia lo stesso tipo P.L. di V e si prova l'esistenza di una larga classe di siffatti ricoprimenti.

---

---

The author is member of G.N.S.A.G.A. of the C.N.R. and partially supported by a N.A.T.O.-C.N.R. fellowship.     

Spanning triangulations in graphs

We prove that every graph of sufficiently large order n and minimum degree at least 2n/3 contains a triangulation as a spanning subgraph. This is best possible: for all integers n, there are graphs of order n and minimum degree ?2n/3? ? 1 without a spanning triangulation. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Geometric triangulations and flips

We prove that for a given flat surface with conical singularities, any pair of geometric triangulations can be connected by a chain of flips.     

Products of foldable triangulations

Regular triangulations of products of lattice polytopes are constructed with the additional property that the dual graphs of the triangulations are bipartite. The (weighted) size difference of this bipartition is a lower bound for the number of real roots of certain sparse polynomial systems by recent results of Soprunova and Sottile [E. Soprunova, F. Sottile, Lower bounds for real solutions to sparse polynomial systems, Adv. Math. 204 (1) (2006) 116–151]. Special attention is paid to the cube case.     

Acute triangulations of trapezoids

In this paper we discuss acute triangulations of trapezoids. It is known that every rectangle can be triangulated into eight acute triangles, and that this is best possible. In this paper we prove that all other trapezoids can be triangulated into at most seven acute triangles.     

Hamiltonian embeddings from triangulations

A Hamiltonian embedding of K_n is an embedding of K_n in a surface,which may be orientable or non-orientable, in such a way thatthe boundary of each face is a Hamiltonian cycle. Ellinghamand Stephens recently established the existence of such embeddingsin non-orientable surfaces for n = 4 and n 6. Here we presentan entirely new construction which produces Hamiltonian embeddingsof K_n from triangulations of K_n when n 0 or 1 (mod 3). We thenuse this construction to obtain exponential lower bounds forthe numbers of nonisomorphic Hamiltonian embeddings of K_n.     

Toughness and Delaunay triangulations

We show that nondegenerate Delaunay triangulations satisfy a combinatorial property called 1-toughness. A graphG is1-tough if for any setP of vertices,c(G–P)|G|, wherec(G–P) is the number of components of the graph obtained by removingP and all attached edges fromG, and |G| is the number of vertices inG. This property arises in the study of Hamiltonian graphs: all Hamiltonian graphs are 1-tough, but not conversely. We also show that all Delaunay triangulationsT satisfy the following closely related property: for any setP of vertices the number of interior components ofT–P is at most |P|–2, where an interior component ofT–P is a component that contains no boundary vertex ofT. These appear to be the first nontrivial properties of a purely combinatorial nature to be established for Delaunay triangulations. We give examples to show that these bounds are best possible and are independent of one another. We also characterize the conditions under which a degenerate Delaunay triangulation can fail to be 1-tough. This characterization leads to a proof that all graphs that can be realized as polytopes inscribed in a sphere are 1-tough. One consequence of the toughness results is that all Delaunay triangulations and all inscribable graphs have perfect matchings.This research was sponsored in part by the National Science Foundation under Grant IRI-88-02457.     

Generating spherical Eulerian triangulations

We show that all spherical Eulerian triangulations can be inductively generated from the set of all even double wheels using just one of the two local transformations used in the algorithm by Brinkmann and McKay and originally proposed by Batagelj.     

Three-pencil lattices on triangulations

In this paper, three-pencil lattices on triangulations are studied. The explicit representation of a lattice, based upon barycentric coordinates, enables us to construct lattice points in a simple and numerically stable way. Further, this representation carries over to triangulations in a natural way. The construction is based upon group action of S ₃ on triangle vertices, and it is shown that the number of degrees of freedom is equal to the number of vertices of the triangulation.