Hot spots conjecture for a class of acute triangles

We show that the hot spots conjecture of J. Rauch holds for acute triangles if one of the angles is not larger than \(\pi /6\). More precisely, we show that the second Neumann eigenfunction on those acute triangles has no maximum or minimum inside the domain. We first simplify the problem by showing that absence of critical points on two sides implies no critical points inside a triangle. This result applies to any acute triangle and might help prove the conjecture for arbitrary acute triangles. Then we show that there are no critical points on two sides assuming one small angle. We also establish simplicity for the smallest positive Neumann eigenvalue for all non-equilateral acute triangles. This result was already known for obtuse triangles, and it fails for the equilateral case.     

Tiling Polygons with Lattice Triangles

Given a simple polygon with rational coordinates having one vertex at the origin and an adjacent vertex on the x-axis, we look at the problem of the location of the vertices for a tiling of the polygon using lattice triangles (i.e., triangles which are congruent to a triangle with the coordinates of the vertices being integer). We show that the coordinates of the vertices in any tiling are rationals with the possible denominators odd numbers dependent on the cotangents of the angles in the triangles.     

Tilings of Convex Polygons with Congruent Triangles

By the spectrum of a polygon A we mean the set of triples (??,??,??) such that A can be dissected into congruent triangles of angles ??,??,??. We propose a technique for finding the spectrum of every convex polygon. Our method is based on the following classification. A tiling is called regular if there are two angles of the triangles, ?? and ?? such that at every vertex of the tiling the number of triangles having angle ?? equals the number of triangles having angle ??. Otherwise the tiling is irregular. We list all pairs (A,T) such that A is a convex polygon and T is a triangle that tiles A regularly. The list of triangles tiling A irregularly is always finite, and can be obtained, at least in principle, by considering the system of equations satisfied by the angles, examining the conjugate tilings, and comparing the sides and the area of the triangles to those of A. Using this method we characterize the convex polygons with infinite spectrum, and determine the spectrum of the regular triangle, the square, all rectangles, and the regular N-gons with N large enough.     

Delaunay refinement algorithms for triangular mesh generation

Delaunay refinement is a technique for generating unstructured meshes of triangles for use in interpolation, the finite element method, and the finite volume method. In theory and practice, meshes produced by Delaunay refinement satisfy guaranteed bounds on angles, edge lengths, the number of triangles, and the grading of triangles from small to large sizes. This article presents an intuitive framework for analyzing Delaunay refinement algorithms that unifies the pioneering mesh generation algorithms of L. Paul Chew and Jim Ruppert, improves the algorithms in several minor ways, and most importantly, helps to solve the difficult problem of meshing nonmanifold domains with small angles.

