Let L be a set of line segments in three dimensional Euclidean space. In this paper, we prove several characterizations of tetrahedralizations. We present an O(nm log n) algorithm to determine whether L is the edge set of a tetrahedralization, where m is the number of segments and n is the number of endpoints in L. We show that it is NP-complete to decide whether L contains the edge set of a tetrahedralization. We also show that it is NP-complete to decide whether L is tetrahedralizable.
展开▼
