On Finding a Guard that Sees Most and a Shop that Sells Most
Otfried Cheong Alon Efrat October 4, 2003
Abstract We present a near-quadratic time algorithm that computes a point inside a simple polygon P having approximately the largest visibility polygon inside P , and nearlinear time algorithm for finding the point that will have approximately the largest Voronoi region when added to an n-point set. We apply the same technique to find the translation that approximately maximizes the area of intersection of two polygonal regions in near-quadratic time. 1 Intro duction We consider two problems where our goal is to find a point x such that the area of the region V (x) "controlled" by x is as large as possible. In the first problem, we are given a simple polygon P , and V (x) is the visibility polygon of x, that is, the region of points y inside P such that the segment xy does not intersect the boundary of P . In the second problem, we are given a set of points T , and V (x) is the Voronoi cel l of x in the Voronoi diagram of the set T  {x}, that is, the set of points that are closer to x than to any point in T . In both problems, it is straightforward to write a closed formula describing the area of the region controlled by a point x. This area function (inside a region where V (x) has the same combinatorial structure) is the sum of the areas of triangles that depend on the location of x. The function is therefore a sum of square roots of rational functions. This function is cumbersome to handle; in fact it is unknown whether comparing the value of such a function for a specific rational input to the
 Department of Mathematics and Computer Science, TU Eindhoven, P.O. Box 513, 5600 MB Eindhoven, The Netherlands; ocheong@win.tue.nl.  Department of Computer Science, University of Arizona, Tucson, AZ 85721, USA; alon@cs.arizona.edu.  Department of Computer Science, DCL 2111, University of Illinois, 1304 West Springfield Ave., Urbana, IL 61801, USA; http://www.uiuc.edu/~sariel; sariel@uiuc.edu. Work on this paper was partially supp orted by a NSF CAREER award CCR0132901.

Sariel Har-Peled

