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 Polygons with Similar Triangles, II

Let A be a polygon, and let s (A) denote the number of distinct nonsimilar triangles Δ such that A can be dissected into finitely many triangles similar to Δ . If A can be decomposed into finitely many similar symmetric trapezoids, then s(A)=∞ . This implies that if A is a regular polygon, then s(A)=∞ . In the other direction, we show that if s(A)=∞ , then A can be decomposed into finitely many symmetric trapezoids with the same angles. We introduce the following classification of tilings: a tiling is regular if Δ has two angles, α and β , such that at each vertex of the tiling the number of angles α is the same as that of β . Otherwise the tiling is irregular. We prove that for every polygon A the number of triangles that tile A irregularly is at most c ⋅ n ⁶ , where n is the number of vertices of A. If A has a regular tiling, then A can be decomposed into finitely many symmetric trapezoids with the same angles. <lsiheader> <onlinepub>26 June, 1998 <editor>Editors-in-Chief: &lsilt;a href=../edboard.html#chiefs&lsigt;Jacob E. Goodman, Richard Pollack&lsilt;/a&lsigt; <pdfname>19n3p411.pdf <pdfexist>yes <htmlexist>no <htmlfexist>no <texexist>yes <sectionname> </lsiheader> Received February 17, 1997, and in revised form June 16, 1997.     

A polygon is determined by its angles

We study the problem of reconstructing a simple polygon from angles measured at the vertices of the polygon. We assume that at each vertex v a sensing device returns a list of angles α₁,α₂,…, where αi is the angle between the i-th and the (i+1)-th vertices visible to v in counterclockwise (ccw) order starting with the ccw neighbor of v along the boundary. We prove that the angle measurements at all vertices of a simple polygon together with the order of the vertices along the boundary uniquely determine the polygon (up to similarity). In addition, we give an algorithm for reconstructing the polygon from this information in polynomial time.     

An inequality on the edge lengths of triangular meshes

We give a short proof of the following geometric inequality: for any two triangular meshes A and B of the same polygon C, if the number of vertices in A is at most the number of vertices in B, then the maximum length of an edge in A is at least the minimum distance between two vertices in B. Here the vertices in each triangular mesh include the vertices of the polygon and possibly additional Steiner points. The polygon must not be self-intersecting but may be non-convex and may even have holes. This inequality is useful for many purposes, especially in proving performance guarantees of mesh generation algorithms. For example, a weaker corollary of the inequality confirms a conjecture of Aurenhammer et al. [Theoretical Computer Science 289 (2002) 879-895] concerning triangular meshes of convex polygons, and improves the approximation ratios of their mesh generation algorithm for minimizing the maximum edge length and the maximum triangle perimeter of a triangular mesh.     

Upper bounds for the perimeter of plane convex bodies

We show that the maximum total perimeter of k plane convex bodies with disjoint interiors lying inside a given convex body C is equal to $\operatorname{per}\, (C)+2(k-1)\operatorname{diam}\, (C)$ , in the case when C is a square or an arbitrary triangle. A weaker bound is obtained for general plane convex bodies. As a consequence, we establish a bound on the perimeter of a polygon with at most k reflex angles lying inside a given plane convex body.     

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.     

Dissections of regular polygons into triangles of equal areas

This paper answers the question, “If a regular polygon withn sides is dissected intom triangles of equal areas, mustm be a multiple ofn?” Forn=3 the answer is “no,” since a triangle can be cut into any positive integral number of triangles of equal areas. Forn=4 the answer is again “no,” since a square can be cut into two triangles of equal areas. However, Monsky showed that a square cannot be dissected into an odd number of triangles of equal areas. We show that ifn is at least 5, then the answer is “yes.” Our approach incorporates the techniques of Thomas, Monsky, and Mead, in particular, the use of Sperner's lemma and non-Archimedean valuations, but also makes use of affine transformations to distort a given regular polygon into one to which those techniques apply.     

Steiner polygons in the Steiner problem

A polygon, whose vertices are points in a given setA ofn points, is defined to be a Steiner polygon ofA if all Steiner minimal trees forA lie in it. Cockayne first found that a Steiner polygon can be obtained by repeatedly deleting triangles from the boundary of the convex hull ofA. We generalize this concept and give a method to construct Steiner polygons by repeatedly deletingk-gons,k n. We also prove the uniqueness of Steiner polygons obtained by our method.     

Periodic reflecting paths in right triangles

