COMPUTING SPANNING LINE SEGMENTS IN 3 DIMENSIONS

Authors
WANG ME WOO TC CHEN LL CHOU SY
Citation
Me. Wang et al., COMPUTING SPANNING LINE SEGMENTS IN 3 DIMENSIONS, The visual computer, 12(4), 1996, pp. 173-180
Citations number
17
Categorie Soggetti
Computer Science Software Graphycs Programming
Journal title
The visual computer → ACNP
ISSN journal
01782789
Volume
12
Issue
4
Year of publication
1996
Pages
173 - 180
Database
ISI
SICI code
0178-2789(1996)12:4<173:CSLSI3>2.0.ZU;2-1
Abstract
A set of spanning line segments S in a polyhedron P preserves the prop erty of intersection; that is, a plane intersects P if and only if it also intersects S. This paper gives a linear time algorithm for constr ucting S for a polyhedron with N extreme vertices. If N is odd, the al gorithm is optimal in yielding [N/2] + 1 spanning line segments. If N is even, it gives (N/2)+ 1, which is optimal in some cases and nearly optimal in others.