square root of an integer number is in NP [OPP03]. It seems difficult to solve the problem analytically, and we resort to approximation. In this paper we address the question of efficiently finding a point x that approximately maximizes the area of V (x). More precisely, let µ(x) be the area of V (x), and let µopt = maxx µ(x) be the area for the optimal solution. Given  > 0, we show how to find xapp such that µ(xapp )  (1 -  )µopt . The main motivation for our first problem arises from art-gal lery or sensor placement problems. In a typical problem of this type, we are given a simple polygon P , and wish to find a set of points (guards ) so that each point of P is seen by least one guard. This problem is NP-hard. Art-gallery problems have attracted a lot of research in the last thirty years [O'R87, Urr00]. A natural heuristic for solving art-gallery problems is to use a greedy approach based on area: We first find a guard that maximizes the area seen, next find a guard that sees the maximal area not seen by the first guard, and so on until each point of P is seen by some guard. Ghosh [Gho87] used a similar greedy heuristic to obtain an O(log n)-approximation on the number of guards needed to see an n-edge polygon, if guard locations are constrained to be on the vertices of P . (An improved algorithm obtains an O(log kopt )-approximation [EH02].) No approximation bounds for the greedy approach are known if guards can be located in the interior of P . However, for the related problem of maximizing the area seen by k guards, for a given number k , Hochbaum and Pathria [HP98] showed that k iterations of the greedy algorithm mentioned above construct a (1 - 1/e)approximation to the more general set-cover problem. In Section 2.4, we show how to apply our result to the problem of finding k -guards that see as much as possible of the polygon P . Ntafos and Tsoukalas [NT94] show how to find, for any  > 0, a guard that sees an area of size (1 -  )µopt . Their algorithm requires O(n5 / 2 ) time in the worst case. In Section 2.3, we give a proba-

Copyright © 2004 by the Association for Computing Machinery, Inc. and the Society for industrial and Applied Mathematics. All Rights reserved. Printed in The United States of America. No part of this book may be reproduced, stored, or transmitted in any manner without the written permission of the publisher. For information, write to the Association for Computing Machinery, 1515 Broadway, New York, NY 10036 and the Society for Industrial and Applied Mathematics, 3600 University City Science Center, Philadelphia, PA 19104-2688

1098


bilistic algorithm that finds such an approximation in time O((n2 / 4 ) log3 (n/ )) with high probability. We also show that approximating the largest visible polygon up to a constant factor is 3SUM-hard [GO95], implying that our algorithm is probably close to optimal as far as the dependency on n is concerned.

Our second problem is motivated by the task of placing a new supermarket such that it takes over as many customers as possible from the existing competition. If we assume that customers are uniformly distributed and shop at the nearest supermarket, then our task is indeed to find a point x such that the Voronoi region of x is as large as possible. The area of Voronoi regions has been considered before in the context of games, such as the Voronoi game [ACC+ 01, CHLM02] or the Hotelling game [OBSC00]. As far as we know, the only previous paper discussing maximizing the Voronoi region of a new point is by Dehne et al. [DKS02], who show that the area function has only a single local maximum inside a region where the set of Voronoi neighbors does not change and is in convex position. They give an algorithm for finding (approximately) the optimal new point numerically based on Newton approximation. In Section 3 we show that given a set T of n points and a  > 0, we can find a point xapp such that µ(xapp )  (1 -  )µopt , where µ(x) is the area of the Voronoi region of x in the Voronoi diagram of T  {x}, Our algorithms are based on the theory of and µopt = maxx µ(x). The (deterministic) running 4 approximations. Instead of measuring area directly, we time of the algorithm is O(n/ + n log n). estimate it by counting the number of points of an Our framework captures a variety of other prob- approximation S inside the region. The estimate is lems, where the goal is to maximize the area of some sufficiently tight such that the point that maximizes it region which depends on a multi-dimensional parame- is a good approximation for the optimal solution. The ter. As an example of such a further application, we beauty of this approach is that it turns a continuous consider the problem of matching two planar shapes P problem into a discrete one: we only need to find the and Q under translations. The area of overlap (or the point x such that V (x) contains the largest number of area of the symmetric difference) of two planar regions points of S . If, for s  S , we define W (s) = {x | s  is a natural measure of their similarity that is insensitive V (x)}, then this problem can be solved by computing to noise [AFRW98, dBCD+ 98]. Mount et al. [MSW96] the arrangement of the W (s), for s  S , and inspecting first studied the function mapping a translation vector each face of this arrangement. to the area of overlap of a translated simple polygon P In Section 2.1, we show how to apply this approach with another simple polygon Q, showing that it is con- to our first problem, maximizing the visibility region. tinuous and piecewise polynomial of degree at most two. Unfortunately, it turns out that the size of the If n and m are the number of vertices of P and Q, respec- approximation required is prohibitively large. This is tively, then the function has O((nm)2 ) pieces, and can mainly due to the fact that the area of the optimal be computed within the same time bound. No algorithm solution might only be of the order of 1/n, so our is known that computes the translation maximizing the approximation needs to guarantee an error of less than area of overlap that does not essentially construct the  /n. In Sections 2.2 and 2.3 we show how to work whole function graph. De Berg et al. [dBCD+ 98] gave around these problems, and improve the running time an O((n + m) log(n + m)) time algorithm to solve the to near-quadratic. problem in the case of convex polygons, and gave a In Section 3, we consider the Voronoi region probconstant-factor approximation. Alt et al. [AFRW98] lem. Here we can exploit the geometry of the optimal gave a constant-factor approximation for the minimum solution to decompose the problem into subproblems

area of the symmetric difference of two convex polygons. Finally, de Berg et al. [dBGK+ 03] consider the case where P is the union of n homothets of a convex body C , Q is the union of m homothets of C , the ratio between the largest and smallest homothet is bounded by a constant, and no point of the plane lies in more than a constant number of homothets. They compute a (1 - )-approximation for the maximal area of overlap of P and Q in time O(nm log nm). We consider the case where P and Q are polygonal regions of complexity n and m, where we assume n  m. In time O(m log n + n2 log n) we can compute a translation maximizing the area of overlap up to  times the area of Q--in other words, the error is absolute here. Note that this makes sense in this application: if the maximal area of overlap is only a small percentage of Q (say less than 1% of Q), then P and Q obviously do not match very well. In many applications it will be sufficient to know that there is no decent match possible. If a match of more than 1% is possible, then there is no difference between absolute and relative error. Finally, we consider the case of homothets studied by de Berg et al., and obtain an O(m log n + n log2 n) time algorithm computing a translation that maximizes the overlap, again up to an absolute error . This algorithms are probabilistic, and succeed with high probability.

1099


such that in each subproblem a small -approximation is sufficient. We generate -approximations by random sampling. The reader may wonder why, if apparently random sampling works, we cannot simply generate a random sample X , compute µ(x) for each x  X , and pick the sample point maximizing µ(x). Such an approach appears to work for maximizing the Voronoi region, but the required sample size would be prohibitively large. The approach doesn't work at all for maximizing the visibility region, as we will see in Section 2.1. Our indirect use of random sampling makes indeed all the difference.

time per sample point, after O(n log n) preprocessing (in fact, linear preprocessing is also achievable). We note now that µopt  1/(n - 2), since this quantity is bounded from below by the area of the largest triangle in a triangulation of P . Let's assume that S is an -approximation for  =  /2n, let xapp  P be the point maximizing eS (xapp ), and let xopt  P be the point maximizing µ(xopt ). Then we have µ(xapp )  eS (xapp ) -  /2n  eS (xopt ) -  /2n  µ(xopt ) -  /n  (1 -  )µopt .

In other words, the point xapp  P seeing the maximal number of points of S is a (1 -  )-approximation to the point in P having the largest visibility polygon. 2 Maximizing the visibility region Now note that s  VP (x) ib and only if x  VP (s). f s V 2.1 Using an -approximation In the following, S e the set of visibility P (s) let P denote a simple polygon, µ(·) denote the area Let WS = measure, and assume that the area of P is 1; that polygons defined by the points of S , and let AP (S ) is, µ(P ) = 1. Given a point x  P , let VP (x) denote the denote the arrangement A(WS ). Our problem has visibility polygon of x inside P ; that is, the region in P reduced to finding a point in P that is contained in visible from x. Formally, the largest number of polygons in WS . yx . Lemma 2.1. Given a simple polygon( P , and a paramVP (x) = y  int(P ) t eter  > 0, one can compute, in O n5 / 4 ) log3 (n/ ) Note, that under this definition a visibility polygon is ime, a point x  P , such that µ(x)  (1 -  )µopt . an open set. Let µ(x) denote the area of VP (x), and let Proof. Let  =  /2n. A uniform random sample S of µopt = maxxP µ(x) denote the maximal area. p ( M = O(1/2 log (1/)) = O n2 / 2 ) log(n/ ) Definition 2.1. For a set S of points in P , and a point x  P , let oints from P is an -approximation with high probability [AS00]. |VP (x)  S | We compute, for each point s  S , its visibility eS (x) = , |S | polygon VP (s) using sweeping. Let WS be the resulting set of polygons. The complexity of the arrangement of ( ; be the estimate of the area visible from x. A(WS ) is O(nM 2 ) = O n5 / 4 ) log2 (n/ ) it can be (5 4 t 3 Consider the range space (P, V ), where V = computed in O n / ) log (n/ ) ime. To see the bound on the complexity, observe that {VP (x) | x  P }. The set S is an -approximation a segment inside P might intersect the boundary of for this range space if for any x  P we have (recall a visibility polygon at most twice. The total number that µ(P ) = 1) of edges of the visibility polygons in WS is O(nM ), and each such segment contains at most O(M ) vertices |eS (x) - µ(x)|  . of the arrangement, implying the bound stated. See Valtr [Val98] showed that the VC-dimension of the [GMMN90] for details. range space (P, V ) is bounded by 23. By the Finally, we perform a simple traversal of the approximat(on theorem [AS00], a uniform random sam- arrangement, where we compute for each face the i p ple S of O d/2 ) log (d/ ) oints from a range space number of polygons of WS that contain it. We pick a of of VC dimension d is an -approximation for this point in the face where this number is largest. range space with probability  1 -  . The size of the sample used is too large to make A uniform sample of points from P can be easily obtained by triangulating P , and first choosing the the above algorithm attractive. There are two reasons triangle (with probability proportional to its area), and for this: The value of  has to be chosen sufficiently then choosing a point from inside the triangle. Thus, small to guarantee correctness for the extreme case this uniform sampling can be done in O(log n) expected where µopt  1/n. Furthermore, an -approximation

1100


Figure 1: Canonical counterexample is stronger than what is really required: it guarantees a good approximation for any range. In the next section we will see that testing a "small" (that is, polynomial) number of candidates is sufficient, and in Section 2.3 we will then deal with the problem of possibly small µopt . At this point, the reader may wonder why we do not take a more direct approach of just sampling enough points, for each point computing its visibility polygon, and returning the largest visibility polygon computed. Somewhat surprisingly, this does not work, as demonstrated by the example depicted in Figure 1. Imagine that we stretch the horizontal and vertical corridors until each of them has area 1/n - 1/n10 , while the central room has area 1/n9 . With high probability, a random sample of size, say, O(n) would have sample points only inside those corridors. Furthermore, the sample points would be "deep" in the corridors. As such, every random sample point would see an area  1/n, while one can place a point in the central room that sees area  2/n. In fact, the visibility arrangement we get for such a sample has quadratic complexity and no point is contained in more than two polygons.

By the (simplified form of the) Chernoff inequality [MR95], we have > | = VP (x)  S | Pr - µ(x)  · µ(x) |S | Pr[|X - | >  ]  -2 2 2   e- /2 + e- /4  2 exp 4 1 2 exp(-11 log n)  10 . n The key observation in the above lemma is that because we are estimating µ(x) for a single fixed point x only, the sample we need is considerably smaller than the sample required by an -approximation, which guarantees the approximation bound for every point x at the same time. Naturally, we would like to use such a small sample in the algorithm of Lemma 2.1 and end up with a faster algorithm. However, one has now to be to careful, to argue that the random sample does not overestimate the area of the visibility polygon of some other point in the polygon. We do so by arguing that the random sample correctly estimate the visibility for all vertices of the visibility arrangement induced by S . Lemma 2.3. Let ,  be parameters, let S be a uniform og n sample from P of size M  c2 l2  , where c2 is an appropriate constant, and let x be a vertex of the arrangement AP (S ). 1. If µ(x)   /4, then Pr[|eS (x)|   /2]  1 . n10

2.2 Estimating the area directly Given a point x  P , we can estimate µ(x) by sampling a set S of points in P , and computing the fraction that is visible Proof. Observe, that x is the intersection of the boundary of two visibility polygons defined by two from x (we assume that µ(P ) = 1). points of S . Let T be the set resulting from S by Lemma 2.2. Let ,  be parameters, x be any point in removing those two points. Clearly, the random sample P , such that µ(x)   and 0 <   1. Let S be a T is independent of x. We have og n uniform sample from P of size M  c1 l2  , where c1 is an appropriate constant. Then, |VP (x)  T | |VP (x)  S | |S | eT (x) = = · |T | |S | |T | 1 1  1 , Pr[|eS (x) - µ(x)| >  · µ(x)]  10 . 2  2 n eS (x) + = eS (x) + M -2 10 Proof. This is immediate from the Chernoff inequality. Indeed, let X1 , . . . , XM be indicator variables, such that since, by definition, the visibility polygons are open Xi = 1 if and only ifi the ith sample point si  S is inside sets, and for c2 large enough. In particular, we have VP (x). Let X = Xi , c1 = 44 and |eS (x) - eT (x)|    2 /10. Thus, if µ(x)   /4 then eS (x)  eT (x)  log n log n  = E[X ] = µ(x)M   · c1 2 = 44 2 .  /2 with high probability, by the Chernoff inequality.  

2. If µ(x)   /4 then Pr[|eS (x) - µ(x)| >  · µ(x)]  n10 . 1

1101


Alternatively, for µ(x)   /4, we have by Lemma 2.2 that |   1 . Pr eT (x) - µ(x)| > · µ(x) 2 n10 Observe that |eS (x) - µ(x)|  |eT (x) - µ(x)| + |eS (x) - eT (x)|  |eT (x) - µ(x)| +  2  /10, and since µ(x)   /4, we have Pr[|eS (x) - µ(x)| >  µ(x)]  | 2  >  µ(x)  Pr eT (x) - µ(x)| + 10 |   1 Pr eT (x) - µ(x)| > µ(x) . 2 n10

and find the vertex that is contained in the largest number of visibility polygons induced by the points of S . Clearly, the overall running time of this algorithm is O(nM 2 log n) = O((n3 / 4 ) log3 (n/ )). This algorithm succeeds with high probability. We conclude: Theorem 2.1. Given a simple polygon P , and a (parameter  > t 0, one can compute, in O n3 / 4 ) log3 (n/ ) ime, a point x  P , such that µ(x)  (1 -  )µopt . This algorithm succeeds with high probability.

2.3 Estimating the area of the optimal solution The running time of Theorem 2.1 is dominated by the worst-case value of  (which is a lower-bound on the area of the largest visibility polygon). Thus, it is natural to perform an exponential search for the right value of  . Indeed, set  = 1/2, and use Lemma 2.4. Clearly, in near linear time, we either found the required visibility polygon, or alternatively, we know (with high It is now natural to pick the vertex in the visibility probability) that µopt  1/2. arrangement contained in the largest number of visibilIn the ith iteration, let i = 1/2i , and we check ity polygons as the best placement for a guard. The whether µopt  i , or alternatively, we get a (1 - following lemma testifies that this indeed works with  )-approximation to the area of the largest visibility high probability. polygon. What is the benefit in this approach? Well, in the Lemma 2.4. Let ,  be parameters such that  > 1/n0.1 ith iteration, we know that µ opt  i-1 (with high and  > 1/n. Let S be a uniform sample from P of probability). Thus, with high probability, no point of log n size M  c3 2  , where c3 is an appropriate constant, A (S ) is contained in more than L = 2 M visibility P i i-1 i and let x be the vertex of the arrangement AP (S ) that polygons (see Lemma 2.7 below for a formal proof of this maximizes eS (x ). intuitive claim). Here Si ils the .sample used in the ith o 1 iteration, of size Mi = O 2gn Furthermore,  i 1. If µopt   /4, then Pr[eS (x )   /2]  6 . n l . og n 2. If µopt   /4 then L = 2i-1 Mi = O 2 1 Pr[|eS (x ) - µopt | >  · µopt (x )]  6 . The arrangement AP (Si ) is shal low ; that is, no point in n this arrangement is contained in more than L visibility Proof. As we can argue quite similarly to Lemma 2.3, polygons. we only sketch the needed modifications. Consider the point xopt that realizes maxpP µ(p). Let x be a vertex Definition 2.2. A set S of points in P is t-shallow if of f , where f is the face of AP (S ) that contains xopt . no point in P is contained inside more than t visibility It is easy to verify, that eS (x ) is "close" to eS (xopt ). polygons of WS . Thus, applying Lemma 2.3 to al l vertices of AP (S ), we Lemma 2.5. If S is t-shal low, then the complexity of have that eS (x ) is a good estimate to the maximum the arrangement A (S ) is O(nk t), where n is the P area visibility polygon in P . The arrangement AP (S ) complexity of the polygon P , and k = |S |. 2 4 has O(nM ) = o(n ) vertices, by the assumptions on  and  . Thus, it follows that the probability that those Proof. The complexity of the union of k such visibility polygons is O(nk ) [GMMN90]. By Clarkson and estimates fail, is smaller than (1/n10 )o(n4 ) < 1/n6 . Shor [CS89] this implies that the complexity of the Lemma 2.4 yields an immediate algorithm for esti- at most t-level is O(t2 n(k /t)) = O(nk t). Since in our mating the maximum area visibility polygon in P . In- case, the at most t-level is the entire arrangement, the deed, set  = 1/n, compute a sample S inside P of size lemma follows. M = O((n log n)/ 2 ), compute the arrangement AP (S ),

1102


of L, then every point inside P sees at most an area 2 · 2 + 1 + o(1) (the area of two rectangles corresponding to two lines, and the area of the unit square, plus some minor additional portions of rectangles that might be locally visible). This implies that there is a constant gap between Thus, the running time of the algorithm is dominated the largest visible polygon in P depending on whether by the running time of the last iteration, which takes L has three lines that share a point. Thus, the problem O(nMI L log(nMI L)) time, where I = log2 n . We of approximating the largest visible polygon up to a conclude: constant factor is 3sum-hard. Theorem 2.2. Given a simple polygon P , and In many cases we do not expect to encounter inputs a (parameter  > t 0, one can compute, in 3 24 where the visibility polygon is truly small (that is  1/n O n / ) log (n/ ) ime, a point x  P , such that µ(x)  (1 -  )µopt . This algorithm succeeds with high of the total area of P ). The following corollary might be useful in such a situation. probability. Interestingly, as pointed out to us by Jeff Erickson, this problem is 3sum-hard [GO95]. As this indicates that a subquadratic algorithm is unlikely, the result of Theorem 2.2 is probably close to optimal. Lemma 2.6. Given a simple polygon P , there is a constant c > 0, such that (1 - c)-approximating the largest visible polygon in P is 3sum-hard. C t orollary 2.1. Given a simple polygon nP , and a parameter  > 0, one can compute, in O µopt 4 log3 n  ime, a point x  P , such that µ(x)  (1 -  )µopt . This algorithm succeeds with high probability.

This implies that in the ith iteration, the algorithm computes an arrangement of complexity n l . log n og n O(nMi L) = O  2 i 2

Lemma 2.7. Let P be a simple polygon of area 1, such that the largest visible polygon in P of area   , and let S be a uniform sample of size M = ((log n)/ ). Then, with high probability, no point in P sees more than 2M  Proof. The details of the proof are tedious but straight- points of S . forward, and we only outline it. The basic idea is to carefully extend the example of Figure 1 for the case of Proof. Clearly, it is enough to prove this for all the n arbitrary lines. vertices of the arrangement A = AP (S ). Consider Let L be a set of n lines with integer coefficients. a vertex v of A, defined by the visibility polygon of Deciding whether three lines of L pass through a two points p, q  S , and observe that the number of common point is 3sum-hard. One can resize and visibility polygons of WS that covers v , is determined translate L, in O(n log n) time, such that all the vertices by the set S \ {p, q }, and as such it is a random of the arrangement of L lie in the square [0.25, 0.75]2 . variable independent of p, with expectation at most Next, consider the axis-parallel square S of side length  =  (M - 2) = (log n). As such, arguing as in M centered at the origin, and let us replace every line Lemma 2.2, it follows by the Chernoff inequality, that e.  L by thickening it into a rectangle r (that is, take the probability that p is contained in mor- than 2 M - 2 the Minkowski sum of with an appropriately small polygons of WS is smaller than 2 exp  Namely, 4 ball) such that the intersection of r with S is of area p is covered by at most 2M  - 2 polygons of WS 2. Here M  n10 is an appropriate large number, with high probability. This implies the lemma, as the and a function of the input. Furthermore, all those number of vertices of WS is bounded by O(nM 2 ). rectangles are disjoint outside the unit square (this can be guaranteed by picking M to be large enough). Let R denote the resulting set of rectangles. By picking M 2.4 Finding a go o d set of guards As discussed in large enough, it is easy to guarantee that the topology the introduction, we want to use the greedy algorithm of the union of the rectangles of R is identical to the to find k "good" guards for P . Namely, at every step topology of the union of lines (that is, no faces outside we pick a guard that sees as much as possible of the regions of the polygon of P not covered yet. We find the union disappear, and so on). Next, consider the polygon P = (rR r)  [0, 1]2 . the first guard using Theorem 2.2. To find the following Clearly, we can compute P in O(n log n) time. Now, if guards, we need to slightly modify the algorithm, as there are three lines in L that pass through a common the uncovered region is no longer a simple polygon. point, then there is a point that stabs three rectangles Indeed, assume that {g1 . . . gi } are guards that were of R, and sees an area  3 · 2 - o(1) inside P . Similarly, already assigned, and let Qi  P be the region not i VP (gi ). The if there is no point that is contained in three lines seen by these guards, namely Qi = P \

1103


complexity of Qi is O(ni), as Qi is the complement of the union of i visibility polygons inside P [GMMN90]. We modify the algorithm to pick random sample points only from Qi , and normalize the area of Qi to be 1. It is straightforward to modify the algorithm of Theorem 2.1 to handle this more complicated case, and verify that the algorithm still work. The only ma jor difference being that we set in Theorem 2.1,  = 1/(ni) since Qi can be decomposed into O(n() triangles. Hence i . the running time increases to O i3 n3 / 4 ) log3 (n/ ) Similarly, the runtime of Theorem 2.2 increases to ( . O i2 n2 / 4 ) log3 (n/ ) To analyze the performance of this algorithm, we use the result of [HP98] that shows that a  -approximation algorithm to the heaviest set in a set-cover instance, when used repeatedly k times, results in a 1 - exp(- ) approximation to the heaviest cover with k sets. Thus, plugging our approximation algorithm with the analysis of [HP98] yield the following result.

Lemma 3.1. Let be the largest reach of any Voronoi region VT (t), for t  T . Then  2/4  µopt   2.

Proof. Let p be a point realizing the reach , that is, its distance to the nearest site is . It follows that VT (p) contains the disc with center p and radius /2, and so µ(p)   2/4. The lower bound follows. Let now x be the point realizing the optimal solution, that is µ(x) = µopt , and let y  VT (x) be the point furthest from x. Its distance to the nearest site in T is at most , and so its distance to x is at most . It follows that VT (x) is contained in the disc with radius and center x, implying the upper bound. Note that the largest reach is also the radius of the largest empty circle. It can be computed in O(n log n) time by computing the Voronoi diagram of T and inspecting every vertex. Our goal is to find a point xapp such that µ(xapp )  (1 -  )µopt , for some parameter  > 0. We partition the Theorem 2.3. Given a simple polygon P , a paramunit square (containing T ) into a grid of squares with eter  > 0, and a positive integer k , one can com(32 4 t side length . For each grid cell Q, we will apply the 3 pute, in O k n / ) log (n/ ) ime, a set of k guards approximation technique of Section 2.1. We will define   {g1 . . . gk }  P such that an estimate function eS , such that for any x  Q we i  have 1   µ VP (gi ) - e(-1) ,  2 , |eS (x) - µ(x)|  8 i . and we pick a point xQ  Q maximizing eS (xQ ). Let's VP (gi ) This algorithm where  = max µ first argue that this solves the problem: Let xapp be the {g1 ...gk }P point xQ that maximizes eS (xQ ). Then succeeds with high probability. µ(xapp )  eS (xapp ) -  µopt - =  2  2  eS (xopt ) - 8 8

3 Maximizing the Voronoi region Let T be a given fixed set of n points in the plane. For a point x not necessarily in T , let VT (x) denote the Voronoi region of x in the Voronoi diagram of T  {x}, and let µ(x) denote the area of VT (x). We are looking for a point xopt maximizing µopt = µ(xopt ). For points x outside the convex hull of T , µ(x) would be infinite. There are quite a few ways of avoiding these boundary situations: using torus topology, restricting the point (i.e., supermarket) to lie within a polygon (i.e., city limits), or by adding a boundary that acts as an additional site. In the following we choose the first option, and assume the input is a set of points in a unit square with torus topology. The reader can easily modify the arguments to handle the boundary in a different way. The reach of a Voronoi region VT (x) is the distance between the site x and the furthest point inside VT (x), or, in other words, the radius of the smallest disc centered at x containing VT (x). We can estimate µopt as follows.

 2  µopt -  µopt 4 (1 -  )µopt ,

and so xapp is the desired approximate solution. It remains to show how to define eS and how to find the point xQ , for each grid cell Q. Let's fix a grid cell Q, and let x be a point in Q. The reach of VT (x) is at most , and so VT (x) can intersect only Q itself and its eight neighboring grid cells. Consequently, all points of T participating in the definition of VT (x) lie in Q and the 24 grid cells at distance at most 2 . Let Q denote the union of these 25 grid cells, and let TQ = T  Q . We make use of the following simple lemma. Lemma 3.2. Let S be a square grid of density  in the plane, that is, the distance between neighboring grid points is , and let C be a convex body of diameter at most D. Then µ  (C ) - 2 |C  S | 4D.

1104


4 Shap e matching We set  :=   /64 and let S be a square grid of Let P and Q be polygonal regions of complexity n and m, respectively, where n  m. For a vector x, let density , covering Q . For a point x  Q, let VP Q (x) denote P (x)  Q, where P (x) = {p + x | p  P } 2 is the region obtained by translating P by x, and let eS (x) =  |VT (x)  S | µ(x) denote the area of VP Q (x). As before, let µopt be be the estimate of the Voronoi region of x. Making use maxx µ(x), and let xopt be such that µopt = xopt . We of the fact that the diameter of VT (x) is at most 2 , we assume µ(Q) = 1. We proceed as in Section 2.2. We sample a set S then have by Lemma 3.2 of points in Q, and for a translation x (identified with |eS (x) - µ(x)|  8     2/8, a point x in the plane), we count the fraction that is in P (x) to obtain the estimate and by what we observed above, it remains to find the point xQ  Q maximizing eS (xQ ). To this end, we |VP Q (x)  S | eS = . define |S | s x . The following lemma is the equivalent of Lemma 2.2, W (s) = Q  VT (x) with literally the same proof. Note that W (s) is simply the largest disc with center s Lemma 4.1. Let ,  be parameters, and let x be a that contains no point of T in its interior, clipped to Q. translation such that µ(x)   and 0 <   1. Let Let WS = {W (s) | s  S } and consider the arrangement og n S be a uniform sample from Q of size M  c1 l2  , A(WS ). As in Section 2.1, our problem has reduced to where c1 is an appropriate constant. Then, finding a point in Q that is contained in the largest number of clipped discs in WS . 1 Pr[|eS (x) - µ(x)| >  · µ(x)]  10 . n Theorem 3.1. Given a set T of n points in the plane and a parameter  > 0, one can deterministical ly compute, in time O(n/ 4 + n log n), a point xapp such We now define, for s  S , W (s) = {x | s  P (x)}. that µ(xapp )  (1 -  )µopt . Obviously, W (s) is a copy of P , reflected at the origin Proof. We start by computing the Voronoi diagram of T and inspecting its vertices to determine the largest reach . We then define the square grid, and determine the set of points TQ relevant in each grid cell. Since a point of T is relevant in at most 25 grid cells, the total size of the sets TQ is O(n). For each grid cell Q we take a square grid S of density  =   /64. It consists of M = 25 2/2 = O(1/ 2 ) points. For s  S , the clipped disc W (s) can be determined by finding the nearest neighbor to s in TQ . We do this by simply comparing the distance from s to each point in TQ . The arrangement WS is computed by a sweep-line algorithm in time O(M 2 ). The number of discs containing each face of the arrangement can again be determined by a simple transversal. We pick a point xQ from the face maximizing the estimate eS (xQ ). By the choice of , every grid cell is within distance at most 2 from a point of T . The number of grid and translated. Let AP (S ) be the arrangement of all regions W (s). The following lemma is the equivalent of Lemma 2.3, and its proof is nearly identical. Lemma 4.2. Let ,  be parameters, let S be a uniform og n sample from Q of size M  c2 l2  , where c2 is an appropriate constant, and let x be a vertex of the arrangement AP (S ). 1. If µ(x)   /4, then Pr[|eS (x)|   /2]  1 . n10

Proof. Consider the tessellation of the plane into little squares of side length , where each point of S is the center of one little square. The boundary of C intersects at most 4D/ little squares, which implies the bound.

cells handled is therefore at most O(n). Each point of T appears at most 25M times in a nearest-neighbor computation, and so the overall running time is O(n log n + nM + nM 2 ) = O(n/ 4 + n log n).

2. If µ(x)   /4 then Pr[|eS (x) - µ(x)| >  · µ(x)]  1 . n10 As in Section 2.2, we can now choose the vertex xapp of AP (S ) that maximizes eS (xapp ). Choosing  =  = , we find that µ(xapp )  µopt -  with probability at least 1 - 1/n6 .

1105


The complexity of the arrangement AP (S ) is O(n2 M 2 ) = O(n2 /6 log2 n), and it can be computed within the same time bound. The vertex maximizing eS (xapp ) can be found by a simple traversal of this arrangement. Consider now the case studied by de Berg et al. [dBGK+ 03]. Here, P is the union of n homothets of a convex body C of constant complexity, Q is the union of m homothets of C , the ratio between the largest and smallest homothet is bounded by a constant, and no point of the plane is contained in more than a constant number of homothets. The probabilistic analysis above goes through unchanged, so it remains to bound the complexity of the arrangement AP (S ). It consists of M translated copies of (the reflection of ) P . The boundary of P has complexity n, as it is the union of n pseudodisks, and this boundary can be computed in time O(n log2 n) [KLPS86]. Each boundary segment (belonging to a single homothet of C ) can intersect only a constant number of other homothets in this set of nM homothets, and so the total number of vertices of AP (S ) is at most O(nM 2 ). It can be computed in time O(nM 2 log n) = O(n/6 log3 n), for instance by a plane sweep. 5 Conclusions We have given a near-quadratic time algorithm for approximating the largest visible polygon inside a simple polygon. Our algorithm runs in near-linear time if the visibility polygon is reasonably large, a case that appears relevant in many applications. We also showed that approximating the area of the largest visible polygon is a 3SUM-hard problem [GO95], and as such it is unlikely to have a subquadratic algorithm. In the second part of the paper, we applied a similar technique to the problem of finding the largest Voronoi cell one might occupy by a single point. Unlike the first problem, where direct random sampling does not yield any guaranteed approximation in the worst case, here direct random sampling seems to be possible. To do so, one has to prove that the area of the region i xµ

Acknowledgment We thank Jeff Erickson for sketching out the proof of Lemma 2.6. We also thank Joseph S. B. Mitchell, Christian Knauer, Ren´ van Oostrum, and Helmut Alt e for fruitful discussions regarding the problems addressed in this paper. References
[ACC+ 01] H.-K. Ahn, S.-W. Cheng, O. Cheong, M. Golin, and R. van Oostrum. Competitive facility location along a highway. In 7th Annual International Computing and Combinatorics Conference, volume 2108 of LNCS, pages 237­246, 2001. [AFRW98] H. Alt, U. Fuchs, G. Rote, and G. Weber. Matching convex shapes with respect to the symmetric difference. Algorithmica, 21:89­103, 1998. [AS00] N. Alon and J. H. Spencer. The probabilistic method. Wiley Inter-Science, 2nd edition, 2000. [CHLM02] O. Cheong, S. Har-Peled, N. Linial, and J. Matouek. The one-round Voronoi game. In Proc. s 18th Annu. ACM Sympos. Comput. Geom., pages 97­ 101, 2002. [CS89] K. L. Clarkson and P. W. Shor. Applications of random sampling in computational geometry, II. Discrete Comput. Geom., 4:387­421, 1989. [dBCD+ 98] M. de Berg, O. Cheong, O. Devillers, M. van Kreveld, and M. Teillaud. Computing the maximum overlap of two convex polygons under translations. Theo. Comp. Sci., 31:613­628, 1998. [dBGK+ 03] M. de Berg, P. Giannopoulos, C. Knauer, R. van Oostrum, and R. C. Veltkamp. Maximizing the area of overlap of two unions of convex homothets under translation. Manuscript, 2003. [DKS02] F. Dehne, R. Klein, and R. Seidel. Maximizing a Voronoi region: The convex case. In Proc. 13th Annu. Internat. Sympos. Algorithms Comput., pages 624­634, 2002. [EH02] A. Efrat and S. Har-Peled. Locating guards in art galleries. 2nd IFIP Internat. Conf. Theo. Comp. Sci., pages 181­192, 2002. [Gho87] S. K. Ghosh. Approximation algorithms for art gallery problems. In Proc. Canadian Inform. Process. Soc. Congress, 1987. [GMMN90] L. Gewali, A. Meng, J. S. B. Mitchell, and S. Ntafos. Path planning in 0/1/ weighted regions with applications. ORSA J. Computing, 2:253­272, 1990. [GO95] A. Ga jentaan and M. H. Overmars. On a class of O(n2 ) problems in computational geometry. Comput. Geom. Theory Appl., 5:165­185, 1995. [HP98] D. Hochbaum and A. Pathria. Analysis of the greedy approach in covering problems. Naval Research Quarterly, 45:615­627, 1998. [KLPS86] K. Kedem, R. Livne, J. Pach, and M. Sharir. On the union of Jordan regions and collision-free trans-

A=

(x)  (1 -  )µopt

s sufficiently large to be "hit" be a sample point. The bounds we were able to prove on the area of A result in an algorithm far slower than the one presented here, and used considerably more involved arguments. It seems that this problem is far from being well understood, and we leave it as open problem for further research. (See [DKS02] for related results.)

1106


lational motion amidst polygonal obstacles. Discrete Comput. Geom., 1:59­71, 1986. [MR95] R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, New York, NY, 1995. [MSW96] D. M. Mount, R. Silverman, and A. Y. Wu. On the area of overlap of translated polygons. Computer Vision and Image Understanding: CVIU, 64(1):53­61, 1996. [NT94] S. C. Ntafos and M. Z. Tsoukalas. Optimum placement of guards. Info. Sciences, 76:141­150, 1994. [OBSC00] A. Okabe, B. Boots, K. Sugihara, and S. N. Chiu. Spatial tessel lations: Concepts and applications of Voronoi diagrams. Probability and Statistics. Wiley, 2nd edition edition, 2000. [OPP03] The open problems pro ject. Problem 33: Sum of square roots. http://cs.smith.edu/~orourke/TOPP/P33.html, 2003. [O'R87] J. O'Rourke. Art Gal lery Theorems and Algorithms. The International Series of Monographs on Computer Science. Oxford University Press, New York, NY, 1987. [Urr00] J. Urrutia. Art gallery and illumination problems. In J. Sack and J. Urrutia, editors, Handbook of Computational Geometry, pages 973­1027. North-Holland, 2000. [Val98] P. Valtr. Guarding galleries where no point sees a small area. Israel J. Math, 104:1­16, 1998.

1107