# Sort array of 3D points to maximize number of tetrahedra in the array

Let $$P$$ be a indexable set(array) of points in $$\mathbb{R}^3$$ s.t. $$P = \{p_0,p_1,p_2,...,p_n\}, p_i \in\mathbb{R}^3$$.

I want to sort $$P$$ so that every 4 consecutive points forms a non-coplanar tetrahedra/3D-simplex/triangular pyramid (whatever you personally call it), I know there will be left over points, so I want to do this maximally, meaning I want to create the maximum number of tetrahedra from the set of points and have them back-to-back in the array as every 4 points. And any left-over points will be at the end of the array (after the tetrahedra) where I will have the starting index stored for those leftover points.

Does anyone know how to accomplish this? (and yes the tetrahedra can be arbitrary with no constraints, meaning they are allowed to intersect, but a point can only be used for a single tetrahedra)

(I know I can find a single simplex by first finding 2 points that are at a distance of $$\epsilon$$ away from each other (meaning I have 2 distinct points) then find a third point that is not colinear by using the orientation test (cross product not the zero vector of 2 vectors formed from the 3 points) then finding a fourth point by using the plane normal test (now that we have 3 points that form a plane we can create a vector from the plane to a new fourth point and compare the dot product of that point with the plane normal and if it is not zero then we have a valid simplex)). (Some thoughts on where to search is to see if this maximization problem has maybe a dual known minimization problem which I don't know what would be or to figure out if the naive algorithm of just grouping 4 points at a time until you can't anymore achieve the maximum or not).

• It is not fully clear to me if the quadruples overlap or not (i.e. $1-2-3-4, 2-3-4-5, \cdots$ or $1-2-3-4, 5-6-7-8\cdots$.
– user16034
Sep 26, 2022 at 8:30
• It looks like you actually want to tesselate a point set in $\mathbb{R}^3$ into tetrahedrons. It's well studied problem, and many algorithms exist - please see: scicomp.stackexchange.com/questions/2026/… Sep 27, 2022 at 0:59
• And also this: doc.cgal.org/latest/Triangulation_3/index.html Sep 27, 2022 at 1:00
• @YvesDaoust the second way, where each index is only used once Sep 27, 2022 at 4:05
• @HEKTO I want to do this because this will be a good preprocessing step for creating 3D convex hull's on the gpu when doing the divide and conquer merge strategy. (at least that is what I am attempting to do) Sep 27, 2022 at 4:06