An Analysis of Triangulation in Geometrically Noisy Environments using Mathematics

Abstract

This paper uses mathematics to analyze the challenges of geometrically noisy environments on triangulation. Given widely accepted algorithmic triangulation methods, such as O(n ln n) or a simpler O(n³) method, we can mathematically prove that triangulation of any two-dimensional polygonal region is possible, albeit impractical in some cases. Further, we consider the implications of environments in which a z-axis is present, as seen in cellular triangulation. In many of the cases where consideration of the z-axis is necessary, we recognize the absence of a fixed or known point of origin and consider methods of addressing this challenge.

§I Two-Dimensional Polygonal Triangulation

While any two-dimensional polygonal figure can be triangulated, many polygonal figures can only be triangulated using an infinite number of triangles [1]. Through Meisters' Two Ears Theorem, a diagonal triangulation of polygons with three or more vertices is possible, given that an interior triangle can be formed between the two end vertices (represented as A and C in a polygon defined by vertices A, B, and C) [2].

Mathematically, the Proof of Lemma effectively shows that "the degree of each of the nodes is at most three because a triangle in a triangulation may be adjacent to at most three other triangles" [3].

We can easily prove this for polygons with few vertices. For example, a polygon in which n=3 (triangle) will have (n−2) triangles, or one triangle. The same polygon will have (n−3) diagonals, or zero. For a polygon in which n=4 (rectangle), the same calculations apply. The rectangle will result in two triangles formed by one diagonal. In geometrically noisy environments, it may be necessary to triangulate using more than one diagonal, in which case triangulation may prove more complex.

While the triangulation of squares and parallelograms can largely be accomplished by bisecting opposite vertices of the polygon, triangulation of trapezoids cannot be accomplished in the same way, given the lack of horizontal symmetry. Regardless, as is the case with both squares and parallelograms, triangulation can be accomplished with only one diagonal.

It is reasonable to consider the reason why triangulation may be necessary, or at least helpful. Namely, in a figure of three or more vertices, such that points A, B, and C all exist in different coordinates on a two-dimensional plane, the distance of line segment AB plus the distance of line segment BC will be longer than the distance of the hypotenuse represented by side AC. Thus, the distance between points for the purposes of calculations may be reduced through the use of triangulation, as proved by the Pythagorean Theorem [5].

§II Two-Dimensional Circular Triangulation

Proving that triangulation of polygonal figures is always possible in any two-dimensional plane is fairly simplistic mathematically, although triangulation itself may be tedious. In contrast, triangulation of a circle is significantly more complex, and requires many more inherent assumptions in the definition of circular triangulation, which is "a closed subset of the closed disc whose complement is a disjoint union of open triangles with vertices on the circumference of the circle" [6].

True triangulation within a circle would require an infinite number of touching vertices, covering the entire circumference of the circle. This may prove impossible in a circle of unknown origin or size. Regardless, an approximation of triangulation can be accomplished with as few as three vertices, each located on the circumference of the circle. In this case, we can ignore arc length and focus solely on the polygonal region created by the vertices. Thus, in circular triangulation approximations, the same principles of two-dimensional polygonal triangulation apply. This is ideal, as two-dimensional triangulation is the most simple and fastest form of triangulation.

§III Three-Dimensional Triangulation

Three-dimensional triangulation of straight-sided shapes follows many of the same principles of two-dimensional polygonal triangulation. In fact, a standard three-dimensional plane can be comprised of two x-y coordinate planes, in which one of the planes is inverted and rotated 180 degrees around the x-axis.

Translating a three-dimensional object into two-dimensional planes can perhaps best be represented by a cube. The process requires two steps. First, a cross-section of the three-dimensional object must be produced, which will result in the creation of two congruent triangular prisms (cross-sections). Second, we can recognize that the resulting cross-section is comprised entirely of two-dimensional polygons. First, we see two triangular sides, thus requiring no triangulation. Second, we see two parallelograms, each of which is easily triangulated. Additionally, we see the five-vertex polygonal region created by the cross-section, which can be divided into two distinct triangles. Thus, the transition of the three-dimensional cube to six two-dimensional polygons is complete and triangulation is now possible.

While the same principles apply for other straight-sided three-dimensional objects, the translation of the three-dimensional object to two-dimensional polygons may be more complex. Further, in geometrically noisy environments, it may be possible to triangulate using a number of polygons which may be in conflict with efficiency. In cases where the three-dimensional object is comprised of multiple smaller three-dimensional objects, it may be possible to first break the object into smaller three-dimensional objects before producing the cross-sections.

§IV The Addition of Geometric Noise

Geometric noise may result in the necessity for more complex triangulation. Noise may prevent the bisecting of two-dimensional polygonal regions, thus causing the number of vertices, n, to increase as the number of diagonals, d, increases. Further, triangulation of the point in which the noise originated may prove impossible, although it may be possible to detect the noise mathematically using triangulation [1].

As an example, in the case of cellular triangulation, data signals can generally be transmitted off of a minimum of three cell towers, though the triangulation with noise may require more than (n−3) diagonals, and thus more than (n−2) triangles.

The initial accuracy of triangulation will depend on a variety of factors. One influential factor is the position of the cellular user in reference to the point of intersection between the two triangles aligned on the central axis of the polygonal plane created between four or more cellular towers.

While this analysis is done in the second dimension, we can assume that cellular triangulation will occur in a three-dimensional environment. Thus, as previously discussed, it will be required to split the three-dimensional environment into standard three-dimensional objects, produce the relevant cross-sections, and then translate the cross-sections into two-dimensional polygonal figures. By creating a cross-section of the three-dimensional object, the surface area of the polygonal region can be calculated and geographically mapped, as is necessary in many cases of cellular triangulation.

References

1. "Triangulation," Wolfram MathWorld. [Online]. Available: https://mathworld.wolfram.com/Triangulation.html. [Accessed: 22-Feb-2023].
2. A. Bogomolny, "Meisters' two ears theorem," Cut the Knot. [Online]. Available: https://www.cut-the-knot.org/pigeonhole/PolygonalEars.shtml. [Accessed: 22-Feb-2023].
3. A. Bogomolny, "Polygonal ears and triangulation duals," Cut the Knot. [Online]. Available: https://www.cut-the-knot.org/Curriculum/Geometry/TriangulationDual.shtml. [Accessed: 22-Feb-2023].
4. "Triangle," Wolfram MathWorld. [Online]. Available: https://mathworld.wolfram.com/Triangle.html. [Accessed: 22-Feb-2023].
5. A. Head, "Pythagorean Theorem," University of Georgia. [Online]. Available: http://jwilson.coe.uga.edu/emt668/emt668.student.folders/headangela/essay1/pythagorean.html. [Accessed: 22-Feb-2023].
6. D. Aldous, "Triangulating the circle, at random," Berkeley. [Online]. Available: https://www.stat.berkeley.edu/users/aldous/Papers/me62.pdf. [Accessed: 23-Feb-2023].