ISSN:
1432-2315
Keywords:
Spanning line segments
;
Skeletons
;
Plane polyhedron intersections
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
Abstract A set of spanning line segments ℊ in a polyhedronP preserves the property of intersection; that is, a plane intersectsP if and only if it also intersects ℊ. This paper gives a linear time algorithm for constructing ℊ for a polyhedron withN extreme vertices. IfN is odd, the algorithm is optimal in yielding [N/2] + 1 spanning line segments. IfN is even, it gives (N/2) + 1, which is optimal in some cases and nearly optimal in others.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01782320