A reflecting path in a Jordan curve has the ready physical analogies of a billiards ball bouncing off the cushions of a custom billiards table and of a laser beam reflecting off the mirrored boundary of a thin cavity. What does the curve tell us about the possible reflecting paths? Two types of reflecting paths are of perennial interest — periodic paths and dense paths. In 1927, G. D. Birkhoff applied a theorem of Poincaré to the billiards ball analogy to show that for anyk>1 and anyw<k/2, with (w, k)=1, a smooth convex curve admits at least two periodic reflecting paths ofk reflections per cycle and winding numberw. Unfortunately Birkhoff's proof does not extent to polygons, nor has any other method been found to yield such sweeping results. Various techniques have produced results for polygons-with-angles-commensurable-with-π and for acute triangles. It was not clear whether an arbitrary right triangle admitted periodic paths. Two simple constructions demonstrate the existence of periodic reflecting paths in right triangles. This paper explores these two constructions, focusing on the simplest result: Let β represent the smallest interior angle of some right triangle, and letN=[π/2β]?1. Then each point interior to the shorter leg of the right triangle lies on a unique reflecting path of (4k+2) reflections per cycle for allk=1,2,...,N?1; and each point interior to some subsegment of the shorter leg lies on a unique reflecting path of 4N+2 reflections per cycle.     

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.     

Recognition of triangles by covariogram

The paper considers the problem of recognition of triangles by orientation-dependent chord length distribution. The following results are obtained: 1. The explicit form of the covariogram and orientation-dependent chord length distribution function for a triangle. 2. The explicit form for the chord length distribution function for a triangle. 3. The length of the maximal chord of a triangle is continuous function on direction u ∈ S ¹ (S ¹ is the space of all directions in the plane). 4. If we have orientation-dependent chord length distribution function for an everywhere dense set of S ¹, then we can uniquely recognize the triangle with respect to reflections and translations. 5. For any finite subset A ? S ¹, there are two non-congruent triangles with the same values of orientationdependent chord length distribution functions on A.     

On a Heilbronn-type problem

Let F be a convex figure with area |F| and let G(n,F) denote the smallest number such that from any n points of F we can get G(n,F) triangles with areas less than or equal to |F|/4. In this article, to generalize some results of Soifer, we will prove that for any triangle T, G(5,T)=3; for any parallelogram P, G(5,P)=2; for any convex figure F, if S(F)=6, then G(6,F)=4.     

Tensor envelopes of regular categories

We extend the calculus of relations to embed a regular category A into a family of pseudo-abelian tensor categories T(A,δ) depending on a degree function δ. Assume that all objects have only finitely many subobjects. Then our results are as follows:

1.

Let N be the maximal proper tensor ideal of T(A,δ). We show that T(A,δ)/N is semisimple provided that A is exact and Mal'cev. Thereby, we produce many new semisimple, hence abelian, tensor categories.

2.

Using lattice theory, we give a simple numerical criterion for the vanishing of N.

3.

We determine all degree functions for which T(A,δ)/N is Tannakian. As a result, we are able to interpolate the representation categories of many series of profinite groups such as the symmetric groups Sn, the hyperoctahedral groups , or the general linear groups GL(n,Fq) over a fixed finite field.

This paper generalizes work of Deligne, who first constructed the interpolating category for the symmetric groups Sn.     

Going in Circles: Variations on the Money-Coutts Theorem

Given a polygon A ₁,...,A _n, consider the chain of circles: S ₁ inscribed in the angle A ₁, S ₂ inscribed in the angle A ₂ and tangent to S ₁, S ₃ inscribed in the angle A ₃ and tangent to S ₂, etc. We describe a class of n-gons for which this process is 2n-periodic. We extend the result to the case when the sides of a polygon are arcs of circles. The case of triangles is known as the Money-Coutts theorem.     

Existence and convergence of best proximity points

Consider a self map T defined on the union of two subsets A and B of a metric space and satisfying T(A)⊆B and T(B)⊆A. We give some contraction type existence results for a best proximity point, that is, a point x such that d(x,Tx)=dist(A,B). We also give an algorithm to find a best proximity point for the map T in the setting of a uniformly convex Banach space.     

Orders in Uniserial Rings

Let A be a ring, and let T(A) and N(A) be the set of all the regular elements of A and the set of all nonregular elements of A, respectively. It is proved that A is a right order in a right uniserial ring if and only if the set of all regular elements of A is a left ideal in the multiplicative semigroup A and for any two elements a ₁ and a ₂ of A, either there exist two elements b ₁ ∈ A and t ₁ ∈ T(A) with a1b₁ = a ₂t₁ or there exist two elements b ₂∈ A and t ₂∈ T(A) with a ₂ b ₂ = a ₁ t ₂. A right distributive ring A is a right order in a right uniserial ring if and only if the set N(A) is a left ideal of A. If A is a right distributive ring such that all its right divisors of zero are contained in the Jacobson radical J(A) of A, then A is a right order in a right uniserial ring.     

