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 Ω(nk2+k4)lower bound on the maximum number of connected components of the umbra and a O(nk3) 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 Ω(n2k3 +nk5) connected components and has complexity O(n3k3).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 +k2) and O(nα(k) + kmα(k) +k2), where m is the complexity of the polygonallight source.

We give a complete description of the Voronoi diagram of three lines in R3. In particular, we show that the topology of the Voronoi diagram is invariant for three lines in general position, that is, that are pairwise skew and not all parallel to a common plane. The trisector consists of four unbounded branches of either a non-singular quartic or of a cubic and line that do not intersect in real space. Each cell of dimension two consists of two connected components on a hyperbolic paraboloid that are bounded, respectively, by three and one of the branches of the trisector. The proof technique, which relies heavily upon modern tools of computer algebra, is of interest in its own right. This characterization yields some fundamental properties of the Voronoi diagram of three lines. In particular, we present linear semi-algebraic tests for separating the two connected components of each two-dimensional Voronoi cell and for separating the four connected components of the trisector. This enables us to answer queries of the form, given a point, determine in which connected component of which cell it lies. We also show that the arcs of the trisector are monotonic in some direction. These properties imply that points on the trisector of three lines can be sorted along each branch using only linear semi-algebraic tests.

In this note we describe the contents of a video illustrating analgorithm for computing the 3D visibility skeleton ofa set of disjoint convex polytopes. The video can be foundat http://www.cs.mcgill.ca/~lzhang15/video/ with file name socg07visidemo.mov.

Motivated by visibility problems in three dimensions, we investigate the complexity and construction of the set of tangent lines in a scene of three-dimensional polyhedra. We prove that the set of lines tangent to four possibly intersecting convex polyhedra in $\mathbb{R}^3$ with a total of n edges consists of $\Theta(n^2)$ connected components in the worst case. In the generic case, each connected component is a single line, but our result still holds for arbitrarily degenerate scenes. More generally, we show that a set of k possibly intersecting convex polyhedra with a total of n edges admits, in the worst case, $\Theta(n^2k^2)$ connected components of maximal free line segments tangent to at least four polytopes. Furthermore, these bounds also hold for possibly occluded lines rather than maximal free line segments. Finally, we present an $O(n^2 k^2 \log n)$ time and $O(nk^2)$ space algorithm that, given a scene of k possibly intersecting convex polyhedra, computes all the minimal free line segments that are tangent to any four of the polytopes and are isolated transversals to the set of edges they intersect; in particular, we compute at least one line segment per connected component of tangent lines.

We prove that the lines tangent to four possibly intersecting convex polyhedra in ℝ3 with n edges in total form Θ(n2) connected components in the worst case. In the generic case, each connected component is a single line, but our result still holds for arbitrary degenerate scenes. More generally, we show that a set of kconvex polyhedra with a total of n edges admits, in the worst case, Θ(n2k2)connected components of (possibly occluded) lines tangent to any four of these polyhedra. We also show a lower bound of Ω(n2k2) on the number of non-occluded maximal line segments tangent to any four of these k convex polyhedra.

In this paper, we show that, amongst n uniformly distributed unit balls in $\mathbb{R}^3$, the expected number of maximal nonoccluded line segments tangent to four balls is linear. Using our techniques we show a linear bound on the expected size of the visibility complex, a data structure encoding the visibility information of a scene, providing evidence that the storage requirement for this data structure is not necessarily prohibitive. These results significantly improve the best previously known bounds of $O(n^{8/3})$ [F. Durand, G. Drettakis, and C. Puech, {ACM Transactions on Graphics}, 21 (2002), pp. 176-206]. Our results generalize in various directions. We show that the linear bound on the expected number of maximal nonoccluded line segments that are not too close to the boundary of the scene and tangent to four unit balls extends to balls of various but bounded radii, to polyhedra of bounded aspect ratio, and even to nonfat three-dimensional objects such as polygons of bounded aspect ratio. We also prove that our results extend to other distributions such as the Poisson distribution. Finally, we indicate how our probabilistic analysis provides new insight on the expected size of other global visibility data structures, notably the aspect graph.

A new hierarchical decomposition of a simple polygon is introduced. The hierarchy has depth O(log n), linear size, and its regions have maximum degree three. Using this hierarchy, circular ray shooting queries in a simple polygon can be answered in O(log* n) query time and O(nlogn) space. If the radius of the circle is fixed, the query time can be improved to O(logn) and the space to O(n). The decomposition is also applied to three other circular arc query problems: shortest directed arc, arc bending, and arc pushing. Using these queries, the largest empty lune determined by two query points in a simple polygon can be computed in O(log3 n) time, while the circular visibility region of a query point in a simple polygon can be reported in time O(m log3 n), where m is the output size.

This paper gives an optimal O(n log n + nk) time algorithm for constructing the levels 1,...,k in an arrangement of n lines in the plane. This algorithm is extended to compute these levels in an arrangement of n unbounded x-monotone polygonal convex chains, of which each pair intersects at most a constant number of times.