Lower bounds on stabbing lines in 3-space

✍ Scribed by M. Pellegrini

• Publisher: Elsevier Science
• Year: 1993
• Tongue: English
• Weight: 433 KB
• Volume: 3
• Category: Article
• ISSN: 0925-7721
• DOI: 10.1016/0925-7721(93)90030-a

✦ Synopsis

Pellegrini,

M., Lower bounds on stabbing lines in 3-space, Computational Geometry: Theory and Applications 3 (1993) 53-58.

A stabbing line for a set of convex polyhedra is extremal if it passes through four edges and is tangent to the polyhedra containing those edges. In this paper we present three constructions of convex polyhedra with many extremal lines. The first construction shows Q(n') extremal stabbling lines constrained to meet two skew lines. The second shows Q(n") extremal lines which are tangent to two polyhedra.

The third shows Q(n') extremal stabbing lines. This last lower bound almost matches the best known upper bound. These lower bounds are relevant for the design and analysis of algorithms constructing the space of stabbing lines.