# ## Triangles and Simplices

These pointers discuss triangles and their higher-dimensional generalizations (simplices). I am particularly interested in triangulation by which I mean partitioning regions into triangles, tetrahedra, or higher dimensional simplices, for various applications including finite element mesh generation and surface interpolation. (The other meaning of triangulation involves determining locations and distances from certain measurements.) For more material on the first type of triangulation, see the mesh generation section of Geometry in Action or the list of my own triangulation papers. For other kinds of partitions, see the page on dissection.

• Acute square triangulation. Can one partition the square into triangles with all angles acute? How many triangles are needed, and what is the best angle bound possible? • 1st and 2nd Ajima-Malfatti points. How to pack three circles in a triangle so they each touch the other two and two triangle sides. This problem has a curious history, described in Wells' Penguin Dictionary of Curious and Interesting Geometry: Malfatti's original (1803) question was to carve three columns out of a prism-shaped block of marble with as little wasted stone as possible, but it wasn't until 1967 that it was shown that these three mutually tangent circles are never the right answer. See also this Cabri geometry page, the MathWorld Malfatti circles page, and the Wikipedia Malfatti circles page.

• Are all triangles isosceles? A fallacious proof from K. S. Brown's math pages.

• Bounded degree triangulation. Pankaj Agarwal and Sandeep Sen ask for triangulations of convex polytopes in which the vertex or edge degree is bounded by a constant or polylog.

• Calabi's triangle constant, defining the unique non-equilateral triangle with three equally large inscribed squares. Is there a three-dimensional analogue? From MathSoft's favorite constants pages.

• Carnival triangles. A factoid about similar triangles inspired by a trigonometric identity.

• Circumcenters of triangles. Joe O'Rourke, Dave Watson, and William Flis compare formulas for computing the coordinates of a circle's center from three boundary points, and higher dimensional generalizations.

• Cube triangulation. Can one divide a cube into congruent and disjoint tetrahedra? And without the congruence assumption, how many higher dimensional simplices are needed to triangulate a hypercube? For more on this last problem, see Triangulating an n-dimensional cube, S. Finch, MathSoft, and Asymptotically efficient triangulations of the d-cube, Orden and Santos. • Enumeration of polygon triangulations and other combinatorial representations of the Catalan numbers.

• An equilateral dillemma. IBM asks you to prove that the only triangles that can be circumscribed around an equilateral triangle, with their vertices equidistant from the equilateral vertices, are themselves equilateral.

