From the Icosahedron to Natural Triangulations of CP(2) and S(2) x S(2)

We present two constructions in this paper: (a) a 10-vertex triangulation CP(10)(2) of the complex projective plane CP(2) as a subcomplex of the join of the standard sphere (S(4)(2)) and the standard real projective plane (RP(6)(2), the decahedron), its automorphism group is A(4); (b) a 12-vertex triangulation (S(2) x S(2))(12) of S(2) x S(2) with automorphism group 2S(5), the Schur double cover of the symmetric group S(5). It is obtained by generalized bistellar moves from a simplicial subdivision of the standard cell structure of S(2) x S(2). Both constructions have surprising and intimate relationships with the icosahedron. It is well known that CP(2) has S(2) x S(2) as a two-fold branched cover; we construct the triangulation CP(10)(2) of CP(2) by presenting a simplicial realization of this covering map S(2) x S(2) -> CP(2). The domain of this simplicial map is a simplicial subdivision of the standard cell structure of S(2) x S(2), different from the triangulation alluded to in (b). This gives a new proof that Kuhnel's CP(9)(2) triangulates CP(2). It is also shown that CP(10)(2) and (S(2) x S(2))(12) induce the standard piecewise linear structure on CP(2) and S(2) x S(2) respectively.

Minimal Triangulations of Manifolds

Finding vertex-minimal triangulations of closed manifolds is a very difficult problem. Except for spheres and two series of manifolds, vertex-minimal triangulations are known for only few manifolds of dimension more than 2 (see the table given at the end of Section 5). In this article, we present a brief survey on the works done in last 30 years on the following:(i) Finding the minimal number of vertices required to triangulate a given pl manifold. (ii) Given positive integers n and d, construction of n-vertex triangulations of different d-dimensional pl manifolds. (iii) Classifications of all the triangulations of a given pl manifold with same number of vertices.In Section 1, we have given all the definitions which are required for the remaining part of this article. A reader can start from Section 2 and come back to Section 1 as and when required. In Section 2, we have presented a very brief history of triangulations of manifolds. In Section 3,we have presented examples of several vertex-minimal triangulations. In Section 4, we have presented some interesting results on triangulations of manifolds. In particular, we have stated the Lower Bound Theorem and the Upper Bound Theorem. In Section 5, we have stated several results on minimal triangulations without proofs. Proofs are available in the references mentioned there. We have also presented some open problems/conjectures in Sections 3 and 5.

An infinite family of tight triangulations of manifolds

We give explicit construction of vertex-transitive tight triangulations of d-manifolds for d >= 2. More explicitly, for each d >= 2, we construct two (d(2) + 5d + 5)-vertex neighborly triangulated d-manifolds whose vertex-links are stacked spheres. The only other non-trivial series of such tight triangulated manifolds currently known is the series of non-simply connected triangulated d-manifolds with 2d + 3 vertices constructed by Kuhnel. The manifolds we construct are strongly minimal. For d >= 3, they are also tight neighborly as defined by Lutz, Sulanke and Swartz. Like Kuhnel complexes, our manifolds are orientable in even dimensions and non-orientable in odd dimensions. (c) 2013 Elsevier Inc. All rights reserved.

Equilibrium and equivariant triangulations of some small covers with minimum number of vertices

Small covers were introduced by Davis and Januszkiewicz in 1991. We introduce the notion of equilibrium triangulations for small covers. We study equilibrium and vertex minimal 4-equivariant triangulations of 2-dimensional small covers. We discuss vertex minimal equilibrium triangulations of RP3#RP3, S-1 x RP2 and a nontrivial S-1 bundle over RP2. We construct some nice equilibrium triangulations of the real projective space RPn with 2(n) + n 1 vertices. The main tool is the theory of small covers.