Although small angles inherent in the input geometry cannot be removed, one would like to triangulate a domain without creating any new small angles. Unfortunately, this problem is not always soluble. A compromise is necessary. A Delaunay refinement algorithm is presented that can create a mesh in which most angles are 30° or greater and no angle is smaller than arcsin[( , where φ60°is the smallest angle separating two segments of the input domain. New angles smaller than 30° appear only near input angles smaller than 60°. In practice, the algorithm's performance is better than these bounds suggest.

Another new result is that Ruppert's analysis technique can be used to reanalyze one of Chew's algorithms. Chew proved that his algorithm produces no angle smaller than 30° (barring small input angles), but without any guarantees on grading or number of triangles. He conjectures that his algorithm offers such guarantees. His conjecture is conditionally confirmed here: if the angle bound is relaxed to less than 26.5°, Chew's algorithm produces meshes (of domains without small input angles) that are nicely graded and size-optimal.     

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.     

Minimal enclosing discs,circumcircles, and circumcenters in normed planes (Part II)

Until now there are almost no results on the precise geometric location of minimal enclosing balls of simplices in finite-dimensional real Banach spaces. We give a complete solution of the two-dimensional version of this problem, namely to locate minimal enclosing discs of triangles in arbitrary normed planes. It turns out that this solution is based on the classification of all possible shapes that the intersection of two norm circles can have, and on a new classification of triangles in normed planes via their angles. We also mention that our results are closely related to basic notions like coresets, Jung constants, the monotonicity lemma, and d-segments.     

The dissection of a polygon into nearly equilateral triangles

Every polygon can be dissected into acute triangles. In this paper we prove that every polygon, such that the interior angles are at least /5, can be dissected into triangles with interior angles all less than or equal to 2/5. We find necessary conditions on the interior angles of the polygon in order to obtain a dissection into triangles with interior angles all (where /3<<2/5). The conjecture can be stated that these conditions are also sufficient.     

Tilings of polygons with similar triangles

We prove that if a polygonP is decomposed into finitely many similar triangles then the tangents of the angles of these triangles are algebraic over the field generated by the coordinates of the vertices ofP. IfP is a rectangle then, apart from four sporadic cases, the triangles of the decomposition must be right triangles. Three of these sporadic triangles tile the square. In any other decomposition of the square into similar triangles, the decomposition consists of right triangles with an acute angle such that tan is a totally positive algebraic number. Most of the proofs are based on the following general theorem: if a convex polygonP is decomposed into finitely many triangles (not necessarily similar) then the coordinate system can be chosen in such a way that the coordinates of the vertices ofP belong to the field generated by the cotangents of the angles of the triangles in the decomposition.This work was completed while the author had a visiting position at the Mathematical Institute of the Hungarian Academy of Sciences.     

The 4-triangles longest-side partition of triangles and linear refinement algorithms

In this paper we study geometrical properties of the iterative 4-triangles longest-side partition of triangles (and of a 3-triangles partition), as well as practical algorithms based on these partitions, used both directly for the triangulation refinement problem, and as a basis for point insertion strategies in Delaunay refinement algorithms. The 4-triangles partition is obtained by joining the midpoint of the longest side with the opposite vertex and the midpoints of the two remaining sides. By means of simple geometrical arguments we show that the iterative partition of obtuse triangles systematically improves the triangles (while they remain obtuse) in the following sense: the sequence of smallest angles monotonically increases while the sequence of largest angles monotonically decreases in an amount (at least) equal to the smallest angle of each iteration. This allows us to improve the known bound on the smallest angle (without making use of previous results), and to obtain a better a priori bound on the number of similarly distinct triangles, as a function of the geometry of the initial triangle. Numerical evidence, showing that the practical behavior of the 4-triangles partition is in complete agreement with this theory, is included. A 4-triangles refinement algorithm is also discussed and illustrated. Furthermore, we show that the time cost of the algorithm is linear independently of the size of the triangulation.

     

Triangulation refinement by using edge subdivision

It is proved that any triangulation of a flat polygonal region can be refined by using repeated subdivisions of an edge so that: (1) the maximum diameter of the triangles would be less than any pre-assigned positive number, and (2) the minimum interior angle of the triangles of the triangulation obtained would be not less than the minimum interior angle of the triangles of the original triangulation divided by 9. The required triangulation refinement is constructed in two steps: first, the triangulation is refined so that the triangles of the triangulation obtained can be combined into pairs, and only boundary triangles may be left unpaired; at this step each triangle is split into at most 4 parts. Then the triangulation obtained is refined once again in order that the diameter of each triangle be less then a prescribed ?. At each of the steps, the minimum interior angle of triangles is reduced by at most 3 times. This is guaranteed by the lemma saying that the interior angles of the triangles into which the original triangle is divided by a median are at least as great as one-third of the minimum interior angle of the original triangle.     

Precise bounds and asymptotics for the first Dirichlet eigenvalue of triangles and rhombi

We study the asymptotic expansion of the first Dirichlet eigenvalue of certain families of triangles and of rhombi as a singular limit is approached. In certain cases, which include isosceles and right triangles, we obtain the exact value of all the coefficients of the unbounded terms in the asymptotic expansion as the angle opening approaches zero, plus the constant term and estimates on the remainder. For rhombi and other triangle families such as isosceles triangles where now the angle opening approaches π, we have the first two terms plus bounds on the remainder. These results are based on new upper and lower bounds for these domains whose asymptotic expansions coincide up to the orders mentioned. Apart from being accurate near the singular limits considered, our lower bounds for the rhombus improve upon the bound by Hooker and Protter for angles up to approximately 22° and in the range (31°,54°). These results also show that the asymptotic expansion around the degenerate case of the isosceles triangle with vanishing angle opening depends on the path used to approach it.     

Cross-Ratios and Angles Determine a Polygon

We prove that a unique simple polygon is determined, up to similarity, by the interior angles at its vertices and the cross-ratios of diagonals of any given triangulation. (The cross-ratio of a diagonal is the product of the ratio of edge lengths for the two adjacent triangles.) This establishes a conjecture of Driscoll and Vavasis, and shows the correctness of a key step of their algorithm for computing Schwarz—Christoffel transformations mapping a disk to a polygon. Received April 10, 1998, and in revised form March 24, 1999.     

Decomposition of closed orientable geometric surfaces into acute geodesic triangles

We prove that for every \(g\ge 2\), a differentiable closed orientable geometric surface of genus g may be decomposed into \(16g-16\) acute geodesic triangles. We also determine the number of acute geodesic triangles needed for the sphere and the torus.     

Adaptive simplification of huge sets of terrain grid data for geosciences applications

We propose and discuss a new Lepp-surface method able to produce a small triangular approximation of huge sets of terrain grid data by using a two-goal strategy that assures both small approximation error and well-shaped 3D triangles. This is a refinement method which starts with a coarse initial triangulation of the input data, and incrementally selects and adds data points into the mesh as follows: for the edge e having the highest error in the mesh, one or two points close to (one or two) terminal edges associated with e are inserted in the mesh. The edge error is computed by adding the triangle approximation errors of the two triangles that share e, while each L₂-norm triangle error is computed by using a curvature tensor (a good approximation of the surface) at a representative point associated with both triangles. The method produces triangular approximations that capture well the relevant features of the terrain surface by naturally producing well-shaped triangles. We compare our method with a pure L₂-norm optimization method.     

On the Helly Number for Line Transversals to Parallel Triangles

We prove two results about the problem of finding the Helly number for line transversals to a family of parallel triangles in the plane: (1) If each three triangles of a family of parallel right triangles are intersected by an ascending (or a descending) line, then there is an ascending (or a descending) line that intersects all     

Linear Precision for Toric Surface Patches

We classify the homogeneous polynomials in three variables whose toric polar linear system defines a Cremona transformation. This classification includes, as a proper subset, the classification of toric surface patches from geometric modeling which have linear precision. Besides the well-known tensor product patches and Bézier triangles, we identify a family of toric patches with trapezoidal shape, each of which has linear precision. Furthermore, Bézier triangles and tensor product patches are special cases of trapezoidal patches.     

Acute Triangulations of the Regular Icosahedral Surface

We prove here that the surface of the regular icosahedron can be triangulated with 8 non-obtuse and with 12 acute triangles. We also show these numbers to be smallest possible.     

An interpretation of viète's “calculus of triangles” as a precursor of the algebra of complex numbers

Viète introduced operations over right triangles which are directly related to the multiplication and division of complex numbers. He determined the relationships between the angles and sides of the triangles concerned. His first operation is characterised by what corresponds to the fact that arguments of complex numbers are added when the latter are multiplied, and in a similar theorem he shows what we now can see as the anticipation of the analogous characteristic for division of complex numbers. Viète finds powers of an arbitrary right triangle which correspond to powers of complex numbers. One of his theorems is structurally similar to the modern formulation of De Moivre's theorem. The investigation of this subject promises further results.     

Triangle Contact Representations and Duality

A?contact representation by triangles of a graph is a set of triangles in the plane such that two triangles intersect on at most one point, each triangle represents a vertex of the graph and two triangles intersects if and only if their corresponding vertices are adjacent. De Fraysseix, Ossona de Mendez and Rosenstiehl proved that every planar graph admits a contact representation by triangles. We strengthen this in terms of a simultaneous contact representation by triangles of a planar map and of its dual. A?primal?Cdual contact representation by triangles of a planar map is a contact representation by triangles of the primal and a contact representation by triangles of the dual such that for every edge uv, bordering faces f and g, the intersection between the triangles corresponding to u and v is the same point as the intersection between the triangles corresponding to f and g. We prove that every 3-connected planar map admits a primal?Cdual contact representation by triangles. Moreover, the interiors of the triangles form a tiling of the triangle corresponding to the outer face and each contact point is a corner of exactly three triangles. Then we show that these representations are in one-to-one correspondence with generalized Schnyder woods defined by Felsner for 3-connected planar maps.     

Tilings of triangles

Let T be a non-equilateral triangle. We prove that the number of non-similar triangles Δ such that T can be dissected into triangles similar to Δ is at most 6. On the other hand, for infinitely many triangles T there are six non-similar triangles Δ such that T can be dissected into congruent triangles similar to Δ. For the equilateral triangle there are infinitely many such Δ. We also investigate the number of pieces in the dissections of the equilateral triangle into congruent triangles.