• Equilateral triangles. Dan Asimov asks how large a triangle will fit into a square torus; equivalently, the densest packing of equilateral triangles in the pattern of a square lattice. There is only one parameter to optimize, the angle of the triangle to the lattice vectors; my answer is that the densest packing occurs when this angle is 15 or 45 degrees, shown below. (If the lattice doesn't have to be square, it is possible to get density 2/3; apparently this was long known, e.g. see Fáry, Bull. Soc. Math. France 78 (1950) 152.)

Asimov also asks for the smallest triangle that will always cover at least one point of the integer lattice, or equivalently a triangle such that no matter at what angle you place copies of it on an integer lattice, they always cover the plane; my guess is that the worst angle is parallel and 30 degrees to the lattice, giving a triangle with 2-unit sides and contradicting an earlier answer to Asimov's question. • Erich Friedman's dissection puzzle. Partition a 21x42x42 isosceles triangles into six smaller triangles, all similar to the original but with no two equal sizes. (The link is to a drawing of the solution.)

• Geodesic dome design software. Now you too can generate triangulations of the sphere. Freeware for DOS, Mac, and Unix.

• Hedronometry. Don McConnell discusses equations relating the angles and face areas of tetrahedra. See also McConnell's hedronometry site.

• Heilbronn triangle constants. How can you place n points in a square so that all triangles formed by triples of points have large area?

• Hero's Formula for the area of a triangle in terms of its side lengths. Mark Dominus explains.

• Hyacinthos triangle geometry mailing list.

• Icosamonohedra, icosahedra made from congruent but not necessarily equilateral triangles.

• In plane sight. Equilateral triangle visibility problem from Andy Drucker. See also here.

• The isoperimetric problem for pinwheel tilings. In these aperiodic tilings (generated by a substitution system involving similar triangles) vertices are connected by paths almost as good as the Euclidean straight-line distance.

• Isosceles pairs. Stan Wagon asks which triangles can be dissected into two isosceles triangles.

• Isotiles, workbook on the shapes that can be formed by combining isosceles triangles with side lengths in the golden ratio.

• Japanese Triangulation Theorem. The sum of inradii in a triangulation of a cyclic polygon doesn't depend on which triangulation you choose! Conversely, any polygon for which this is true is cyclic.

• Jordan sorting. This is the problem of sorting (by x-coordinate) the intersections of a line with a simple polygon. Complicated linear time algorithms for this are known (for instance one can triangulate the polygon then walk from triangle to triangle); Paul Callahan discusses an alternate algorithm based on the dynamic optimality conjecture for splay trees.

• Kabon Triangles. How many disjoint triangles can you make out of n line segments? From Eric Weisstein's treasure trove of mathematics. According to Toshi Kato, these should actually be called Kobon triangles, after Kobon Fujimura in Japan; Kato also tells me that Mr. Saburo Tamura proved a bound of F(n) <n(n-2)/3. • Richard Kenyon's Gallery of tilings by squares and equilateral triangles of varying sizes.

• A map of all triangles and the search for the ideal acute scalene triangle, Robert Simms.

• Monge's theorem and Desargues' theorem, identified. Thomas Banchoff relates these two results, on colinearity of intersections of external tangents to disjoint circles, and of intersections of sides of perspective triangles, respectively. He also describes generalizations to higher dimensional spheres.

• A pair of triangle centers, Vincent Goffin. Do these really count as centers? They are invariant under translation and rotation but switch places under reflection.

• Parabolic isometry of an ideal hyperbolic triangulation. Animation by John Griffin.

• A pre-sliced triangle. Given a triangle with three lines drawn across it, how to draw more lines to make it into a triangulation? From Stan Wagon's PotW archive.

• Prince Rupert's tetrahedra? One tetrahedron can be entirely contained in another, and yet have a larger sum of edge lengths. But how much larger? From Stan Wagon's PotW archive.

• Rational triangles. This well known problem asks whether there exists a triangle with the side lengths, medians, altitudes, and area all rational numbers. Randall Rathbun provides some "near misses" -- triangles in which most but not all of these quantities are irrational. See also Dan Asimov's question in geometry.puzzles about integer right-angled tetrahedra.

• Rudin's example of an unshellable triangulation. In this subdivision of a big tetrahedron into small tetrahedra, every small tetrahedron has a vertex interior to a face of the big tetrahedron, so you can't remove any of them without forming a hole. Peter Alfeld, Utah.

• Sighting point. John McKay asks, given a set of co-planar points, how to find a point to view them all from in a way that maximizes the minimum viewing angle between any two points. Somehow this is related to monodromy groups. I don't know whether he ever got a useful response. This is clearly polynomial time: the decision problem can be solved by finding the intersection of O(n2) shapes, each the union of two disks, so doing this naively and applying parametric search gives O(n4 polylog), but it might be interesting to push the time bound further. A closely related problem of smoothing a triangular mesh by moving points one at a time to optimize the angles of incident triangles can be solved in linear time by LP-type algorithms [Matousek, Sharir, and Welzl, SCG 1992; Amenta, Bern, and Eppstein, SODA 1997].

• Tetrahedrons and spheres. Given an arbitrary tetrahedron, is there a sphere tangent to each of its edges? Jerzy Bednarczuk, Warsaw U.

• Tetrahedra classified by their bad angles. From "Dihedral bounds for mesh generation in high dimensions". • Three untetrahedralizable objects   • Tim's Triangular Page.

• Triangle centers.

• Triangle geometry and the triangle book. Steve Sigur's web site describing many important triangle centers and loci. According to the site, he also has a book with John Conway on the subject, coming soon.

• Triangle tiling. Geom. Ctr. exhibit at the Science Museum of Minnesota.

• Triangles and squares. Slides from a talk I gave relating a simple 2d puzzle, Escher's drawings of 3d polyhedra, and the combinatorics of 4d polytopes, via angles in hyperbolic space. Warning: very large file (~8Mb). For more technical details see my paper with Kuperberg and Ziegler.

• Federation Square. This building in Melbourne uses the pinwheel tiling as a design motif. Thanks to Khalad Karim for identifying it. Photos by Dick Hess, scanned by Ed Pegg Jr. See this Flickr photopool for many more photos.  • Triangulated pig. M. Bern, Xerox.

• Triangulating 3-dimensional polygons. This is always possible (with exponentially many Steiner points) if the polygon is unknotted, but NP-complete if no Steiner points are allowed. The proof uses gadgets in which quadrilaterals are stacked like Pringles to form wires. • Triangulation numbers. These classify the geometric structure of viruses. Many viruses are shaped as simplicial polyhedra consisting of 12 symmetrically placed degree five vertices and more degree six vertices; the number represents the distance between degree five vertices.

• Triangulations and arrangements. Two lectures by Godfried Toussaint, transcribed by Laura Anderson and Peter Yamamoto. I only have the lecture on triangulations.

• Triangulations with many different areas. Eddie Grove asks for a function t(n) such that any n-vertex convex polygon has a triangulation with at least t(n) distinct triangle areas, and also discusses a special case in which the vertices are points in a lattice.

• Untitled, Forbes Gallery, 1987, Ken Goldberg.

• Frank Zubek's Elusive Cube. Magnetic tetrahedra connect to form dissections of cubes and many other shapes.

From the Geometry Junkyard, computational and recreational geometry pointers.
Send email if you know of an appropriate page not listed here.
David Eppstein, Theory Group, ICS, UC Irvine.
Semi-automatically filtered from a common source file.