Strongly minimal triangulations of (S (3) x S (1))(#3) and (S (3) x S (1))(#3)

A triangulated d-manifold K, satisfies the inequality for da parts per thousand yen3. The triangulated d-manifolds that meet the bound with equality are called tight neighbourly. In this paper, we present tight neighbourly triangulations of 4-manifolds on 15 vertices with as an automorphism group. One such example was constructed by Bagchi and Datta (Discrete Math. 311 (citeyearbd102011) 986-995). We show that there are exactly 12 such triangulations up to isomorphism, 10 of which are orientable.

Tight triangulations of closed 3-manifolds

A triangulation of a closed 2-manifold is tight with respect to a field of characteristic two if and only if it is neighbourly; and it is tight with respect to a field of odd characteristic if and only if it is neighbourly and orientable. No such characterization of tightness was previously known for higher dimensional manifolds. In this paper, we prove that a triangulation of a closed 3-manifold is tight with respect to a field of odd characteristic if and only if it is neighbourly, orientable and stacked. In consequence, the Kuhnel-Lutz conjecture is valid in dimension three for fields of odd characteristic. Next let F be a field of characteristic two. It is known that, in this case, any neighbourly and stacked triangulation of a closed 3-manifold is F-tight. For closed, triangulated 3-manifolds with at most 71 vertices or with first Betti number at most 188, we show that the converse is true. But the possibility of the existence of an F-tight, non-stacked triangulation on a larger number of vertices remains open. We prove the following upper bound theorem on such triangulations. If an F-tight triangulation of a closed 3-manifold has n vertices and first Betti number beta(1), then (n - 4) (617n - 3861) <= 15444 beta(1). Equality holds here if and only if all the vertex links of the triangulation are connected sums of boundary complexes of icosahedra. (C) 2015 Elsevier Ltd. All rights reserved.

Harmonic deformation of Delaunay triangulations

We construct harmonic functions on random graphs given by Delaunay triangulations of ergodic point processes as the limit of the zero-temperature harness process. (C) 2012 Elsevier B.V All rights reserved.

Simultaneous aligning and smoothing of Surface triangulations

[EN]In this work we develop a procedure to deform a given surface triangulation to obtain its alignment with interior curves. These curves are defined by splines in a parametric space and, subsequently, mapped to the surface triangulation. We have restricted our study to orthogonal mapping, so we require the curves to be included in a patch of the surface that can be orthogonally projected onto a plane (our parametric space). For example, the curves can represent interfaces between different materials or boundary conditions, internal boundaries or feature lines. Another setting in which this procedure can be used is the adaption of a reference mesh to changing curves in the course of an evolutionary process...

Approximating the MaxMin and MinMax Area Triangulations using Angular Constraints

* A preliminary version of this paper was presented at XI Encuentros de Geometr´ia Computacional, Santander, Spain, June 2005.

Quadratic Time Computable Instances of MaxMin and MinMax Area Triangulations of Convex Polygons

We consider the problems of finding two optimal triangulations of a convex polygon: MaxMin area and MinMax area. These are the triangulations that maximize the area of the smallest area triangle in a triangulation, and respectively minimize the area of the largest area triangle in a triangulation, over all possible triangulations. The problem was originally solved by Klincsek by dynamic programming in cubic time [2]. Later, Keil and Vassilev devised an algorithm that runs in O(n^2 log n) time [1]. In this paper we describe new geometric findings on the structure of MaxMin and MinMax Area triangulations of convex polygons in two dimensions and their algorithmic implications. We improve the algorithm’s running time to quadratic for large classes of convex polygons. We also present experimental results on MaxMin area triangulation.

Some results on open-edge and open mobile guarding of polygons and triangulations

This paper focuses on a variation of the Art Gallery problem that considers open-edge guards and open mobile-guards. A mobile guard can be placed on edges and diagonals of a polygon, and the ‘open’ prefix means that the endpoints of such an edge or diagonal are not taken into account for visibility purposes. This paper studies the number of guards that are sufficient and sometimes necessary to guard some classes of simple polygons for both open-edge and open mobile-guards. A wide range of polygons is studied, which include orthogonal polygons with or without holes, spirals, orthogonal spirals and monotone polygons. Moreover, this problem is also considered for planar triangulation graphs using open-edge guards.

Topology-Guided Tessellation Of Quadratic Elements

Topology-based methods have been successfully used for the analysis and visualization of piecewise-linear functions defined on triangle meshes. This paper describes a mechanism for extending these methods to piecewise-quadratic functions defined on triangulations of surfaces. Each triangular patch is tessellated into monotone regions, so that existing algorithms for computing topological representations of piecewise-linear functions may be applied directly to the piecewise-quadratic function. In particular, the tessellation is used for computing the Reeb graph, a topological data structure that provides a succinct representation of level sets of the function.

Completions of epsilon-dense partial Latin squares

A classical question in combinatorics is the following: given a partial Latin square $P$, when can we complete $P$ to a Latin square $L$? In this paper, we investigate the class of textbf{$epsilon$-dense partial Latin squares}: partial Latin squares in which each symbol, row, and column contains no more than $epsilon n$-many nonblank cells. Based on a conjecture of Nash-Williams, Daykin and H"aggkvist conjectured that all $frac{1}{4}$-dense partial Latin squares are completable. In this paper, we will discuss the proof methods and results used in previous attempts to resolve this conjecture, introduce a novel technique derived from a paper by Jacobson and Matthews on generating random Latin squares, and use this novel technique to study $ epsilon$-dense partial Latin squares that contain no more than $delta n^2$ filled cells in total.

In Chapter 2, we construct completions for all $ epsilon$-dense partial Latin squares containing no more than $delta n^2$ filled cells in total, given that $epsilon < frac{1}{12}, delta < frac{ left(1-12epsilonright)^{2}}{10409}$. In particular, we show that all $9.8 cdot 10^{-5}$-dense partial Latin squares are completable. In Chapter 4, we augment these results by roughly a factor of two using some probabilistic techniques. These results improve prior work by Gustavsson, which required $epsilon = delta leq 10^{-7}$, as well as Chetwynd and H"aggkvist, which required $epsilon = delta = 10^{-5}$, $n$ even and greater than $10^7$.

If we omit the probabilistic techniques noted above, we further show that such completions can always be found in polynomial time. This contrasts a result of Colbourn, which states that completing arbitrary partial Latin squares is an NP-complete task. In Chapter 3, we strengthen Colbourn's result to the claim that completing an arbitrary $left(frac{1}{2} + epsilonright)$-dense partial Latin square is NP-complete, for any $epsilon > 0$.

Colbourn's result hinges heavily on a connection between triangulations of tripartite graphs and Latin squares. Motivated by this, we use our results on Latin squares to prove that any tripartite graph $G = (V_1, V_2, V_3)$ such that begin{itemize} item $|V_1| = |V_2| = |V_3| = n$, item For every vertex $v in V_i$, $deg_+(v) = deg_-(v) geq (1- epsilon)n,$ and item $|E(G)| > (1 - delta)cdot 3n^2$ end{itemize} admits a triangulation, if $epsilon < frac{1}{132}$, $delta < frac{(1 -132epsilon)^2 }{83272}$. In particular, this holds when $epsilon = delta=1.197 cdot 10^{-5}$.

This strengthens results of Gustavsson, which requires $epsilon = delta = 10^{-7}$.

In an unrelated vein, Chapter 6 explores the class of textbf{quasirandom graphs}, a notion first introduced by Chung, Graham and Wilson cite{chung1989quasi} in 1989. Roughly speaking, a sequence of graphs is called "quasirandom"' if it has a number of properties possessed by the random graph, all of which turn out to be equivalent. In this chapter, we study possible extensions of these results to random $k$-edge colorings, and create an analogue of Chung, Graham and Wilson's result for such colorings.

Geometric discretization through primal-dual meshes

This thesis introduces new tools for geometric discretization in computer graphics and computational physics. Our work builds upon the duality between weighted triangulations and power diagrams to provide concise, yet expressive discretization of manifolds and differential operators. Our exposition begins with a review of the construction of power diagrams, followed by novel optimization procedures to fully control the local volume and spatial distribution of power cells. Based on this power diagram framework, we develop a new family of discrete differential operators, an effective stippling algorithm, as well as a new fluid solver for Lagrangian particles. We then turn our attention to applications in geometry processing. We show that orthogonal primal-dual meshes augment the notion of local metric in non-flat discrete surfaces. In particular, we introduce a reduced set of coordinates for the construction of orthogonal primal-dual structures of arbitrary topology, and provide alternative metric characterizations through convex optimizations. We finally leverage these novel theoretical contributions to generate well-centered primal-dual meshes, sphere packing on surfaces, and self-supporting triangulations.