Flip graphs for eight points in 3D space are fully connected

Flip Graphs for Eight Points in Three Dimensions Are Connected

Computational Geometry

Summary

The paper shows that for any arrangement of four to eight points in three-dimensional space, where no four points lie perfectly flat, you can move between different ways of connecting those points step-by-step without removing or adding points. The authors prove this by focusing on one special corner of the shape and breaking down the problem into easier parts. They use a technique that projects 3D shapes onto a flat surface, turning complex spatial connections into simpler planar ones to understand how to change the connections. This result means there is always a way to transform one tetrahedral arrangement into another through a sequence of simple flips.

What this means in practice

  • For 3d modeling software developers: Guarantee the ability to transform mesh configurations of small point sets incrementally for smoother editing and refinement in 3D models.
  • For computer graphics engineers: Improve algorithms handling tetrahedral meshes by ensuring all small datasets can be navigated via flips, aiding mesh optimization and animation.

A theory result. No direct application yet.

Authors

Marc Khoury

Abstract

We prove that every configuration of four through eight points in three-dimensional space, with no four points coplanar, has a connected full geometric flip graph under $2 \leftrightarrow 3$ flips. Every point remains fixed and present throughout the sequence. The proof brings each tetrahedralization into placing form at a convex hull vertex: the tetrahedra not incident to that vertex fill the convex hull of the remaining points. This reduction allows us to establish connectivity by induction, using the connectivity of regular tetrahedralizations. The main geometric tool is radial projection, which turns the tetrahedra incident to a hull vertex into a planar triangulation. When this planar triangulation is regular, varying its lifting heights produces legal spatial flips that progressively shrink the region occupied by the incident tetrahedra and reach placing form. Planar lifting criteria and compatibility constraints between the projections at different hull vertices resolve the remaining small cases. For eight points, at most 35 flips are needed to reach placing form.
View PDFOpen arXiv