Permutation-operator inequalities on certain symmetry classes of tensors

If A∈T(m, N), the real-valued N-linear functions on E_m, and σ∈S_N, the symmetric group on {…,N}, then we define the permutation operator P_σ: T(m, N) → T(m, N) such that P_σ(A)(x₁,x₂,…,x_N = A(x_σ(1),x_σ(2),…, x_σ(N)). Suppose Σ^q_i=1n_i = N, where the n_i are positive integers. In this paper we present a condition on σ that is sufficient to guarantee that 〈P_σ(A₁?A₂???A_q),A₁?A₂?? ? A_q〉 ? 0 for A_i∈S(m, n_i), where S(m, n_i) denotes the subspace of T(m, n_i) consisting of all the fully symmetric members of T(m, n_i). Also we present a broad generalization of the Neuberger identity which is sometimes useful in answering questions of the type described below. Suppose G and H are subgroups of S_N. We let T_G(m, N) denote all A∈T(m, N) such that P_σ(A) = A for all σ∈G. We define the symmetrizer $\text{S}$_G: T(m, N)→T_G(m,N) such that $\text{S}{}_{\mathrm{G}}\text{(A) = 1/|G|Σ}{}_{\mathrm{\sigma \in G}}\text{P}{}_{\mathrm{\sigma }}\text{(A)}$. Suppose H is a subgroup of G and A∈T_H(m, N). Clearly $\text{6}\text{S}{}_{\mathrm{<mtext>G</mtext>}}\text{6(A) 6? 6A6.}$ We are interested in the reverse type of comparison. In particular, if D is a suitably chosen subset of T_H(m,N), then can we explicitly present a constant C>0 such that $\text{6}\text{S}{}_{\mathrm{G}}\text{(A)6?C6A6}$ for all A∈D?     

A classification of regressive transformation semigroups on chains

For each subchain X?? of a chain X, let T _RE (X,X??) denote the semigroup under composition of all full regressive transformations, ??:X??X?? satisfying x????x for all x??X. Necessary and sufficient conditions for T _RE (X,X??) and T _RE (Y,Y??) to be isomorphic are given. This isomorphism theorem is applied to classify the semigroup of regressive transformations T _RE (X,X??) where X is one of several familiar subchains of ?, the chain of real numbers.     

Tilings of Parallelograms with Similar Right Triangles

We say that a triangle $T$ T tiles the polygon $\mathcal A $ A if $\mathcal A $ A can be decomposed into finitely many non-overlapping triangles similar to $T$ T . A tiling is called regular if there are two angles of the triangles, say $\alpha $ α and $\beta $ β , such that at each vertex $V$ V of the tiling the number of triangles having $V$ V as a vertex and having angle $\alpha $ α at $V$ V is the same as the number of triangles having angle $\beta $ β at $V$ V . Otherwise the tiling is called irregular. Let $\mathcal P (\delta )$ P ( δ ) be a parallelogram with acute angle $\delta $ δ . In this paper we prove that if the parallelogram $\mathcal P (\delta )$ P ( δ ) is tiled with similar triangles of angles $(\alpha , \beta , \pi /2)$ ( α , β , π / 2 ) , then $(\alpha , \beta )=(\delta , \pi /2-\delta )$ ( α , β ) = ( δ , π / 2 - δ ) or $(\alpha , \beta )=(\delta /2, \pi /2-\delta /2)$ ( α , β ) = ( δ / 2 , π / 2 - δ / 2 ) , and if the tiling is regular, then only the first case can occur.     

Conjugate cone characterization of positive definite and semidefinite matrices

Positive definite and semidefinite matrices are characterized in terms of positive definiteness and semidefiniteness on arbitrary closed convex cones in Rⁿ. These results are obtained by generalizing Moreau's polar decomposition to a conjugate decomposition. Some typical results are: The matrix A is positive definite if and only if for some closed convex cone K, A is positive definite on K and (A+A^T)^?1 exists and is semidefinite on the polar cone K°. The matrix A is positive semidefinite if and only if for some closed convex cone K such that either K is polyhedral or (A+A^T)(K) is closed, A is positive semidefinite on both K and the conjugate cone K^A={s∣x^T(A+ A^T)s?0?x∈K}, and (A+A^T)x=0 for all x in K such that x^TAx=0.