Given any set of $3$D points, can we always make non-overlapping tetrahedrons from them where the union of tetrahedrons exactly fill the convex hull of the input points?
AFAIK, given any set of $2$D points, we can triangulate them like this:
- Generate all possible segments connecting any two points.
- Randomly add an segment to a list so that the newly-added segment doesn't properly intersect with any segment in the list.
- Make triangles from triplets of adjacent edges from the list.
Proper segment-segment intersection allows two segments to touch each other, but doesn't allow
- two collinear segments to have a shared "length"
- two segments to cross each other
- two identical segments
Two segments are considered adjacent if they have exactly one common endpoint.
Using the approach above, can we extend to $3$D? Like this:
- Generate all possible triangle connecting any three points.
- Randomly add a triangle to a list so that the newly-added triangle doesn't properly intersect with any triangle in the list.
- Make tetrahedrons from quadruplets of adjacent triangles from the list.
Proper triangle-triangle intersection allows
- two triangles to touch each other
- two triangles to share a common edge, or have a collinear edge
but doesn't allow
- two triangles on the same plane to have a shared area
- two triangles to cross each other
- two identical triangles
Two triangles are considered adjacent if they have exactly one common edge.
(I'm not a math person. My definition of segment-segment or triangle-triangle intersection/adjacency might be incomplete, feel free to correct me as usual.)
