Join Copernicus Academic and get access to over 12 million papers authored by 7+ million academics.

Related Articles:

• Image mosaicking using SURF features of line segments.

• A novel anatomy-based five-points eight-line-segments technique for precision subtotal tongue recons Read more...

• Intertypic modular exchanges of genomic segments by homologous recombination at universally conserve Read more...

• Comparison of laparoscopic liver resection for hepatocellular carcinoma located in the posterosuperi Read more...

• Different cut points in detecting child nutritional disorders-where do we draw the line?

Detecting tetrahedralizations of a set of line segments☆

Boting Yang - No affiliation found

2004/10/01 Full-length article DOI: 10.1016/j.jalgor.2004.04.006 Journal: Journal of Algorithms

Abstract:

AbstractLet 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(mnlogn) 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 distinct endpoints of segments 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 a subset of the edge set of a tetrahedralization.