Between umbra and penumbra

Computing shadow boundaries is a difficult problem in the case of non-pointlight sources. A point is in the umbra if it does not see any part of anylight source; it is in full light if it sees entirely all the light sources;otherwise, it is in the penumbra. While the common boundary of the penumbraand the full light is well understood, less is known about the boundary of theumbra. In this paper we prove various bounds on the complexity of the umbra andthe penumbra cast by a segment or polygonal light source on a plane in the presence ofpolygon or polytope obstacles. In particular, we show that a single segment light source may cast on a plane, in thepresence of two triangles, four connected components of umbra and that two fatconvex obstacles of total complexity n can engender (n) connectedcomponents of umbra. In a scene consisting of a segment light source and kdisjoint polytopes of total complexity n, we prove an (nk²+k⁴)lower bound on the maximum number of connected components of the umbra and a O(nk³) upper bound on its complexity. We also prove that, in the presence of kdisjoint polytopes of total complexity n, some of which being light sources,the umbra cast on a plane may have (n²k³ +nk⁵) connected components and has complexity O(n³k³).These are the first bounds on the size of the umbra in terms of both k and n. These results prove that the umbra, which is bounded by arcs of conics,is intrinsically much more intricate than the full light/penumbra boundary whichis bounded by linesegments and whose worst-case complexity is in (nα(k) +km +k²) and O(nα(k) + kmα(k) +k²), where m is the complexity of the polygonallight source.