Floodlight illumination problems are art-gallery variants, where a target domain needs to be illuminated by guards, each associated with a field of view. The rotating rays Voronoi diagram is a Voronoi diagram with rays as sites under the angular distance. There is a natural connection of this Voronoi structure with the problem of finding the minimum aperture such that a given set of uniform aperture floodlights illuminates a target domain. In this work we present an interactive visualization software for such problems, supporting different angular distances, namely, oriented and unoriented versions, and for different domains, namely, the plane and simple polygons.

Abstract The farthest-color Voronoi diagram (FCVD) is defined on a set of n points in the plane, where each point is labeled with one of m colors. The colored points constitute a family $$\mathcal {P}$$ P of m clusters (sets) of points in the plane whose farthest-site Voronoi diagram is the FCVD. The diagram finds applications in problems related to facility location, shape matching, data imprecision, and others. In this paper we present structural properties of the FCVD, refine its combinatorial complexity bounds, and present efficient algorithms for its construction. We show that the complexity of the diagram is $$O(n\alpha (m)+\textit{str}(\mathcal {P}))$$ O ( n α ( m ) + str ( P ) ) , where $$\textit{str}(\mathcal {P})$$ str ( P ) is a parameter reflecting the number of straddles between pairs of clusters, which is $$O(m(n-m))$$ O ( m ( n - m ) ) . The bound reduces to $$O(n+ \textit{str}(\mathcal {P}))$$ O ( n + str ( P ) ) if the clusters are pairwise non-crossing . We also present a lower bound, establishing that the complexity of the FCVD can be $$\Omega (n+m^2)$$ Ω ( n + m 2 ) , even if the clusters have pairwise disjoint convex hulls. Our algorithm runs in $$O((n+\textit{str}(\mathcal {P}))\log ^3 n)$$ O ( ( n + str ( P ) ) log 3 n ) -time, and in certain special cases in $$O(n\log n)$$ O ( n log n ) time.

Given a set A of n points in ℝ^d with weight function w: A→ℝ_{> 0}, the Fermat distance function is φ(x): = ∑_{a∈A}w(a)‖x-a‖. A classic problem in facility location dating back to 1643, is to find the Fermat point x*, the point that minimizes the function φ. We consider the problem of computing a point x̃* that is an ε-approximation of x* in the sense that ‖x̃*-x*‖<ε. The algorithmic literature has so far used a different notion based on ε-approximation of the value φ(x*). We devise a certified subdivision algorithm for computing x̃*, enhanced by Newton operator techniques. We also revisit the classic Weiszfeld-Kuhn iteration scheme for x*, turning it into an ε-approximate Fermat point algorithm. Our second problem is the certified construction of ε-isotopic approximations of n-ellipses. These are the level sets φ^{-1}(r) for r > φ(x*) and d = 2. Finally, all our planar (d = 2) algorithms are implemented in order to experimentally evaluate them, using both synthetic as well as real world datasets. These experiments show the practicality of our techniques.