Good Illumination of Minimum Range

A point p is 1-well illuminated by a set F of n point lights if p lies in the interior of the convex hull of F. This concept corresponds to triangle-guarding or well-covering. In this paper we consider the illumination range of the light sources as a parameter to be optimized. First, we solve the problem of minimizing the light sources' illumination range to 1-well illuminate a given point p. We also compute a minimal set of light sources that 1-well illuminates p with minimum illumination range. Second, we solve the problem of minimizing the light sources' illumination range to 1-well illuminate all the points of a line segment with an O(n^2) algorithm. Finally, we give an O(n^2 log n) algorithm for preprocessing the data so that one can obtain the illumination range needed to 1-well illuminate a point of a line segment in O(log n) time. These results can be applied to solve problems of 1-well illuminating a trajectory by approaching it to a polygonal path.


Introduction and definitions
Visibility or illumination has been the main topic for a lot of different works but most of them cannot be applied to real life, since they deal with ideal concepts. For instance, light sources have some restrictions since they cannot illuminate an infinite region as their light naturally fades as the distance grows. As well as cameras or robot vision systems, both have severe visibility range restrictions because they cannot observe with sufficient detail far away objects. We present some of these illumination problems adding several restrictions to make them more realistic, each light source has a limited illumination range so their illuminated regions are delimited. We use a limited visibility definition due to Ntafos [13] as well as a new concept related to this type of problems, the t-good illumination due to Canales et. al [1,6]. This last concept tests the light sources' distribution in the plane. If they are somehow surrounding the object we want to illuminate, there is a big chance it is 1-well illuminated (1-good illumination is also known as △-guarding [14] or well-covering [9]). This paper is solely focused in an optimization problem related to limited 1-good illumination. We propose the linear algorithm MER-Point to calculate the Minimum Embracing Range (MER) of a point in the plane and it also solves the decision problem. We move on to the computation of the MER of a line segment. In order to do this, we propose an algorithm that takes advantage of the Parametric Search [10,11] and runs in O(n 2 ) time. Our last algorithm is the main result in this paper as it computes the E-Voronoi diagram [3] restricted to a line segment which allows us to obtain the illumination range needed to 1-well illuminate a query point of the line segment in O(log n) time.
Let F be a set of n light sources in the plane that we call sites. Each light source fi ∈ F has limited illumination range r > 0, this is, they can only illuminate objects that are within the circle centered at fi with radius r. As we only consider 1-good illumination, throughout this paper we will refer to it just as illumination. The first two problems minimize the light sources' range while illuminating certain objects (points and line segments). On the third one, we also try to answer efficiently which light source embraces any given point in a line segment, this is, we want to compute the E-Voronoi Diagram restricted to a line segment. The next definitions follow from the notation introduced by Chiu and Molchanov [8], where CH(F ) denotes the convex hull of the set F . Definition 1.1 A set of points F is called an embracing set for a point p in the plane if p lies in the interior of the CH(F ). Definition 1.2 A site fi ∈ F is an embracing site for p if p is an interior point of the convex hull formed by fi and by all the sites of F closer to p than fi.
Following this definition, there may be more than one embracing site for a point p. Since we are trying to minimize the light sources' illumination range, in fact, we are trying to compute the closest embracing site for point p (see Figure 1). The NNE-graph [8] consists of a set of vertices V where each vertex v ∈ V is connected to its first nearest neighbour, its second nearest neighbour, ..., until v is in the convex hull of its nearest neighbours. Chan et al. [7] present several algorithms to construct the NNE-graph. Figure 1: The light sources f 1 and f 5 are embracing sites for point p. The light source f 5 is the closest embracing site for p with illumination range r = d(p, f 5 ). Definition 1.3 Let F be a set of n light sources in the plane. We call Closest Embracing Triangle for a point p, CET(F, p), to a set of three light sources of F containing p in the interior of the triangle they define and where one of the three light sources is the closest embracing site for p.
Since the set of light sources is always F , CET(F, p) is shortened to CET(p) in this paper. Definition 1.4 ([6]) Let F be a set of n light sources in the plane. We say that a point p in the plane is t-well illuminated by F if every open half-plane containing p in its interior, contains at least t light sources of F illuminating p.
This definition tests the light sources' distribution in the plane so that the greater the number of light sources in every open half-plane containing the point p, the better the illumination of p. This concept can also be found under the name of △-guarding [14] or well-covering [9]. The motivation behind this definition is the fact that, in some applications, it is not sufficient to have one point illuminated but some neighbourhood of it [9].
is the shaded open area, so every point that lies inside it is 1-well illuminated by the light sources f 1 , f 2 and f 3 . (b) All the interior points of the CH(f 1 , Definition 1. 5 We say that a point p is 1-well illuminated by the light sources f1, f2 and f3 if p ∈ A E r (f1, f2, f3) for some range r > 0. Definition 1.6 Given a set F of n light sources, we call Minimum Embracing Range to the minimum range needed to 1-well illuminate a point p or a set of points S in the plane, respectively MER(F, p) or MER(F, S).
Since the set F is clear from the context, we will use "MER of a point p" instead of MER(F, p) and "MER of a set S" instead of MER(F, S). Once we have found the closest embracing site for a point, its MER is given by the distance between the point and its closest embracing site. So we know that a point is 1-well illuminated if all the light sources' illumination range is, at leat, the same value as MER. In the next section we focus on our solution to obtain the closest embracing site of F for a point p as well as one CET(p).

Minimum Embracing Range of a Point
Let F be a set of n light sources in the plane and p a point we want to 1-well illuminate. The objective of this section is to compute the value of the MER of p, rm, as well as one CET(p). The closest embracing site for p can be obtained in linear time using the NNE-graph by Chan et. al [7]. The algorithm we present in this section also has the same time complexity.
The MER-Point Algorithm First of all, we compute the distances from p to all the light sources. Afterwards, we compute the median of all the distances in linear time [4]. Depending on this value, we can split the light sources in two halves: the set Fc that contains the closest half to p and the set F f that contains the furthest half. We check whether p ∈ int(CH(Fc)), what is equivalent to test if Fc is an embracing set for p. If the answer is negative, we recurse adding the closest half in F f . Otherwise, we recurse halving Fc. This logarithmic search runs until we find the light source fp ∈ F and the subset F E ⊆ F such that p ∈ int(CH(F E )) but p / ∈ int(CH(F E \ {fp}). The light source fp is the closest embracing site for p and its MER is rm = d(fp, p).
On each recursion, we have to check whether p ∈ int(CH(F ′ )), F ′ ⊆ F . This can be done in linear time [12] if we choose carefully the set of points so that each point is studied only once. As soon as we have computed fp, we can find the two other vertices of a CET(p) in linear time as follows. Consider the circle centered at p of radius rm and the line pfp that splits the light sources inside the circle in two sets. Note that if fp is the closest embracing site for p then there is a semicircle empty of other light sources than fp. A CET(p) has fp and two other light sources in the circle as vertices. Actually, any pair of light sources f l , fr such that each lies on a different side of the line passing through p and fp verifies that p ∈ int(CH(f l , fp, fr)). Proof : Let F be a set of n light sources. The distances from p to all the light sources can be computed in linear time. Computing the median also takes linear time [4], as well as splitting F in two halves. Checking if p ∈ int(CH(F ′ )), F ′ ⊆ F , is linear on the number of light sources in F ′ . So the total time for this logarithmic search is O(n + n 2 + n 4 + n 8 + ...) = O(n). Therefore, we find the closest embracing site for p in linear time. So this algorithm computes the MER of p and a CET(p) in total O(n) time.
The decision problem is trivial after the MER of p is computed. Point p is 1-well illuminated if the given illumination range is greater or equal to the MER of p.

Minimum Embracing Range of a Line Segment
In this section we compute the MER, rm, of a line segment, this is, we compute the minimum illumination range needed to 1-well illuminate a line segment with a set of light sources. Without loss of generality, suppose that a line segment s = p l pr is an horizontal line segment and that p l and pr are respectively the leftmost and the rightmost points of s. Since our solution uses the Parametric Search technique due to Megiddo [10,11], we first concentrate on the following decision problem: given a range r > 0, is s 1-well illuminated by a set F of n light sources?
The algorithm in this section decides if a line segment s is 1-well illuminated knowing that the light sources of F have illumination range r. The idea behind this algorithm is to split s into several open segments and check if r is enough to 1-well illuminate all of them. We will show that, if two consecutive open segments are 1-well illuminated, the point in between also is. Hence, if all segments and both extreme points are 1-well illuminated, so is the segment s.
Let us first introduce some notation. We know that each light source fi ∈ F illuminates a circle centered at itself with radius r, C(fi, r), and that each circle can intersect s in at most two points. Since we have n light sources, there are n such circles and at most 2n intersection points between s and the circles. Let I be the set containing the points p l = i0 and pr = im and all the sorted intersection points according to their x-coordinate i1 . . . im−1.If i k is an intersection point between C(fi, r) and s, let f (i k ) be fi. If i k ∈ I is to the left (resp. right) of f (i k ), it is called the leftmost (rightmost) intersection point. Let also s k = (i k−1 , i k ), with i k−1 , i k ∈ I be the open segment between the intersection points i k−1 and i k , for k = 1, . . . , m. Note that the light sources illuminating s k are the same for all points in s k since its endpoints are consecutive intersections of I. The function F(s k ) returns the set of the light sources that illuminate s k ⊆ s with range r. Knowing that F(s1) = F(i0), the function is recursively defined for k = 1, . . . , m − 1 as follows.
In the Figure 3 there is an example of what happens when the intersection point i k ∈ I is the leftmost point or the rightmost point.
. Since both open segments are 1-well illuminated, i k must lie on the boundary of both convex hulls. Since, by definition of F(s k ), one of the two convex hulls is contained in the other, and both segments are inside the biggest one, i k is also contained. Hence, i k ∈ I is 1-well illuminated.
Proof : By definition of F(s k ), the segment s k is 1-well illuminated if it is interior to the convex hull of this set. Since this convex hull is obviously convex, the segment s k is 1-well illuminated when its endpoints are in the convex hull of F(s k ). Proof : Follows from Lemmas 3.1 and 3.2. An efficient algorithm to solve the Decision Problem is then the following: Check if i0 and im are 1-well illuminated using the MER-Point algorithm. For all k ∈ [1, . . . , m] we compute CH(F(s k )) by simply adding or deleting a point to CH(F(s k−1 )) and check whether s k is 1-well illuminated. If all checks are true, then s is 1-well illuminated; otherwise, it is not. Proposition 3.1 Given a real number r > 0, a set F of n light sources with limited illumination range r and a line segment s, the algorithm described above decides if s is 1-well illuminated by F in O(n log n) time.
Proof : Let F , be a set of n light sources with a limited illumination range r. Checking if p l and pr are 1-well illuminated is linear using the MER-Point algorithm. Sorting the points in I according to their x-coordinate takes O(n log n) time. Computing the set of light sources that illuminate p l is linear but constructing its convex hull takes O(n log n) time. Updating dynamically the convex hull every time we need to add or remove a light source can also be done in O(log n) (amortized) time [5], and checking if both i k−1 , i k are in the CH(F(s k )) takes O(log n) time. Since we have at most 2n intersection points and we spend O(log n) time on each one, this algorithm decides if s is 1-well illuminated by F with range r in O(n log n) time.
Note that this procedure still works when each light source has a different range. Instead of having n circles with the same radius, we have n circles with different radii. After computing the intersection points between the n circles and the line segment, the remaining procedure is exactly the same.

The Algorithm
We have an algorithm to decide if, given a range value, a line segment is 1-well illuminated. In order to compute the minimum range needed to 1-well illuminate the segment, we will apply the Parametric Search technique due to Megiddo [10,11].
Let F be a set of n light sources. Let g be a monotonic function (g(x) ≥ g(y) if x > y) with a root. We want to convert our problem in a monotonic root-finding problem since we have an efficient decision algorithm to solve it. Now we define the function g as follows: We know how to compute if s is 1-well illuminated using the decision algorithm just presented. Our goal to find the greatest root θ * = max{θ : g(θ) = 0} using the Parametric Search and once we have it, the MER of s is rm = 1 θ * . Since we solve the decision problem in O(n log n) time, we can find this root in O(n 2 log 2 n) time. An small improvement in performance can be achieved using the following parallel decision algorithm.  Proof : The sequential decision algorithm takes S(n) ∈ O(n log n) time while the one running in parallel requires T (n) ∈ O(log n) time when using P (n) ∈ O( n 2 log n ) processors. So the total time to evaluate the function g(θ) and finding its greatest root using the Parametric Search, as well as computing the MER of s, is O(S(n)T (n) log P (n)+T (n)P (n)) ∈ O(n log n×log n×log( n 2 log n )+log n× n 2 log n ) ∈ O(n 2 ) time.

The E-Voronoi Diagram Restricted to a Line Segment
In the previous section we have computed the minimum illumination range that a set of light sources must have in order to embrace all the points of a line segment. Now we go further and compute the closest embracing site for every point of the line segment which is equivalent to solve the problem of constructing the E-Voronoi diagram [3] restricted to a line segment s = p l pr. With this structure, it is possible to make a query in O(log n) time to know the minimum illumination range needed to embrace a point of s. As in the previous section, we will assume that s is an horizontal line segment and that p l and pr are respectively the leftmost and rightmost points of s. The next definition can be found under the previous name of MIR-Voronoi region (MIR-VR) [3]. The set of all the E-Voronoi regions is called the E-Voronoi diagram of F (formerly known as the MIR Voronoi Diagram [3]). An algorithm to compute the E-Voronoi diagram of F restricted to a segment s follows.
For each light source f ∈ F , we perform a sweep searching for the points of s that belong to the E-VR(f, F ). When the sweeping for f is done, we have computed all the components of the E-VR(f, F ) restricted to s (note that the E-Voronoi region of a light source is not always connected [3]). When the sweeping is done for all the light sources of F , we have computed the E-Voronoi diagram of F restricted to s.
Let us start computing the E-Voronoi region of a light source f ∈ F restricted to s. Let p f be the closest point on s to the source f . We will sweep from left to right (from p f to pr) and then from right to left (from p f to p l ). When we are moving along s, we change from one E-Voronoi region to another when the point has two closest embracing sites or the point reaches the border of the convex hull of its current closest embracing set. In the first case, this corresponds to the intersection between s and the perpendicular bisectors between the two closest embracing sites of the point. For that reason, we compute the intersection points between s and the perpendicular bisectors between the light sources in F \{f } and f . We keep these intersection points as well as p l , p f and pr sorted by the x-coordinate in two lists (one for each type of sweeping), L1 = {p f , . . . , pr} and L2 = {p f , . . . , p l }. The intersection points between s and the convex hull of the closest embracing set of a point will be added to this list during the sweeping. As the E-VR(f, F ) may not be connected, while sweeping s we might cross several of its components. So to catch up where each component starts or ends, we say that pi ∈ s is a starting (ending) point of the E-VR(f, F ) if it is the point where a component of the E-VR(f, F ) starts (ends). We will only explain the sweeping from left to right using the list L1 (the sweeping from right to left is a mirror of this one).
For each pi ∈ L1 starting on pi = p f , we compute the convex hull of all light sources inside the circle with radius d(f, pi). We use H(f, pi) for this hull. Note that f is on its boundary and call H * (f, pi) the obtained convex hull when deleting f (the two edges adjacent to f are called support lines). We will look for the points pi ∈ s such that pi ∈ int(H(f, pi)) but pi / ∈ int(H * (f, pi)), this is, the points pi ∈ s such that f is their closest embracing site. The following lemmas give the clues to the discretization of the sweeping.  Proof : Given a point pi ∈ L1 and the light source f ∈ F , let pi ∈ int(H * (f, pi)). At first, pi ∈ int(H * (f, pi)) might suggest that pi / ∈ E-VR(f, F ) but this may also suggest that we have just crossed a perpendicular bisector and now there is another light source in F that also 1-well illuminates pi. So if pi ∈ E-VR(f, F ) then pi has two closest embracing sites. This means that the last points on the left of pi are also in the same component of the E-VR(f, F ) as pi, but the points on its right are in a component of another E-Voronoi region. So pi is the ending point of a component of the E-VR(f, F ) restricted to s. Lemma 4.2 Given two consecutive points pi, pi+1 ∈ L1 and the light source f ∈ F , let pi ∈ int (H(f, pi)) but pi / ∈ int (H  *  (f, pi)). If one of the support lines intersects s between pi and pi+1 on si ∈ s, then [pi, si) is a segment contained in the E-VR(f, F ) restricted to s.
Proof : Given two consecutive points pi, pi+1 ∈ L1 and the light source f ∈ F , if pi ∈ int (H(f, pi)) and pi / ∈ int(H * (f, pi)) then it is clear that the point is 1-well illuminated by f so pi ∈ E-VR(f, F ). We know that between pi and pi+1 we do not cross any perpendicular bisector between f and the other light sources in F so if the E-VR(f, F ) ends before pi+1, that is because the set H(f, pi) is not an embracing set for all the points in the segment pipi+1. Let si ∈ s be the intersection point between s and one of the support lines, so the segment between pi and si is 1-well illuminated by the set H(f, pi) (see Figure 4(a)). On the other hand, sipi+1 / ∈ H(f, pi) so it is not 1-well illuminated by f . This means that [pi, si) is a segment contained in the E-Voronoi region of f restricted to s. Proof : Given two consecutive points pi, pi+1 ∈ L1 and the light source f ∈ F , if pi ∈ int (H(f, pi)) and pi / ∈ int(H * (f, pi)) then pi ∈ E-VR(f, F ). If H * (f, pi) intersects s between pi and pi+1 then H(f, pi) is not an embracing set for the whole segment pipi+1 (see Figure 4   time. This is also the (amortized) time spent on dynamically updating the convex hull [5]. So the sweeping for each light source takes O(n log n) time and it computes the restricted E-Voronoi region of the light source we are studying at the moment. Since we have n light sources, the algorithm computes the E-Voronoi diagram of F restricted to s in O(n 2 log n) time.
Using this algorithm, we compute E-Voronoi diagram of F restricted to s and we can also compute the MER of s using the following proposition. This technique takes O(n 2 log n) time but it is simpler than the one presented in the previous section.
Proposition 4.1 Let s be a line segment and F a set of n light sources. The MER of s is given by the biggest distance between a light source f ∈ F and one of the extremes of its E-Voronoi region restricted to s.
Proof : Given a line segment s, the MER of s is the biggest distance between a point of s and its closest embracing site. By definition, a point is in the E-Voronoi region of f ∈ F if f is its closest embracing site. If we compute the biggest distance between a light source f and a point of s in its E-Voronoi region, we get the minimum illumination range needed to 1-well illuminate all the points in the E-VR(f, F ) restricted to s. Let t be the intersection between s and the E-VR(f, F ) and pi be an interior point of t. Assume that p f ∈ t (see Figure 5(a)), since p f is the closest point of t to f , the distance between pi and f increases when we are moving away from p f along t. So the minimum illumination range needed to 1-well illuminate t is the biggest distance between one of its extreme points and f . Now suppose that p f / ∈ t (see Figure 5(b)), this means that the distance d(f, pi) increases if we move pi towards one of the extremes of t and decreases towards the other end. Again, the biggest distance between f and a point of t is the distance between one of its extremes and f . As each light source f ∈ F has a minimum illumination range that can be computed by the distance between f and one of the extremes of its E-Voronoi region restricted to s, the biggest of these minimum illumination ranges is the MER of s.
The most interesting consequence of this algorithm is the following. Proof : Let F be a set of n light sources and s a line segment. We can compute the E-Voronoi diagram of F restricted to s in O(n 2 log n) time using the algorithm described above. This preprocess allows us to have a structure that localizes a point q ∈ s in O(log n) time. Once the point is located, t l t r t l s s p f Figure 5: (a) The E-Voronoi region of f ∈ F is the gray area, d(f, t l ) is the biggest distance between f and a point of t, d(f, p i ) ≤ d(f, t l ), p i ∈ t l t r . (b) For a point p i ∈ t l t r , d(f, p i ) ≤ d(f, t r ) and the latter is the minimum illumination range needed to 1-well illuminate t.
we know what is the E-Voronoi region that it belongs to, this is, we know what is the closest embracing site for q. The MER of q is given by the distance between q and its closest embracing site.
This algorithm and the one in the previous section are also useful when we want to compute the MER to 1-well illuminate a trajectory or a polygonal line. We can decompose the trajectory in several line segments and apply one of the algorithms to each part. This way, we compute a range for each piece and the greatest range of them all is the MER of the whole polygonal line or trajectory. An algorithm that shows how to compute all the different Closest Embracing Triangles for a line segment and their ranges can be found in [2].

Conclusions
The visibility problems solved in this paper consider n light sources. We presented the linear algorithm MER-Point for computing a CET(p) and its MER. This algorithm can also be used to decide if a point in the plane is 1-well illuminated. We also presented a quadratic algorithm to compute the MER of a line segment in the plane using the Parametric Search. Concerning the main subject in this paper, we presented another algorithm that computes the E-Voronoi diagram restricted to a line segment, as well as its MER. Both algorithms can also be extended to compute the MER of either open or closed polygonal lines.