Linear method clarifies tetrahedron edge bisection choices
Multiform Longest Edge Bisection of Tetrahedra via Sextuple Permutations
Computational Geometry
Summary
The paper tackles the problem of splitting a 3D shape called a tetrahedron along its longest edge, which becomes tricky when multiple longest edges exist. The authors represent these shapes using numbers that describe their edge lengths squared, making the math simpler and avoiding messy coordinate data. They introduce a way to handle all possible longest-edge choices systematically through sequences called bisection patterns. Their work shows these patterns form neat geometric regions and that complex refinement steps can be reduced to a small set of states, making analysis and computation easier.
What this means in practice
- •For computational geometry engineers: Optimize mesh refinement algorithms by using the linear and combinatorial structure discovered to handle all longest-edge splits efficiently.
- •For finite element method developers: Implement structured and computable tetrahedral mesh refinements that systematically manage ambiguous longest-edge choices for better numerical simulations.
Authors
Agustin Trujillo, Jose Pablo Suarez, Tania Moreno-García
Abstract
We introduce a new formulation of the Longest Edge Bisection (LEB) of tetrahedra entirely in sextuple space R6, where tetrahedra are represented by the squares of their edge lengths. This representation renders the LEB refinement equations fully linear and eliminates the need for coordinate-based data structures. A central difficulty in three-dimensional LEB arises when a tetrahedron possesses multiple longest edges, making the refinement rule intrinsically multivalued. We formalize this phenomenon through the notion of Multiform Longest Edge Bisection (MLEB), which systematically explores all admissible longest-edge choices. To encode this multivalued behavior, we introduce the concept of bisection patterns, defined as sequences of sextuple permutations governing the refinement process. We prove that the set of sextuples sharing a common LEB pattern forms a convex region in R6. For structurally significant families of tetrahedra, including the R1+ family and the Liu-Joe family, we show that the infinite refinement tree collapses into a finite directed graph with eight states. Remarkably, both families are governed by the same graph, differing only in their initial state. This directed-graph formulation provides a unified combinatorial description of the refinement process and offers an efficient computational framework for deep iterative LEB analysis.