Given a straight-line graph embedded in $\mathbb{R}^3$ with known vertex coordinates and edges and no edge intersections, is it possible to find all the enclosed convex polyhedra inside? If so, is there some algorithm to do this that returns the list of vertices for each polyhedron? As an example, this algorithm should return all the tetrahedra in the graph formed by the vertices and edges in a $\mathbb{R}^3$ delaunay triangulation.
3
-
$\begingroup$ Could you define what a straight-line graph is? Simply a graph embedding such that all edges can be parametrized by $tv+(1-t)w$ where $v,w$ are the coordinates of the vertices spanning the respective edge? $\endgroup$– Jens FischerCommented Mar 25 at 17:37
-
$\begingroup$ I mean the map $t\mapsto tv+(1-t)w$ and $t\in [0,1]$. $\endgroup$– Jens FischerCommented Mar 25 at 17:58
-
$\begingroup$ In a straight-line graph all edges are straight lines, so I believe your definition is correct. $\endgroup$– n1psCommented Mar 26 at 7:24
Add a comment
|