Longest edge bisection can fail for high dimensional simplices
Degenerating orbits of the Longest Edge Bisection process
Computational Geometry
Summary
The longest edge bisection process is a way to break down shapes called simplices, which helps in creating meshes used in computer simulations. It was widely believed that this process always behaved nicely without breaks or collapses. But the authors show that in three and higher dimensions, this process can actually fail or degenerate, meaning it doesn’t work as expected. They also find that as the dimension grows, random simplices are almost sure to experience this failure. This challenges previous assumptions and provides new insights into how this process behaves dynamically.
Longest Edge Bisectionsimplexfinite-element mesh refinementdynamical systemdegeneracyhyperbolic behaviorelliptic behaviorprojective shape spacehigh dimensionrandom simplices
Authors
Karim A. Adiprasito, Daniel Kalmanovich, Yaar Solomon
Abstract
We study the Longest Edge Bisection (LEB) process as a dynamical system on the projective shape space of simplices. A long-standing conjecture going back to Adler and Rivara-Levin and motivated by finite-element mesh refinement, often taken as a standing assumption, is that this procedure is non-degenerate and, in fact, in a certain way periodic. We prove: \begin{itemize} \item There are 3-dimensional simplices such that the longest edge-bisection algorithm degenerates. \item There is an open set of 4-dimensional simplices on which the longest edge-bisection algorithm degenerates. \item If parametrizing the space of $d$-dimensional simplices by independent standard Gaussian vectors, then as $d$ increases, a random simplex degenerates asymptotically almost surely. \end{itemize} This is realized through exhibiting hyperbolic behaviour of the LEB process. We also exhibit elliptic behaviour that is nonperiodic.