Interactive Uniform Floodlight Illumination and Rotating Rays Voronoi Diagrams

To motivate and facilitate further research on the aforementioned problems, we provide an interactive visualization software (https://github.com/VD-collective/rvd-explorer) that supports both angular distance functions in different domains, namely the plane and polygons. Next, we describe our software and then give an overview of results.

Both the entire plane and polygonal domains are supported. The domain can be chosen by toggling Polygonal domain. In the plane, rays can be placed anywhere in ${ℝ}^2$ and distances are evaluated over the entire ${ℝ}^2$; see, e.g., Figures 2 and 4. In polygonal domains, a polygon $𝒫$ is given with one ray per vertex, and distances are only evaluated inside $𝒫$. When Edge-aligned rays is enabled, each edge $\overline{v_i,v_{i+1}}$ of $𝒫$ induces a ray $r_i$ with apex $v_i$ passing through $v_{i+1}$, as in the Brocard illumination problem [3, 14]; see, e.g., Figures 3 and 5.

The application is implemented in the JavaFX graphics framework. Diagrams are rendered by pixel-based rasterization of the viewport. For each pixel, angular distances to all rays are evaluated and colored by the nearest site. Thus, for a $W\times H$ viewport, each frame renders in $O(nWH)$ time. All computations run on the CPU. To maintain a fluid interactivity, pixel rows are processed in parallel and expensive operations are avoided, e.g., angles are compared without computing their values. Diagram edges are detected by comparing neighboring pixel assignments and selectively supersampled for anti-aliasing. The user interface is built on a custom lightweight library for interactive parameter control.

A comprehensive study of the oriented $\text{RVD}(𝒮)$ was given in [1]. A key property is that the distance function is discontinuous, at $2\pi$, and that the bisectors consist of circular arcs and rays. The worst-case combinatorial complexity of $\text{RVD}(𝒮)$ is shown to be $\mathrm{\Omega }(n^2)$ and the same is true for the complexity of a single Voronoi region. An $O(n^{2+ϵ})$ complexity upper bound, for any $ϵ>0$, is obtained via 3-dimensional envelopes [20]; the same approach yields a construction algorithm running in $O(n^{2+ϵ})$ time.

The unoriented $\text{RVD}(𝒮)$ was first proposed in [9], accompanied by an $\mathrm{\Omega }(n^2)$ worst-case complexity bound. Its bisectors were investigated in [11]; they consist of circular and hyperbolic arcs. Notably, several results of the oriented case [1] carry over: for example, with minor adaptations of the 3-dimensional envelope methods, we can obtain an $O(n^{2+ϵ})$ complexity upper bound and an $O(n^{2+ϵ})$-time algorithm.

The angle ${\alpha }^{\ast }$ takes values in $[2\pi /n,2\pi ]$ in the oriented variant [1], and in the unoriented, it takes values in $[\pi /n,\pi ]$. It can be obtained by a traversal after constructing $\text{RVD}(𝒮)$, so it requires $O(n^{2+ϵ})$ total time [1]. It is unknown whether ${\alpha }^{\ast }$ can be computed faster directly, without $\text{RVD}(𝒮)$. Still, computing ${\alpha }^{\ast }$ admits an $\mathrm{\Omega }(n\log n)$ lower bound: the simple case where all rays share the same apex is equivalent to the Max-Gap problem on a circle, which has an $\mathrm{\Omega }(n\log n)$ lower bound in the real RAM model [13, 19].

The Voronoi diagram $\text{RVD}(𝒮)$ constrained to a convex polygon $𝒫$ was studied extensively in [1]. It is a tree, has $\mathrm{\Theta }(n)$ combinatorial complexity, and can be constructed in optimal deterministic $\mathrm{\Theta }(n)$ time using an elaborate divide-and-conquer scheme. This result is accompanied by a simple $O(n\log n)$-time algorithm; a similar algorithm to directly compute ${\alpha }^{\ast }$ is given in [3]. The angle ${\alpha }^{\ast }$ takes values in $(0,\pi /2-\pi /n]$ [1].

For simple polygons few results are known. The challenge comes from the presence of reflex vertices which obstruct the visibility of the rays. To construct $\text{RVD}(𝒮)$, an $O(n^{4+ϵ}r)$-time algorithm was described in [14], where $r$ is the number of reflex vertices: $𝒫$ is decomposed in $O(n^{2}r)$ visibility cells in $O(n^3)$ time [8, 10] and the $O(n^{2+ϵ})$-time algorithm [1] is applied in each cell. The above implies an $O(n^{4+ϵ}r)$ combinatorial complexity bound. A worst-case $\mathrm{\Omega }(n^2)$ lower bound can be realized by star-shaped polygons, as the one in Figure 6.

Regarding the angle ${\alpha }^{\ast }$, an $O(n^3{\log }^{2}n)$-time algorithm to compute it directly was given in [3]. The angle takes values in $(0,2\pi -\pi /6)$ and instances arbitrarily close to the upper bound can be realized by windmill-shaped polygons as shown in Figure 7. It is a regular triangle with three outward wings attached on the corners.