# How to get the minimal enclosed polyhedra in a Line framework (points connectivity lists)?

Greetings all and thank you. I'm a Ph.D. candidate working on a force structure's 3D tessellation project and get stuck.

I've simplified the system into a set of lines linked together which formed a Line-Framework (points connectivity list). Now I want to get the tessellation of this Line-Framework in a set of minimal convex polyhedra without changing the connectivity of the points. Let me give an example for further description.

The Line-Framework is described in points pairs, e.g.{{P1,P2};{P2,P3};{P2,P9}...}, which can be drawn as follows. Each point Pi has coordinate details.(And all the lines are the same length.)

And I want to have the convex set {v1={P1,P2,P3,P4,P5,P6,P7,P8};v2={P9,P2,P3,P6,P7};v3={P10,P11,P1,P4,P5,P8}}; V=v1+v2+v3. How can I workout the points set collections I need?

I've tried Delaunay triangulation but merging tetrahedra is complicated. THANKS!

The Line-Framework describes the system of a pack of spheres. Each $$P_i$$ is the center of the sphere, and $$\{P_i,P_j\}$$ means that the sphere $$S_i$$ contacts with $$S_j$$. The length of $$\{P_i,P_j\}$$ is $$|P_i,P_j|=R_i+R_j$$.

• Welcome to the site! Have you considered computing the DCEL data structure, and then using some known convex-hull algorithm? Commented Jul 12, 2021 at 9:16
• I'd like to know which properties of your example we can assume to hold in your application. In your example, the graph of your Line-Framework lies on the surface of the polyhedron that is the union of the minimal polyhedra you are looking for. Is this true in general? (this would be false if e.g. an edge between P1,P8 exists) Also, is the union of your polyhedra always bounded by a surface of genus 0? (in other words, is the Line-Framework always a planar graph, as in your example?) Finally, I'm not familiar with the term, "Line-Framework". Could provide a definition or reference? Commented Jul 12, 2021 at 9:51
• If the assumptions I mention hold, then the faces of the polyhedra you look for are either a face of the graph of your Line-Framework, or bounded by a separating non-facial cycle of the Line-Framework. Additionally, each face of the line-framework occurs exactly once and each separating cycle occurs exactly twice. So one approach is to find all separating cycles of your Line-Framework and cut the graph at all of those cycles. Then the faces of all components that remain bound the minimal polyhedra. Commented Jul 12, 2021 at 9:59
• @nirshahar About the convex-hull algorithm, I just know the two-dimensional algorithm in computational geometry gives the convex-hull to a set of points (points cloud). In three dimensions, I know little about the convex hull algorithm. It will be helpful if you can give me some links or examples. Thanks! Commented Jul 12, 2021 at 13:00
• @Discretelizard Thanks for your reply. You've asked a very nice and sharp question. The term "Line-Framework" is a self-used word to describe the system of a pack of spheres. Each $P_i$ is the center of the sphere, and $\{P_i,P_j\}$ means that the sphere $S_i$ contacts with $S_j$. The length of $\{P_i,P_j\}$ $|P_i,P_j| = R_i + R_j$. Commented Jul 12, 2021 at 13:29