3D Visibility and Lines in Space

Computing visibility information in a 3D environment is crucial to many applications such as computer graphics, vision and robotics. Typical visibility problems include computing the view from a given point, determining whether two objects partially see each other, and computing the umbra and penumbra cast by a light source. In a given scene, two points are visible if the segment joining them does not properly intersect any obstacle in the scene. The study of visibility is thus intimately related to the study of the set of free line segments in a scene. In this talk, I will review some recent combinatorial and algorithmic results related to non-occluded segments tangent to up to four objects in three dimensional scenes.