Approximation Algorithms for Guarding 1.5 Dimensional Terrains by James Alexander .King B.Math., University of Waterloo, 2003 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR T H E DEGREE OF MASTER OF SCIENCE in The Faculty of Graduate Studies (Computer Science) THE UNIVERSITY OF BRITISH COLUMBIA August, 2005 © James Alexander King, 2005 Abstract ii Abstract The 1.5-dimensional terrain guarding problem gives an x-monotone chain (the terrain) and asks for the minimum set of vertices of the terrain (guards) such that every vertex of the terrain is seen by at least one guard. This terrain guarding problem is a restriction of the SET COVER problem, which is known to be both NP-complete and inapproximable within a sub-logarithmic factor [19]. Fortunately, it is known that the 1.5-dimensional terrain guarding problem is approximable to within a constant factor [5, 11], though no attempt has been made to minimize the approximation factor. We give a 4-approximation algorithm for the general 1.5D terrain guarding problem, as well as a 2-approximation algorithm for the case with upwardlooking guards, i.e. when guards cannot see vertices that are below themselves. Contents iii Contents Abstract 11 Contents iii List of Figures Acknowledgements 1 Introduction 1.1 1.2 1.3 1.4 Problem Statement Motivation 1.2.1 Applications 1.2.2 Minimizing the Approximation Factor 1.2.3 Failure of Trivial Methods Related Work 1.3.1 The Art Gallery Problem 1.3.2 1.5-Dimensional Terrain Guarding 1.3.3 2.5-Dimensional Terrain Guarding 1.3.4 Watchtower Problems Organization 2 Preliminaries 2.1 2.2 Terminology and Notation Elementary Lemmas 3 Upward Looking Guards v vi 1 2 4 4 4 4 6 6 6 8 8 9 10 11 11 13 3.1 Introduction to the Upward Looking Case 3.2 The T G - U P Algorithm 14 3.3 3.4 Modifications for T G - T T - U p Time Complexity 16 16 4 The General Case 4.1 4.2 4.3 4.4 4.5 Introduction to the General Case Preliminaries Finding a Good Left Vertex The Terminal Case The Recursive Case 14 17 18 18 21 • 22 22 Contents 4.6 4.7 5 6 Modifications for T G - T T Time Complexity iv 23 23 D o m i n a t i o n of D i r e c t e d A c y c l i c G r a p h s . . . 27 5.1 5.2 28 28 Motivation NP-Hardness and Inapproximability Future Work 30 6.1 6.2 6.3 31 31 32 NP-Completeness Characterization of Terrain Graphs Reductions Between Restricted Visibility Problems Bibliography 33 List of Figures List of Figures 1.1 1.2 An example of a 1.5D terrain, d can see 6, c, and e but not a or / . A terrain for which the greedy method achieves a logarithmic approximation factor [4] 2 5 2.1 The shaded areas are terrain free and their union contains ad. . . 12 4.1 The order of some vertices related to an open vertex v 4.2 L'(v) and R(v) must be in the shaded region 4.3 The shaded region is terrain free, so every left vertex in [L(v), R'(v)] must see v 4.4 The nested interval [L(y) R(L(y))] can be handled independently with the help of a dominant outside vertex 19 20 21 t 23 Acknowledgements vi Acknowledgements I w o u l d like to t h a n k m y supervisor, W i l l E v a n s , for his guidance t h r o u g h o u t m y M a s t e r ' s degree a n d in particular for this project. I w o u l d also like to t h a n k m y second reader, D a v i d K i r k p a t r i c k , for his m a n y helpful c o m m e n t s . I a m very grateful to B o a z B e n - M o s h e for t a k i n g the t i m e to assist m e w i t h this p r o b l e m . I w o u l d like to t h a n k all of m y colleagues at U B C , especially the students a n d faculty of the B E T A lab. Finally, I w o u l d like to t h a n k M e l i n d a for all of her love and support. Chapter 1. Introduction Chapter 1 Introduction 1 Chapter 1. Introduction 2 1.1 Problem Statement In the 1.5-dimensional terrain guarding problem we are given as input a terrain T that is an x-monotone polygonal chain. A n x-monotone polygonal chain is a polygonal chain that intersects any vertical line at most once. It can be thought of as an array of n vertices in 2-dimensional space sorted in ascending order of ^-coordinate, where edges 'connect the dots' from left to right. Note that the x-monotonicity requires x-coordinates to be distinct. Figure 1.1: A n example of a 1.5D terrain, d can see b, c, and e but not a or / . We say that a point on the terrain sees another point on the terrain if there is a line of sight between them, i.e. the line segment connecting them is never strictly below T . A guard is simply a point on the terrain that we add to a 'guarding set'. Given a terrain T , we are asked for the smallest possible guarding set, i.e. the smallest set G of points on T such that every point on T is seen by some point in G. Along with the terrain T , we are given two (possibly infinite) subsets of the points on T : S Q , the set of points on which we are allowed to place guards (i.e. the set of points that are allowed to be in our guarding set), and ST, the target set of points that our guarding set must see. W i t h these sets in mind, we can be slightly more formal and say that the problem is to find the smallest subset G of SG such that every point in ST is seen by some g € G. For a terrain T , we use V ( T ) to denote the vertex set of T . There are two different versions of this terrain guarding problem that are natural to consider: 1. T G - V V : S 2. T G - T T : S = V ( T ) and S C G = T and S T T = V(T). = T. Chapter 1. Introduction In this be placed of as the simply as 3 p a p e r o u r m a i n f o c u s is t h e p r o b l e m T G - V V i n w h i c h g u a r d s m u s t o n vertices a n d only vertices need to be guarded; this c a n be thought discrete version of t h e p r o b l e m . W e will often refer to this p r o b l e m TG. B e n - M o s h e et al. [5] p o i n t o u t a r e d u c t i o n f r o m T G - T T t o T G - V V ( s e e S e c t i o n 1.3.2 f o r d e t a i l s ) . T h e a l g o r i t h m s w e p r e s e n t a c t u a l l y w o r k f o r b o t h v e r s i o n s of the problem, though m i n o r modifications are required to apply t h e m to T G TT. Chapter 1. Introduction 1.2 4 Motivation 1.2.1. Applications N a t u r a l l y , t h e m o t i v a t i o n f o r 1.5D t e r r a i n g u a r d i n g c o m e s f r o m g u a r d i n g o r c o v e r i n g t e r r a i n . T h e 1.5D c a s e a p p e a r s , f o r e x a m p l e , w h e n g u a r d i n g o r c o v e r i n g a road, perhaps w i t h security cameras or street lights. T h e 2.5D c a s e h a s m o r e p o w e r f u l a p p l i c a t i o n s , m o s t n o t a b l y f o r p r o v i d i n g a w i r e l e s s c o m m u n i c a t i o n n e t w o r k t h a t c o v e r s a g i v e n r e g i o n . Its p r o v e n i n tractibility and inapproximability, however, motivate us to look towards the 1.5D c a s e f o r i n s i g h t . I t i s a l s o a p p l i c a b l e , f o r e x a m p l e , i f w e o n l y n e e d t o c o v e r the p a t h between two points o n apolyhedral terrain. I thas been pointed out [5] t h a t t h e 1.5D t e r r a i n g u a r d i n g p r o b l e m c a n b e u t i l i z e d i n h e u r i s t i c m e t h o d s f o r t h e 2.5D c a s e . 1.2.2 Minimizing the Approximation Factor T h e r e c e n t r e s u l t s o f B e n - M o s h e et al. [5] a n d C l a r k s o n a n d V a r a d a r a j a n [11] s h o w e d that constant-factor a p p r o x i m a t i o n algorithms exist for T G . Efforts to design a n exact p o l y n o m i a l - t i m e a l g o r i t h m for T G have b e e n unsuccessful a n d it is v e r y p o s s i b l e t h a t n o s u c h a l g o r i t h m e x i s t s . If T G is N P - h a r d , t h e n t h e b e s t algorithm running in polynomial time will be the approximation algorithm with t h e l o w e s t a p p r o x i m a t i o n f a c t o r . F o r t h i s r e a s o n t h e r e is s i g n i f i c a n t m o t i v a t i o n to m i n i m i z e the approximation factor. 1.2.3 Failure of Trivial Methods T h e g r e e d y a l g o r i t h m f o r SET COVER, w h i c h a c h i e v e s t h e o p t i m a l a p p r o x i m a t i o n f a c t o r o f 0 ( l o g n), r e p e a t e d l y p i c k s t h e s e t t h a t c o n t a i n s t h e m o s t u n c o v e r e d elements. Similarly, the n a t u r a l g r e e d y a l g o r i t h m for terrain g u a r d i n g repeate d l y p i c k s t h e g u a r d t h a t sees t h e m o s t u n g u a r d e d vertices. I t is n o t a t a l l obvious that this m e t h o d would not achieve a constant approximation factor. H o w e v e r , B e n - M o s h e [4] p r o v i d e s t h e f o l l o w i n g e x a m p l e o n w h i c h t h e g r e e d y algorithm achieves alogarithmic approximation factor. O b s e r v e t h e t e r r a i n i n F i g u r e 1.2. T h e r e a r e O ( l o g n ) ' b o w l s ' . E a c h b o w l c o n t a i n s 3t i m e s as m a n y vertices as t h e b o w l to its right. H a l f of the vertices of e a c h b o w l a r e s e e n b y a a n d t h e o t h e r h a l f a r e s e e n b y b. T h e m i n i m u m g u a r d i n g s e t f o r t h e t e r r a i n i s {a,b}, b u t t h e g r e e d y a l g o r i t h m w i l l p i c k t h e c i r c l e d v e r t i c e s f r o m left to right to achieve a n a p p r o x i m a t i o n factor of O ( l o g n ) . There example, guarded gorithms are other natural greedy-like algorithms that one might consider. one could repeatedly pick the guard that maximizes the leftmost v e r t e x or the lowest u n g u a r d e d vertex. Terrains exist for these that prove they do not achieve constant approximation factors. For unalThe Chapter 1. Introduction 5 Figure 1.2: A terrain for which the greedy method achieves a logarithmic approximation factor [4]. apparent absence of simple algorithms that achieve constant approximation factors motivates us to consider more sophisticated techniques. Chapter 1. Introduction 1.3 1.3.1 6 Related Work The Art Gallery Problem T h e 1.5D terrain guarding problem is similar to a well-studied polygon guarding problem k n o w n as the art gallery problem. T h i s problem, posed by V i c t o r K l e e i n 1973, asks for the m i n i m u m number of security cameras (that can rotate to obtain a full field of vision) required to guard a given art gallery. T h e art gallery is represented by a simple polygon and cameras are points inside the polygon. A camera guards a point if the line segment between t h e m is contained w i t h i n the polygon. T h e size n of a problem instance is the number of vertices of the polygon. C h v a t a l ' s Art Gallery Theorem [10] states that |_§J cameras are always sufficient and sometimes necessary for guarding a polygon. K o o s h e s h and M o r e t [23] give a linear-time a l g o r i t h m for guarding a polygon w i t h |_§J cameras that is based on 3-colouring the triangulated polygon. F i n d i n g the m i n i m u m number of cameras required to guard a given polygon is N P - h a r d , as proven by A g g a r w a l [2]. T h e variation of the art gallery problem i n w h i c h cameras must be placed on the perimeter of the polygon is more closely related to 1.5D terrain guarding. L^J cameras are still sufficient and sometimes necessary, and K o o s h e s h and M o r e t ' s a l g o r i t h m works i n this variation since it actually places cameras on vertices. T h i s variation is still N P - c o m p l e t e as proven by Lee and L i n [24]. Eidenbenz et al. [17] prove that the art gallery problem is A P X - c o m p l e t e , regardless of restrictions on guard placement. T h i s means that there is some positive constant 5 such t h a t no polynomial-time a l g o r i t h m w i t h an a p p r o x i m a t i o n factor less t h a n 1 + S exists. In other words, the problem does not admit a polynomial-time a p p r o x i m a t i o n scheme unless P = N P . T h e y provide an even stronger result i n the case of polygons w i t h holes: no polynomial-time algorithm can have a sub-logarithmic a p p r o x i m a t i o n factor. 1.3.2 1.5-Dimensional Terrain Guarding W h e n guarding a 1.5D terrain it is easy to see that [ f J guards are sufficient (place a guard at every other vertex) and sometimes necessary (e.g. i f every vertex is on the upper hull of the terrain). If o n l y the vertices of the terrain need to be guarded this b o u n d drops to E v e r y instance of T G is an instance of S E T COVER, but we know that S E T COVER is N P - c o m p l e t e (see, e.g., [20]) and no sub-logarithmic a p p r o x i m a t i o n factor can be obtained unless N P C D T I M E ( n ) [19]. In general it is not p a r t i c u l a r l y difficult to modify a T G - V V a l g o r i t h m to solve instances of T G - T T , though this often involves some p o l y n o m i a l increase i n time complexity. l o g l o g n Chapter 1. Introduction 7 It is u n k n o w n whether or not T G is N P - h a r d . In 1995 C h e n et al. [9] proposed a n N P - h a r d n e s s proof obtainable v i a a modification of Lee and L i n ' s proof [24]. However, the proof, whose details were omitted, was never completed successfully. Since then, attempts to find a p o l y n o m i a l - t i m e a l g o r i t h m for T G and attempts to prove that it is N P - h a r d have b o t h been unsuccessful. T h e first constant-factor a p p r o x i m a t i o n a l g o r i t h m for the 1.5D terrain guarding problem was given by B e n - M o s h e et al. [5]. T h e i r a l g o r i t h m works by first placing guards to divide the terrain into independent s u b t e r r a i n s . E a c h subterrain has the property that it does not require internal guards, i.e. every unguarded vertex can be seen from outside the s u b t e r r a i n . F o r each such subterrain that is not completely guarded they then proceed w i t h steps that either reduce the s u b t e r r a i n or split it into multiple independent s u b t e r r a i n S v T h e y made no attempt to m i n i m i z e their algorithm's a p p r o x i m a t i o n factor; as such it is very large (at least 48). It could be brought d o w n possibly as low as 6 w i t h some minor modifications and careful accounting, but due to the inevitable cost incurred by repeatedly d i v i d i n g the terrain it does not seem that it could be brought any lower t h a n 6. O u r approach differs from that of B e n - M o s h e et al. i n that ours is completely iterative. B y avoiding a divide and conquer approach we are able to get the a p p r o x i m a t i o n factor as low as 4. W e need to work differently t h a n they do their iterative steps since we cannot depend on the desirable properties that their d i v i s i o n offers. B e n - M o s h e et al. also give a reduction from T G - T T to T G - V V . T h e y show that a quadratic number of extra vertices can be added i n the middle of any terrain's edges to create a terrain i n w h i c h any set of vertices that guards every vertex must guard the entire terrain. T h e y then show that any edge guard can be replaced by two vertex guards, essentially saying that a c-approximation a l g o r i t h m for T G - V V can be applied to one of these augmented terrains to give a 2c-approximation a l g o r i t h m for T G - T T . A n o t h e r constant-factor a p p r o x i m a t i o n a l g o r i t h m is given by C l a r k s o n and V a r a d a r a j a n [11]. Consider a p a r t i t i o n of a 1.5D terrain into m a x i m a l intervals such that, for any two points p and p' i n a given interval, the leftmost point that sees p and the leftmost point that sees p' are the same. If we label each interval w i t h the leftmost point that sees it and read the labels from leftmost interval to rightmost interval, C l a r k s o n and V a r a d a r a j a n note t h a t we end up w i t h an (n, 2) Davenport-Schinzel sequence [25]. Such a sequence must have length at most 2n. T h i s characterization of the lack of complexity i n 1.5D terrains allows t h e m to efficiently find appropriate e-nets [21] for instances of T G . T h e y then a p p l y the S E T COVER method of B r o n n i m a n n and G o o d r i c h [8] to solve the problem using these e-nets. T h e end result is a constant-factor a p p r o x i m a t i o n a l g o r i t h m that runs i n p o l y n o m i a l time. Chapter 1. Introduction 8 The 1.5D terrain guarding problem becomes easy if, instead of being placed on the terrain, all guards 'float' above the terrain at a fixed altitude that is above the highest vertex. Eidenbenz [14] gives a linear-time algorithm for finding an optimal set of guards in this case. The problem also becomes easy if guards can only look rightwards. Chen et al. [9] give a linear-time algorithm for this case. 1.3.3 2.5-Dimensional Terrain Guarding A 2.5D terrain is a polyhedral surface that intersects every vertical line at most once and whose projection onto the x, y-plane is a simple polygon with no holes. The 2.5D Terrain Guarding Problem is therefore a natural extension of the 1.5D problem to the next dimension. Bose et al. [7] prove that |_T|J vertex guards are sufficient and sometimes necessary. If guards can be placed on edges then |_f J guards are sufficient [-18] and [ " g J are sometimes necessary. Efficient algorithms for achieving these bounds for vertex guards and edge guards are given by Bose et al. [6]. 4 4 Finding a minimum number of guards for a 2.5D terrain is NP-complete and Eidenbenz shows that it cannot be approximated within a sub-logarithmic factor unless N P C D T I M E ( n s . s ) [15]. Eidenbenz et al. show that the problem is also NP-complete and equally inapproximable when guards 'float' at a given altitude that is higher than the highest point in the terrain [16] (recall that this can be solved in linear time for 1.5D terrains). lo 1.3.4 Io n Watchtower Problems A fc-watchtower problem provides a terrain and an integer k and asks for the minimum height h such that k guards can be placed at height h above the terrain (not above "sea level") to guard the terrain. The discrete version of the problem is that in which the guards must be above vertices of the terrain. Most of the best results for these problems when k = 2 are due to Agarwal et al. [1]. For 1.5D terrains they present polynomial-time algorithms for both the discrete and continuous versions of the 2-watchtower problem. For 2.5D terrains they present a polynomial-time algorithm for the discrete 2-watchtower problem. Zhu gives an O(nlogn) algorithm for the 1-watchtower problem on 2.5D terrains. ' Chapter 1. Introduction 1.4 9 Organization T h e rest o f t h e p a p e r is o r g a n i z e d as f o l l o w s . I nC h a p t e r 2 w e i n t r o d u c e notation a n d some small but fundamental lemmas. In Chapter 3 we give our 2 - a p p r o x i m a t i o n a l g o r i t h m for the u p w a r d - l o o k i n g case. In C h a p t e r 4 w e give o u r 4 - a p p r o x i m a t i o n a l g o r i t h m for t h e g e n e r a l case. I nC h a p t e r 5 w e p r o v e N P - h a r d n e s s a n d i n a p p r o x i m a b i l i t y o f DOMINATING SET o n d i r e c t e d a c y c l i c g r a p h s to s h o w t h a t our 2 - a p p r o x i m a t i o n a l g o r i t h m for the u p w a r d - l o o k i n g case is significant. In C h a p t e r 6 w e d i s c u s s o p e n p r o b l e m s a n d s u g g e s t d i r e c t i o n s for f u t u r e w o r k r e g a r d i n g 1.5D t e r r a i n g u a r d i n g . Chapter 2. Preliminaries Chapter 2 Preliminaries 10 Chapter 2. 2.1 Preliminaries 11 Terminology and Notation A n i n s t a n c e o f t h e 1 . 5 D terrain g u a r d i n g p r o b l e m is s i m p l y a n x - m o n o t o n e c h a i n T. T h i s c h a i n i s a s e t o f n v e r t i c e s , {vi,..., v }, s u c h t h a t is t o t h e right o f Vj i f a n d o n l y i f i < j. W e c o m p a r e v e r t i c e s u s i n g t h e i r i n d i c e s ; t h i s m a k e s i t m u c h easier to describe relationships between t h e m . F o r example, x < y m e a n s t h a t x i s l e f t o f y, a n d f o r a s e t S o f v e r t i c e s , m a x ( 5 ) i s t h e r i g h t m o s t v e r t e x i n S. W h e n r e f e r r i n g t o p o i n t s o n t h e t e r r a i n t h a t a r e n o t v e r t i c e s w e u s e t h e c o m p a r a t o r s i n as i m i l a r m a n n e r . n F o r a v e r t e x x w e u s e L(x) t o d e n o t e t h e l e f t m o s t p o i n t w h e r e w e c a n p l a c e a g u a r d t h a t s e e s x a n d R(x) t o d e n o t e t h e r i g h t m o s t p o i n t w h e r e w e c a n p l a c e a g u a r d t h a t s e e s x . I t i s n o t d i f f i c u l t t o s e e t h a t L(x) a n d R(x) w i l l a l w a y s b e vertices i n t h e g e n e r a l case, w h e t h e r x is av e r t e x o r n o t (this is n o t necessarily t r u e i n t h e u p w a r d - l o o k i n g c a s e , a s w e e x p l a i n i n S e c t i o n 3 . 3 ) . W e u s e Tr,(x) t o d e n o t e t h e t e r r a i n r e s t r i c t e d t o t h e i n t e r v a l [ i > i , x ] a n d u s e TR(X) to denote the t e r r a i n r e s t r i c t e d t o [ x , v \. W e u s e CHi(x) t o d e n o t e t h e c o n v e x h u l l o f 7 L ( X ) n and use C H R ( X ) for that of T R ( X ) . If a v e r t e x x sees e v e r y u n g u a r d e d v e r t e x t h a t t h a t x dominates y. W e c a n a l s o s a y t h a t a s e t S u n g u a r d e d v e r t e x seen b y x is also seen b y s o m e dominates y with respect to a certain region of v e r t e x i n t h a t region t h a t y sees. another vertex y sees w e s a y d o m i n a t e s av e r t e x x if e v e r y v e r t e x i n S. W e s a y t h a t x T if x sees e v e r y u n g u a r d e d W e consider am i n i m u m guarding set GOPT for the terrain T . W e assume there is s o m e m a p p i n g g o f vertices of T t o g u a r d s i n GOPT s u c h that, for a v e r t e x v, g(v) i s a g u a r d i n G O P T t h a t s e e s v. W e s a y t h a t g(v) i s t h e g u a r d responsible for g. g i s s u r j e c t i v e b u t n e v e r i n j e c t i v e ( s i n c e | G O P T | < n); w e use it to simplify t h e explanation of o u r accounting scheme. O u r algorithms a r e i t e r a t i v e ; i n e a c h i t e r a t i o n t h e y f i n d s o m e a p p r o p r i a t e u n g u a r d e d v e r t e x v. T h e y t h e n p l a c e a c o n s t a n t n u m b e r o f g u a r d s t h a t t o g e t h e r d o m i n a t e g(v) a n d c h a r g e t h e m t o g{v). R e p e a t e d l y d o i n g t h i s g i v e s u s c o n s t a n t - f a c t o r a p p r o x i m a t i o n algorithms. 2.2 Elementary Lemmas Here w e state a n d prove several small b u t fundamental l e m m a s that w e will use i n t h e rest of t h e paper. T h e y apply to b o t h t h e general case a n d t h e u p w a r d - l o o k i n g case. T h e s e l e m m a s a n d corollaries c a n b e u s e d w i t h left a n d right i n t e r c h a n g e d ; this is stated explicitly for C o r o l l a r y 1 as a n e x a m p l e b u t is not stated for the others. L e m m a 1. ( O r d e r C l a i m ) [5, 9] For vertices a, b, c , d such that a < b < c < d, if a sees c and b sees d then a sees d. Chapter 2. 12 Preliminaries Proof. T h i s b e c o m e s q u i t e c l e a r w i t h t h e h e l p o f a d i a g r a m ( s e e F i g u r e 2 . 1 ) . I t i s t r i v i a l l y t r u e i f a = b o r c = d; o t h e r w i s e w e k n o w t h a t a < b < c < d. I n t h i s c a s e b c a n n o t b e a b o v e ac a n d c c a n n o t b e a b o v e bd ( o t h e r w i s e t h e f a c t t h a t a sees c a n d bsees d w o u l d b e violated). T h i s m e a n s that the t w o line s e g m e n t s m u s t c r o s s ; w e c a l l t h e i r i n t e r s e c t i o n p o i n t p. C o n s i d e r i n g t h e t r i a n g l e f o r m e d b y a , _ p , a n d d, w e n o t e t h a t n o p o i n t o n t h e t e r r a i n c a n b e a b o v e t h e l o w e r h u l l a n d ad i s t h e u p p e r h u l l . T h e r e f o r e n o p o i n t o n t h e t e r r a i n c a n b e a b o v e ad. F o r t h e u p w a r d - l o o k i n g case it is n o t difficult to see t h a t if a sees c a n d b sees d then om u s t be below d so the l e m m a holds. • d F i g u r e 2 . 1 : T h e s h a d e d a r e a s a r e t e r r a i n f r e e a n d t h e i r u n i o n c o n t a i n s ad. C o r o l l a r y 1. For vertices v,u,x with v < u < x, if v and u can both be seen from TR(X) then R(u) < R(v). C o r o l l a r y 1. ( S y m m e t r i c V e r s i o n ) For vertices v,u,x with x < u < v, if v and u can both be seen from TL(X) then L(v) < L(u). L e m m a 2. For an interval [ a , 6] where a sees b, any guard in (a, b) is dominated with regard to Tji(b) by a. Proof. L e t v b e a g u a r d i n ( a , 6) a n d l e t u b e s o m e v e r t e x i n TJJ(6) s e e n b y u. I f u = b w e k n o w t h a t a s e e s u. O t h e r w i s e t h e o r d e r c l a i m , a p p l i e d t o o , v, 6, u, s t a t e s t h a t a s e e s u. • C o r o l l a r y 2. For vertices x and y such that x < y < R(x), we know that R(y) < R(x). Chapter 3. Upward Looking Guards Chapter 3 U p w a r d Looking Guards 13 Chapter 3. Upward Looking Guards 3.1 14 Introduction to the Upward Looking Case We consider a restricted version of the 1.5-dimensional terrain guarding problem in which guards cannot see below themselves. That is, a guard at x can see a point y if and only if the line segment xy does not pass under the terrain and y is not below x. With this restriction we refer, to the problem as the upward looking 1.5-dimensional terrain guarding problem. We can define T G - V V - T J p = T G - U P and T G - T T - U p , whose definitions should be obvious from Section 1.1. In Section 3.2 we give a 2-approximation algorithm for T G - U P . In Section 3.3 we show how the algorithm can, with minor modifications, be applied to T G T T - U P to obtain the same approximation factor. In Section 3.4 we show that our algorithm runs in quadratic time. The restriction that a guard cannot see points below it has several .effects on the visibility graph of the terrain. First of all, since visibility between two vertices is no longer symmetric, the visibility graph is a directed graph. Secondly, if we assume that the vertices are in general position (specifically that no two are at the same height), the visibility graph is acyclic since a vertex on the terrain can only see vertices above it and can only be seen by vertices below it. With such an assumption the problem T G - U P is therefore equivalent to D O M I N A T I N G S E T (see, e.g., [20]) on a restricted class of directed acyclic graphs. We refer to the D O M I N A T I N G S E T problem on general D A G s as D O M - D A G . In Chapter 5 we show via a simple reduction from S E T C O V E R that D O M D A G is NP-hard. We also show that any polytime approximation algorithm for D O M - D A G must have at least a logarithmic approximation factor unless N P C D T I M E ( n s s ) . Since, with the assumption of general position, T G U P is a restricted case of D O M - D A G , this inapproximability increases the significance of a constant factor approximation algorithm for T G - U p . We should note that our algorithm does not require vertices to be in general position. l o 3.2 l o n The T G - U P Algorithm Our algorithm starts with an empty set G of guards and repeatedly considers the lowest vertex p on the terrain that is not seen by G. We will place up to 3 guards to dominate g(p) and charge them to g(p). Our algorithm is based on the following lemma: Lemma 3 . If p is the lowest unguarded vertex then {L(p),p, R(p)} dominates any vertex that sees p. Proof. Any vertex that sees p must be in \L(p), R(p)]. Using Lemma 2 we can see that {L(p),p} dominates any vertex in [L(p),p] with regard to T R ( P ) and {p, R(p)} dominates any vertex in [p, R(p)} with regard to T L ( P ) . p must be the highest point in [L(p),R(p)], so there are no unguarded points in [L(p),R(p)\ other than p. What remains to be shown is that {L(p),p, R(p)} dominates Chapter 3. Upward Looking Guards 15 any vertex in (L(p),p) with regard to TL(L(P)) and dominates any vertex in (p, R{p)) with regard to T (R{ )). Let v be a vertex in (L(p),p). If there is an unguarded vertex u to the left of L(p) that is seen by v then the order claim tells us the line segment between p and u is uninterrupted by the terrain. This means that if u does not see p then p must see u. u cannot see p because this would contradict the definition of L(p), so p must see u. This proves our claim for the left side; the right side can be proven symmetrically. • R P Our algorithm is very simple. Once we have found the lowest unguarded vertex p, we simply place guards at L(p), p, and R(p) and charge them to g(p). Lemma 3 tells us that any vertex that sees p must be dominated by {L(p),p, R(p)}. These vertices may or may not be distinct so in actual fact we have placed 1, 2, or 3 guards. At first it seems that this algorithm can have an approximation factor as high as 3, but with a bit more analysis we can prove an upper bound less than 2. Let P be the set containing the lowest unguarded point at each iteration of our algorithm (i.e. the points p for which we placed guards at L(p), p, and R(p)). \P\ < \GOPT\- Let p be some vertex in P. We know that L(p) <p< R(p), but we can be more specific. We consider three cases based on the vertices related to p: 1. L(p)=p 2. L(p) =p< 3. L ( ) <p< P = R(p) R(p) or L(p) <p = R(p) R(p). Clearly our algorithm places 1 guard in the first case, 2 in the second, and 3 in the third. We know that \G\ < 3|P|, but we can also say that if Case 1 occurs at least as often as Case 3 then \G\ < 2\P\. Case 1 will occur if and only if p is a local minimum. Case 3 will occur if and only if p is an intermediate maximum, where we define an intermediate maximum as a local maximum that is neither the leftmost nor the rightmost vertex in the terrain. Any other situation falls into Case 2. Now we show that Case 1 occurs more often than Case 3, bringing the approximation factor below 2. The number of local minima is one more than the number of intermediate maxima, since there is exactly one local minimum between any two intermediate maxima, as well as one to the left of the leftmost and one to the right of the rightmost. Also, every local minimum is in P since a local minimum can only be guarded by itself. Therefore Case 1 must occur strictly more often than Case 3, so our algorithm's approximation factor is below 2. It is not difficult to come up with sample terrains in which our algorithm achieves an approximation factor as bad as 2 — 0(l/n), and that is the upper bound. 16 Chapter 3. Upward Looking Guards Pseudocode for our algorithm is as follows: Algorithm 1 TG-UP(T) while unguarded points remain do let p be the lowest unguarded vertex; add p, L(p), and R(p) to G; end while 3.3 Modifications for T G - T T - U P To make the T G - U P algorithm work for T G - T T - U P we need to consider guarding edges instead of guarding vertices. The following two observations are crucial. First of all, if p is the lowest unguarded point on the terrain, any guard that sees p must see every unguarded point on the same edge as p. Secondly, the lowest unguarded point on the terrain will always be the lowest point on some edge. These observations together mean that if a guard sees part of an edge but not all of it then, for our purposes, it may as well see none of that edge. We are therefore only concerned about whether a guard sees all of an edge or not. Consider an edge (a;, y) where, without loss of generality, x is below y. A point sees all of (x, y) if and only if it sees x and is not below the line passing through x and y. The leftmost point that sees this edge will either be L(x) if it not below the line passing through x and y and will be x otherwise. The rightmost point that sees this edge will be x. It is therefore clear that there are no more than 2n potential guard locations that we need to consider. 3.4 Time Complexity For T G - V V - U P we first compute the visibility graph of the terrain. As BenMoshe points out [3] this can be done in 0(n ) time. From here on it is simple to show that the algorithm runs in quadratic time. Our algorithm goes through 0{n) iterations. In each iteration we find the lowest unguarded vertex p, find L(p) and R(p), place guards at these vertices, then mark all vertices seen by our new guards as guarded. All of the work in an iteration can clearly be done in linear time. Our algorithm for T G - U P therefore runs in 0(n ) time. 2 2 For T G - T T - U P we do the same. The only difference is that the visibility graph will be a bipartite graph with points on the terrain seeing edges (see Section 3.3). The size of the graph will still be 0(n ) and can be constructed in 0(n ) time. Our algorithm therefore runs in 0(n ) time for T G - T T - U P . 2 2 2 Chapter 4. The General Case Chapter 4 The General Case 17 Chapter 4. The General Case 4.1 18 Introduction to the General Case Our algorithm for the general case works by repeatedly finding an unguarded vertex u and a set S of up to 4 vertices such that S must dominate g(u). By doing so, we achieve an approximation factor of 4 . Our algorithm does not require any knowledge of previously placed guards other than which vertices are unguarded. GUARD RIGHT is a recursive subroutine that does most of the algorithm's work. GUARDRIGHT takes two vertices x and c as parameters and it places guards appropriately until every vertex in \x,R(x)) is guarded. The preconditions are that x is unguarded, x is not on CH(T), and every unguarded vertex in \L(R(x)),x) is seen by c. We note that if x is not on CH(T) then x ^ R{x), which is a fact we will need later. The other significant consequences of x not being on the convex hull are that L(R(x)) < L(x) < x and, due to Corollary 2, no vertex outside of [L(R(x)), R(x)} can see an unguarded vertex y in [a;, R(x)). In the outermost loop of our algorithm we consider the two leftmost unguarded vertices p and q with p < q. In the case where p is not on CH(T) we call GUARDRlGHT(p,p) and the preconditions are satisfied. If p is on C H ( T ) but q is not we call G U A R D R l G H T ( g , p) and the preconditions are satisfied. If both p and q are on the convex hull we can simply place a guard at R(p) and this will dominate g(p). Clearly if there is only one unguarded vertex p remaining we can just place a guard on p to dominate g(p). We say that an interval I is independent if no unguarded interior vertex in I can be seen from outside I. For a call to GUARDRlGHT(a;, c) we say that the interval [L(R(x)), R(x)\ is pseudo-independent since we could make it independent with the placement of a single guard (at c in this case). GUARD RIGHT will either find an unguarded vertex u G [x, R(x)) for which g(u) can be dominated by 4 guards or will find a pseudo-independent subinterval of [a:, R(x)} that it can recurse on. 4.2 Preliminaries Here we introduce some lemmas that hold in the general case. Lemma 4. (Lip Lemma) For an interval, [a, b] where a sees b, if there are no unguarded vertices in (a, b) then {a, 6} dominates any guard in [a, b). Proof. This follows easily from Lemma 2 since a sees b and b sees o. • Lemma 5. For a vertex x, any guard v in TL{X) is dominated with regard to TR(X) by a guard in C H ^ ( x ) . One such dominating guard is the rightmost vertex in Ti(v) D C H L ( X ) . Chapter 4. The General Case 19 Proof. Let u be the rightmost vertex in TL(V) n C H L ( X ) . If v is on C H L ( X ) then v = u and the lemma clearly holds. Otherwise let w be the first vertex on CHL(X) to the right of u. Now u dominates v with regard to TR(X) C TR(W) by Lemma 2. • C o r o l l a r y 3 . For vertices x and v, if L(v) <x<v then L(v) is on C H L ( X ) . At this point we introduce some new terminology and notation that depends on the parameters of GUARDRIGHT. It should be emphasized that this notation applies only to this particular call to GUARDRIGHT. We say that a left vertex is a vertex in CH([L(R(x)),x\) — {x}. A right vertex is a vertex in \x,R(x)]. A n open vertex is an unguarded vertex in [x, R{x)) that can be seen by a left vertex. A closed vertex is an unguarded vertex in [x, R{x)) that cannot be seen by a left vertex. For an open vertex v we provide additional notation: R'(v) is the rightmost left vertex that sees v and L'(v) is the leftmost right vertex that sees v. R'(v) and L'(v) are undefined unless v is an open vertex. L e m m a 6. (a) If v is a closed vertex then L(R(x)) < x < L(v) <v< R(v) < R(x). (b) If v is an open vertex then L(R(x)) < L(v) < R'(v) < x < L'(v) < v < R(v) < R{x). Proof, (a) L(R(x)) < x since R(x) sees x. x < L(v) otherwise v would be an open vertex. L(v) < v by definition. R(v) < R(x) by Corollary 2. (b) L(R(x)) < L(v) by Corollary 1 if x < v and by the Order Claim otherwise. L(v) < R'(v) <x< L'(v) <vby definition. R(v) < R(x) by Corollary 2. • L(R(x)) L(V)\ ; V R'(V)V:X R(x) ,/»R(v) L'(v) X Figure 4.1: The order of some vertices related to an open vertex v. Chapter 4. The General Case 20 Lemma 7. For an open vertex v, L'(v) sees R(v). Proof. I f v = x t h i s i s c l e a r l y t r u e s i n c e x = L'(x). O t h e r w i s e , i t i s e a s y t o s e e t h a t t h i s i s t r u e a s l o n g a s v i s n o t a b o v e t h e l i n e p a s s i n g t h r o u g h L'(v) a n d R(v). L'(v) c a n n o t b e b e l o w t h e l i n e p a s s i n g t h r o u g h x a n d v o t h e r w i s e v w o u l d b e s e e n b y a v e r t e x i n [x, L'(v)) w h i c h c o n t r a d i c t s t h e d e f i n i t i o n o f L'(v). S i m i l a r l y , R(v) c a n n o t b e b e l o w t h e l i n e p a s s i n g t h r o u g h v a n d R(v). I t s h o u l d n o w b e c l e a r t h a t v i s n o t a b o v e t h e l i n e p a s s i n g t h r o u g h L'(v) a n d R(v) ( s e e F i g u r e 4.2). T h e rest follows trivially. • ,Rjv) / / X*- F i g u r e 4 . 2 : L'(v) a n d R(v) m u s t b e i n t h e s h a d e d r e g i o n . Lemma 8. For an open vertex v the set of left vertices that see v is contiguous, i . e . every left vertex in [L(v), R'{v)} sees v. Proof. C o n s i d e r CH{[L{v), R'(v)}). T h i s i s a s u b s e t o f CH([L(R(x)),x}) {x} s i n c e L(v) a n d R'(v) a r e b o t h o n CH([L(R(x)),x]). S o w e c a n see t h a t CH([L(v), R'(v)]) i s a s e t o f l e f t v e r t i c e s a n d w e k n o w t h a t n o l e f t v e r t e x n o t i n t h e s e t c a n s e e v. N o w w e w i l l s h o w t h a t i f w i s a v e r t e x i n t h e s e t , w ^ L(v), w s e e s v, a n d u i s t h e f i r s t v e r t e x i n t h e s e t t o t h e l e f t o f w, t h e n u a l s o s e e s v. C o n s i d e r t h e l i n e p a s s i n g t h r o u g h v a n d w. u m u s t b e a b o v e t h i s l i n e s i n c e w L(v). S i n c e u a n d w are c o n s e c u t i v e p o i n t s o n t h e c o n v e x h u l l , w s e e s u. N o w w e c a n s e e t h a t uw a n d wv a r e l i n e s e g m e n t s t h a t d o n o t i n t e r f e r e w i t h t h e t e r r a i n , s o uv c a n n o t i n t e r f e r e w i t h t h e t e r r a i n s i n c e i t i s a b o v e m i ; a n d wv. T h e r e f o r e u s e e s v. I t i s e a s y t o e x t e n d t h i s i n t o a n i n d u c t i o n p r o o f f o r t h e lemma. • Lemma 9. For every vertex v in [L(R(x)),x) there is a left vertex u such that {c,u} dominates v. This guard u is the rightmost vertex in Tr,(v) D C H L ( X ) . Proof. then v TL(U). we can v. B y L e m m a 5 w e k n o w t h a t u d o m i n a t e s v w i t h r e g a r d t o TR(X). liu^v c a n n o t see a n y v e r t e x to t h e left of u so u d o m i n a t e s v w i t h r e g a r d to c c a n s e e e v e r y u n g u a r d e d v e r t e x i n [L(R(x)),x). S i n c e L(R(x)) < u, s e e t h a t T (u) U [L(R(x)), x) U T (x) = T. T h e r e f o r e { c , u} d o m i n a t e s • L R Chapter 4. The General Case 21 Figure 4.3: The shaded region is terrain free, so every left vertex in [L(v), R'{v)] must see v. Lemma 9 tells us that, as long as we place a guard at c when we place other guards, we needn't place any guard in [L(R(x)),x) unless it is on a left vertex. 4.3 Finding a Good Left Vertex The first thing we note is that there must be at least one open vertex in [x, R(x)), namely x. There may or may not be a closed vertex in [x,R(x)). We define b as the leftmost left vertex such that some open vertex v is seen by b but not by any left vertex to the right of b. In other words, b is the minimum R'(v) over all open vertices v. We define d as the leftmost open vertex for which R'(d) = b. Lemma 10. Every open vertex in (L'(d),R(x)) is seen by L(d). Proof. If d = x then the proof follows easily from the symmetric version of Corollary 1, so we will assume this is not the case. First we will prove that there are no open vertices in (L'(d),d). Assume for the sake of contradiction that there is an open vertex v in (L'(d),d). We can apply the order claim to R'(v),L'{d),v,d to see that R'(v) sees d. This tells us that R'(v) < R'(d), which violates the definition of d, so there cannot be any such vertex v. Now we show that L(d) sees every open vertex in (d, R(x)). Let u be an open vertex in (d, R(x)). We have L(u) < d < u so by the symmetric version of Corollary 1 we know that L(u) < L(d). By the definition of d we know that R'(d) < R'(u). Therefore L(d) G [L(u), R'(u)], so by Lemma 8 we know that L(d) sees u. • Lemma 11. Any guard in [L(R(x)),x) that sees d is dominated by {L(d),c}. Proof. Let v be a guard in [L(R(x)), x) that sees d. Since c sees every unguarded vertex in \L(R(x)),x) it suffices to prove that L(d) dominates v with regard to Chapter 4. The General Case 22 TR(X). L(d) < v, so by Lemma 2 L(d) dominates v with regard to Tfi(d). Now we show that no left vertex that sees d can see any open vertex to the left of d. It follows from the definition of b = R'(d) and from Lemma 8 that any open vertex seen from the left of R'(d) must be seen by R'(d). However, d is the leftmost open vertex seen by R'(d), so no open vertex to the left of d can be seen by R'(d). In other words, no open vertex to the left of d can be seen by a left vertex that sees d. This, along with Lemma 5, tells us that v cannot see any unguarded vertices in [x,d). Since v cannot see any closed vertices at all, this means that L(d) dominates v with regard to TR(X). V cannot see anything left of L(R(x)) except possibly if v = L(d), so {L(d),c} dominates v over the entire terrain. • Recall that, while searching for a suitable vertex u for which we can dominate g(u) with 4 guards, either we find one right away or we find some pseudoindependent pocket (i.e. a subinterval of [x,R(x))) that we can recurse upon. 4.4 The Terminal Case We first consider the case where there are no closed vertices in (L'(d), R(d)). We place guards at {c, L(d), L'(d), R(d)} and claim that these guards dominate any guard that sees d. Lemma 10 tells us that every open vertex in (L'(d), R(d)) is seen by L(d), and since there are no closed vertices in (L'(d),R(d)) there are no longer any unguarded vertices in (L'(d),R(d)). L'(d) sees R(d) by Lemma 7. Therefore, by Corollary 4, any guard in [L'(d), R(d)] is dominated by {L(d), L'(d), R(d), c}. By Lemma 11 any guard in [L(R(x)),x] that sees d is dominated by {L(d),L'(d),R(d),c}. Any guard that sees d must either be in [L(R(x)), x] or in [L'(d), R(d)}, so {L(d), L'(d), R(d), c} dominates any guard that can see d. 4.5 The Recursive Case If there are closed vertices in (L'(d),R(d)) our job is slightly more complicated and requires recursion (this is where we find our 'independent pocket'). We require another subroutine, G U A R D L E F T , that is like a mirror image of G U A R D R I G H T . For G U A R D L E F T ( : E ' , C ' ) the precondition on c' is flipped horizontally: every unguarded vertex in (x', R(L(x'))] must be seen by c'. Let y be the rightmost closed vertex (note that y is not necessarily in the interval (V(d), R(d)), but it must be in (L'(d), R(x))). We will show that the preconditions are satisfied if we call G U A R D L E F T ( ? / , L(d)). By Corollary 2 R(L(y)) < R(x) and by the definition of y any unguarded vertex in (y, R(x)) is an open vertex. Therefore by Lemma 10 every unguarded vertex in (y, R(L(y))) is seen by L(d). If R(L(y)) < R(x) then either R(L(y)) is already guarded or it is an open vertex and is seen by L(d). If R(L(y)) = R(x) then L(d) sees 23 Chapter 4. The General Case R(L(y)) s i n c e e v e r y v e r t e x i n CH([L(R(x)),x}) s e e s R(x). T h e r e f o r e e v e r y u n g u a r d e d v e r t e x i n (y, R(L(y))} i s s e e n b y L(d). W e k n o w y i s u n g u a r d e d a n d y € (x, R(x)) ( a n d i s t h e r e f o r e n o t o n CH(T)), s o t h e p r e c o n d i t i o n s a r e s a t i s f i e d . L(R(x)) R(x) ,,-;>R(L(y)) L(y)^T •> y x F i g u r e 4 . 4 : T h e n e s t e d i n t e r v a l [L(y), R(L(y))] c a n b e h a n d l e d with the help of a d o m i n a n t outside vertex. independently In this w a y w e c a n d o a sort o f recursive zig-zagging where each call t o GUARDRIGHT w i l l s p a w n a c a l l t o G U A R D L E F T a n d e a c h c a l l t o G U A R D L E F T w i l l s p a w n a c a l l t o GUARD RIGHT. I t i s n o t d i f f i c u l t t o s e e t h a t e v e n t u a l l y , a f t e r a t m o s t a l i n e a r n u m b e r o f t h e s e z i g - z a g g i n g s t e p s , w e w i l l f i n d a s u i t a b l e u. A t t h i s p o i n t w e c a n s i m p l y p l a c e o u r 4g u a r d s a n d , if w e n e e d t o , s t a r t ab r a n d n e w c a l l t o GUARDRIGHT. P s e u d o c o d e f o r GUARDRIGHT a n d t h e m a i n a l g o r i t h m GUARD t h a t c a l l s i t i s g i v e n a s A l g o r i t h m 3 a n d A l g o r i t h m 2 r e s p e c t i v e l y . 4.6 Modifications for T G - T T N o real modifications need to be m a d e to apply our T Galgorithm to T G - T T . H o w e v e r , w e n e e d t o k e e p t r a c k o fm o r e i n f o r m a t i o n i f w e w a n t o u r a l g o r i t h m t o r u n a s efficiently as p o s s i b l e . T h i s i sd i s c u s s e d i nS e c t i o n 4.7. 4.7 Time Complexity I t i s c l e a r t h a t a t m o s t 0(n) i n i t i a l c a l l s t o GUARDRIGHT c a n b e m a d e . F o r T G - V V i t i s a l s o e a s y t o s e e t h a t a n i n i t i a l c a l l t o GUARDRIGHT w i l l r e s u l t i n a Chapter 4. The General Case A l g o r i t h m 2 GUARD(T) while T is not completely guarded do let p be the leftmost unguarded vertex; if p is the only unguarded vertex then place a guard at p; charge the guard to g(p); else if p is not on CH(T) then GUARDRIGHT (p, p); else let q be the second leftmost unguarded vertex; if q is not on CH(T) then GUARDRIGHT(9,P); else place a guard at R(p); charge the guard to g(p); end if end if end while A l g o r i t h m 3 GUARD RIGHT(:E, c) • c sees every unguarded vertex in (L(R(x)),x) Require: • x is unguarded • xi CH(T) b <— mm{R'(v) : v is open}; d <— min{v : R'(v) = b}; if there is a closed vertex in (L'(d), R(d)) t h e n let y be the rightmost such closed vertex; GUARDLEFT(I/, L(d)); else place guards at c, L(d), L'(d), and R(d); charge the guards to g(d)\ end if 24 Chapter 4. The General Case n u m b e r o f g u a r d s b e i n g p l a c e d i n 0(n ) t i m e . W e c a n t h e r e f o r e g i v e a n b o u n d o f 0(n ) f o r t h e r u n n i n g t i m e o f T G - V V . 2 25 upper 3 I f w e w a n t T G - V V t o b e m o r e e f f i c i e n t , w e c a n m a k e GUARDRIGHT(X, C) c o n t i n u e p l a c i n g g u a r d s u n t i l [ x , R(x)) h a s b e e n c o m p l e t e l y g u a r d e d . T h i s c h a n g e s t h i n g s slightly; o nag i v e n i t e r a t i o n , x i s n o t necessarily u n g u a r d e d so t h e r e i s n o t n e c e s s a r i l y a n o p e n vertex. I f t h e r e is n o o p e n v e r t e x , h o w e v e r , w e c a n j u s t r e c u r s e i m m e d i a t e l y b y c a l l i n g GUARDRlGHT(y, c) s o t h i s i s n o t a p r o b l e m . T o i n c r e a s e e f f i c i e n c y , w e c a n s o r t t h e o p e n v e r t i c e s v b y R'(v) ( b r e a k i n g t i e s u s i n g t h e x - c o o r d i n a t e s of o p e n vertices) t ofind a n a p p r o p r i a t e b a n d d faster i n e a c h iteration. A c a l l t o GUARDRIGHT(X, c ) , i g n o r i n g a l l r e c u r s i v e c a l l s t h a t i t s p a w n s , c a n n o w r u n i n 0(n + m l o g m ) t i m e , w h e r e m i s t h e n u m b e r o f o p e n v e r t i c e s i n [x,R(x)). I t i s e a s y t o s e e t h a t t h e ' n ' t e r m s , a d d e d u p o v e r t h e e n t i r e c o u r s e o f t h e a l g o r i t h m , w i l l c o s t 0(n ) t i m e s i n c e t h e r e w i l l b e a t m o s t 0(n) c a l l s t o GUARDRIGHT. A n y v e r t e x w i l l b e a n o p e n v e r t e x f o r a t m o s t o n e c a l l t o GUARDRIGHT, SO t h e s u m o f a l l m l o g m f a c t o r s e n c o u n t e r e d w i l l a c t u a l l y b e bounded b y O ( n l o g n ) . All other overhead incurred b ythe algorithm can b e d e a l t w i t h i n 0[n ) t i m e , s o t h e r u n n i n g t i m e o f T G - V V i s b o u n d e d b y 0(n ). P s e u d o c o d e f o r t h e e f f i c i e n t b u t l e s s e l e g a n t v e r s i o n o f GUARDRIGHT i s g i v e n a s A l g o r i t h m 4. 2 2 2 W h e n dealing with T G - T T the only real problem isfinding band d a t each i t e r a t i o n o f a c a l l t o GUARDRIGHT. I n s t e a d o f o p e n v e r t i c e s a n d c l o s e d v e r t i c e s , w e c o n s i d e r o p e n e d g e s e c t i o n s a n d c l o s e d e d g e s e c t i o n s . I t is n o t difficult t o see t h a t for e a c h edge o fthe terrain, a t m o s t one c o n t i g u o u s section will b e o p e n a n d a t m o s t o n e will b eclosed. F r o m left t o right o na n edge, w e c a n h a v e a guarded section, a closed section, an open section, and another guarded section, t h o u g h not all o fthese sections will necessarily exist. F o r a n o p e n section, the l e f t m o s t p o i n t w i l l h a v e t h e l e f t m o s t R'. L(p) i s a l w a y s a v e r t e x r e g a r d l e s s o f w h e r e p i s . I f w e k e e p t r a c k o f t h e t r a n s i t i o n p o i n t s f o r t h e f u n c t i o n L(p) ( t h e r e a r e o n l y 0(n) o f t h e m [11]) t h e n we can k n o w where open sections end a n d closed sections begin. For every edge, o u r a l g o r i t h m also keeps t r a c k o fw h e r e t h e u n g u a r d e d s e c t i o n starts a n d e n d s (it m u s t b e c o n t i g u o u s ) . A f t e r p l a c i n g a g u a r d , u p d a t i n g t h e u n g u a r d e d s e c t i o n o n every edge c a n b edone quite easily i nlinear time. A s s u m e w ehave just p l a c e d a g u a r d a t g. T o t h e l e f t o f g c a l l t h e first v e r t e x x\ a n d c o n s i d e r t h e e d g e e i w h o s e l e f t e n d p o i n t i s x\. M a r k d o w n t h a t e v e r y p o i n t o n e\ i s g u a r d e d . N o w , m o v i n g l e f t f r o m x i , find t h e first v e r t e x a b o v e t h e l i n e g o i n g t h r o u g h g a n d x\\ c a l l t h i s X2, d e f i n e e% a p p r o p r i a t e l y a n d m a r k d o w n t h a t e v e r y p o i n t o n e<i a b o v e t h e l i n e g o i n g t h r o u g h g a n d x\ i s g u a r d e d . I t i s e a s y t o s e e h o w w e can proceed t oupdate the unguarded section of each edge in linear time. Since Chapter 4. Algorithm 4 G U A R D R i G H T ( a ; , c) ~ R . e ^ i r The General Case 26 (EFFICIENT VERSION) • c sees every unguarded vertex in (L(R(x)), x) e : . x i CH(T) while there are unguarded vertices in [x, R{x)) do if there is a closed vertex then let y be the rightmost closed vertex; if there is an open vertex in (y, R(x)) then b <— mm{R'(v) : v is open}; d <— min{i; : R'(v) = b}; if y is in (L'(d), R(x)) then G U A R D L E F T ( J / , L(d)); else place guards at c, L(d), L'(d), and R(d); end if else GUARDLEFT(y, y); end if else b <— min{R'(v) : v is open}; d <- min{v : R'{v) = b}; place guards at c, L(d), L'(d), and R(d); end if end while we place 0(n) guards the total cost of updating guarded edge sections of the terrain is 0(n ). 2 If we do all of the aforementioned maintenance, we will only need to consider the leftmost point in each open section when looking for b and d. Therefore we do not need to worry about asymptotically more points in T G - T T than in TG-VV. The running time therefore remains 0(n ). 2 Chapter 5. Domination of Directed Acyclic Graphs Chapter 5 Domination of Directed Acyclic Graphs 27 Chapter 5. Domination of Directed Acyclic Graphs 5.1 28 Motivation DOMINATING S E T i s a w e l l - k n o w n N P - c o m p l e t e p r o b l e m for general u n d i r e c t e d g r a p h s [20]. E v e r y u n d i r e c t e d g r a p h c a n b e r e p r e s e n t e d a s a d i r e c t e d g r a p h , so t h e p r o b l e m is N P - c o m p l e t e for g e n e r a l d i r e c t e d g r a p h s as w e l l . F o r u n d i r e c t e d a c y c l i c g r a p h s , i.e. t r e e s , t h e r e i s a s i m p l e l i n e a r - t i m e a l g o r i t h m f o r DOMINATING SET [12]. I n t h i s s e c t i o n w e s h o w t h a t t h e DOMINATING SET p r o b l e m on directed acyclic graphs ( D A G s ) , which we will abbreviate as D O M - D A G , is N P - c o m p l e t e a n d c a n n o t b e efficiently a p p r o x i m a t e d w i t h i n a s u b - l o g a r i t h m i c factor. W h i l e the general 1.5D terrain g u a r d i n g p r o b l e m i s a restriction of DOMSET on general graphs, the upward-looking case i s a restriction o f D O M - D A G ( a s s u m i n g t h e v e r t i c e s a r e i n g e n e r a l p o s i t i o n ) . I t is t h e r e f o r e n a t ural to consider the complexity of D O M - D A G before trying to solve T G - U P . T h e hardness a n d inapproximability of D O M - D A G support the relevance of a 2 - a p p r o x i m a t i o n a l g o r i t h m for T G - U P . INATING 5.2 NP-Hardness and Inapproximability Lemma 12. D O M I N A T I N G S E T on directed acyclic graphs is NP-complete. Furthermore, if k is the size of the minimum dominating set, it cannot be approximated to within a factor of o ( l o g k) in polynomial time unless N P C DTIME(n l o s l o e ). n Proof. T h e p r o o f f o l l o w s f r o m a f a i r l y t r i v i a l g a p - p r e s e r v i n g r e d u c t i o n f r o m SET COVER. R e c a l l t h a t a n i n s t a n c e I o f SET C O V E R is a set S a l o n g w i t h a c o l l e c t i o n C o f s u b s e t s o f S, a n d t h e p r o b l e m i s t o f i n d t h e s m a l l e s t s u b s e t C' o f C s u c h t h a t e v e r y e l e m e n t o f S i s i n a t l e a s t o n e o f t h e s u b s e t s i n C'. O u r r e d u c t i o n c r e a t e s a D A G G w i t h |-S*| + | C | + 1 v e r t i c e s t h a t i s a n i n s t a n c e o f D O M - D A G . For each element in S we create avertex with no outgoing edges. W e will call t h e s e element vertices. F o r e a c h X S C ( r e c a l l t h a t X C S), w e c r e a t e a v e r t e x w i t h a n o u t g o i n g e d g e t o e a c h e l e m e n t v e r t e x t h a t r e p r e s e n t s a n e l e m e n t i n X. W e w i l l c a l l t h e s e set vertices. W e t h e n c r e a t e o n e f i n a l v e r t e x , t h e s o u r c e , w i t h n o i n c o m i n g edges a n d w i t h a n o u t g o i n g edge to every set vertex. T h e r e a r e s e v e r a l t h i n g s t o n o t e a b o u t G. F i r s t o f a l l , t h e s o u r c e i s i n e v e r y d o m i n a t i n g set o fG since i t h a s n o i n c o m i n g edges. S e c o n d l y , for a n y d o m i n a t i n g set A of G t h a t contains a n e l e m e n t vertex, ad o m i n a t i n g set B o f equal or lesser cardinality c a n be constructed trivially by replacing each element v e r t e x v i n A w i t h o n e o f t h e s e t v e r t i c e s t h a t h a s a n o u t g o i n g e d g e t o v. F i n d i n g am i n i m u m d o m i n a t i n g set of G that contains the source a n d does n o t c o n t a i n a n y e l e m e n t v e r t i c e s is t h e r e f o r e n o h a r d e r t h a n f i n d i n g a n y m i n i m u m d o m i n a t i n g s e t o f G. S o a m i n i m u m d o m i n a t i n g s e t o f G c o n s i s t s o f t h e source, plus the m i n i m u m subset of set n o d e s required to cover all of the e l e m e n t Chapter 5. Domination of Directed Acyclic Graphs 29 n o d e s . It s h o u l d b e c l e a r t h a t t h e m i n i m u m d o m i n a t i n g s e t f o r G h a s s i z e k + 1 i f a n d o n l y i f t h e m i n i m u m s e t c o v e r o f I c o n t a i n s e x a c t l y k e l e m e n t s o f C. SET C O V E R is N P - c o m p l e t e a n d c a n n o t b e a p p r o x i m a t e d to w i t h i n a f a c t o r of o(log|S|) in polynomial time unless N P C D T I M E ( n s s ) [ 1 9 ] . Also, the size of t h e m i n i m u m d o m i n a t i n g set for t h e g r a p h o b t a i n e d b y o u r r e d u c t i o n is at m o s t \S\. S i n c e o u r r e d u c t i o n i s g a p - p r e s e r v i n g a n d i s c l e a r l y p o l y n o m i a l , D O M D A G m u s t be N P - c o m p l e t e a n d cannot be a p p r o x i m a t e d to within afactor of o ( l o g |fc|) i n p o l y n o m i a l t i m e u n l e s s N P C D T I M E ( n ' ° ). • l o s l o l o s n n Chapter 6. Future Work Chapter 6 Future Work 30 31 Chapter 6. Future Work 6.1 NP-Completeness The most pressing and obvious question regarding the 1.5D terrain guarding problem is whether o r not it is NP-complete. All o four attempts a t a n N P - h a r d n e s s p r o o f h a v e b e e n s t y m i e d b yt h e O r d e r C l a i m . O n t h e other h a n d , attempts a tdesigning an exact polynomial-time algorithm have also been unsuccessful. If t h e p r o b l e m i s n o t N P - h a r d , w e w o u l d b e i n t e r e s t e d i n a p o l y n o m i a l - t i m e a l g o r i t h m . I f t h e p r o b l e m i sN P - h a r d , w e w o u l d b e interested i n a p p r o x i m a b i l i t y t h r e s h o l d s , e.g. w h e t h e r i t i s A P X - c o m p l e t e o r a d m i t s a P T A S o r e v e n a n FPTAS. 6.2 Characterization of Terrain Graphs W e d e f i n e a n ordered graph a s a g r a p h G i n w h i c h t h e v e r t i c e s vi < vi < ... < v h a v e a n o r d e r i n g a n d t h e r e i s a n e d g e b e t w e e n Vi a n d vi i f o r e v e r y i € [ l , n — l ] . W e d e f i n e a terrain graph a s a g r a p h G t h a t i s t h e v i s i b i l i t y g r a p h o fa 1 . 5 D terrain (specifically, a n instance o fT G - V V ) . I ti s easy t o see that every terrain graph isan ordered graph, but not every ordered graph is a terrain graph. n + T h e O r d e r C l a i m seems t ocapture m u c h of the restriction of terrain graphs. H o w e v e r , i t is n o t t h e c a s e t h a t e v e r y o r d e r e d g r a p h o b e y i n g t h e O r d e r C l a i m is a terrain g r a p h (consider, for e x a m p l e , a cycle of 4 o rm o r e vertices). W h a t a d ditional restrictions must we place on ordered graphs t o ensure they are terrain g r a p h s ? C o n s i d e r the following l e m m a for 1 . 5 D terrains: L e m m a 13. ( M i d p o i n t C l a i m ) For any vertices and Vj such that j > i + 1 and Vi sees Vj, there is some vertex in (vi,Vj) that is seen by both and Vj. Proof. L e t x b e t h e v e r t e x i n (vi,Vj) c l o s e s t t o t h e l i n e p a s s i n g t h r o u g h Vi a n d Vj ( n o t e t h a t a l l v e r t i c e s i n t h i s i n t e r v a l a r e b e l o w t h e l i n e ) . I t i s e a s y t o s e e t h a t Vi a n d VJ b o t h s e e x. • W e w o u l d like t o k n o w whether the O r d e r C l a i m a n d the M i d p o i n t C l a i m together are restrictive enough that every ordered graph obeying both claims is a t e r r a i n g r a p h . I f t h i s is n o t t h e c a s e , t h e r e m a y b e s o m e o t h e r u s e f u l p r o p e r t y of terrain g r a p h s t h a t w e c o u l d exploit i n our search for a p o l y n o m i a l - t i m e terrain guarding algorithm. Chapter 6. Future Work 6.3 32 Reductions Between Restricted Visibility Problems T e r r a i n g u a r d i n g is e a s y w h e n g u a r d s c a n o n l y see t o t h e r i g h t . It a l s o s e e m s that m a n y t r o u b l e s o m e scenarios are e l i m i n a t e d w h e n guards c a n only see u p wards. W h e n guards can only look downwards, however, the problem seems as c o m p l e x as t h e u n r e s t r i c t e d case if n o t m o r e so, t h o u g h it s e e m s t h a t o u r a l g o r i t h m for the general case c a n solve this variant. W e would be interested in reductions between upward-looking, downwardlooking, and general terrain guarding. For example, would a polynomial-time a l g o r i t h m for t h e d o w n w a r d l o o k i n g c a s e i m p l y t h a t t h e g e n e r a l c a s e is i n P ? W o u l d a n N P - h a r d n e s s p r o o f for the u p w a r d - l o o k i n g case i m p l y that the general c a s e is N P - h a r d ? I n p a r t i c u l a r it s e e m s t h a t t h e u p w a r d - l o o k i n g c a s e s h o u l d b e at least as h a r d as the general case. However, our efforts to provide reductions of this kind have been unsuccessful. Bibliography 33 Bibliography P. Agarwal, S. Bereg, O. Daescu, H. Kaplan, S. Ntafos, and B. Zhu. Guarding a terrain by two watchtowers. In Symposium on Computational Geometry, pages 346-355, 2005. A. Aggarwal. The art gallery problem: Its variations, applications, and algorithmic aspects. PhD thesis, Johns Hopkins University, 1984. B. Ben-Moshe. Geometric Facility Location Optimization. PhD thesis, Ben-Gurion University, 2004. B. Ben-Moshe. Personal communication, 2005. B. Ben-Moshe, M. Katz, and J. Mitchell. A constant-factor approximation algorithm for optimal terrain guarding. In Symposium on Discrete Algorithms, 2005. P. Bose, D. Kirkpatrick, and Z. Li. Efficient algorithms for guarding or illuminating the surface of a polyhedral terrain. In Proceedings of the 8th Canadian Conference on Computational Geometry, pages 217-222, 1996. P. Bose, T. Shermer, G. Toussaint, and B. Zhu. Guarding polyhedral terrains. Computational Geometry: Theory and Applications, 7, 1997. H. Bronnimann and M. T. Goodrich. Almost optimal set covers in finite VC-dimension. Discrete & Computational Geometry, 14, 1995. D. Z. Chen, V. Estivill-Castro, and J. Urrutia. Optimal guarding of polygons and monotone chains (extended abstract), 1996. V. Chvatal. A combinatorial theorem in plane geometry. J. Comb. Theory Series B, 18:39-41, 1975. K. L. Clarkson and K. Varadarajan. Improved approximation algorithms for geometric set cover. In Symposium on Computational Geometry, 2005. E. Cockayne, S. Goodman, and S. Hedetniemi. A linear algorithm for the domination number of a tree. Information Processing Letters, 4(2):41-44, November 1975. T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. MIT Press, 2001. Bibliography 34 [14] S. Eidenbenz. (In-)Approximability of Visibility Problems on Polygons and Terrains. PhD thesis, E T H Zurich, 2000. [15] S. Eidenbenz. Approximation algorithms for terrain guarding. Information Processing Letters, 82(2):99-105, April 2002. [16] S. Eidenbenz, C . Stamm, and P. Widmayer. Positioning guards at fixed height above a terrain — an optimum inapproximability result. Lecture Notes in Computer Science, 1461, 1998. [17] S. Eidenbenz, C . Stamm, and P. Widmayer. Inapproximability results for guarding polygons and terrains. Algorithmica, 31(1):79—113, 2001. [18] H . Everett and E . Rivera-Campo. Edge guarding polyhedral terrains. Computational Geometry: Theory and Applications, 7, 1997. [19] U . Feige. A threshold of Inn for approximating set cover. Journal of the ACM, 45(4):634-652, July 1998. [20] M . Garey and D. Johnson. Computers and Intractibility: A Guide to the Theory of NP-Completeness. W . H . Freeman and Co., 1979. [21] D. Haussler and E . Welzl. e-Nets and Simplex Range Queries. Discrete & Computational Geometry, 2:127-151, 1987. [22] D. S. Johnson. Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences (JCSS), 9:256-278, 1974. [23] A . A . Kooshesh and B. M . E . Moret. Three-coloring the vertices of a triangulated simple polygon. Pattern Recognition, 25, 1992. [24] D. T . Lee and A . K . Lin. Computational complexity of art gallery problems. IEEE Transactions on Information Theory, 32:276-282, 1986. [25] M . Sharir and P. K . Agarwal. Davenport-Schinzel sequences and their geometric applications. Technical report, 1995.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Approximation algorithms for guarding 1.5 dimensional...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Approximation algorithms for guarding 1.5 dimensional terrains King, James Alexander 2005
pdf
Page Metadata
Item Metadata
Title | Approximation algorithms for guarding 1.5 dimensional terrains |
Creator |
King, James Alexander |
Date Issued | 2005 |
Description | The 1.5-dimensional terrain guarding problem gives an x-monotone chain (the terrain) and asks for the minimum set of vertices of the terrain (guards) such that every vertex of the terrain is seen by at least one guard. This terrain guarding problem is a restriction of the SET COVER problem, which is known to be both NP-complete and inapproximable within a sub-logarithmic factor [19]. Fortunately, it is known that the 1.5-dimensional terrain guarding problem is approximable to within a constant factor [5, 11], though no attempt has been made to minimize the approximation factor. We give a 4-approximation algorithm for the general 1.5D terrain guarding problem, as well as a 2-approximation algorithm for the case with upwardlooking guards, i.e. when guards cannot see vertices that are below themselves. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2009-12-11 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0051328 |
URI | http://hdl.handle.net/2429/16609 |
Degree |
Master of Science - MSc |
Program |
Computer Science |
Affiliation |
Science, Faculty of Computer Science, Department of |
Degree Grantor | University of British Columbia |
Graduation Date | 2005-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
Aggregated Source Repository | DSpace |
Download
- Media
- 831-ubc_2005-0505.pdf [ 1.77MB ]
- Metadata
- JSON: 831-1.0051328.json
- JSON-LD: 831-1.0051328-ld.json
- RDF/XML (Pretty): 831-1.0051328-rdf.xml
- RDF/JSON: 831-1.0051328-rdf.json
- Turtle: 831-1.0051328-turtle.txt
- N-Triples: 831-1.0051328-rdf-ntriples.txt
- Original Record: 831-1.0051328-source.json
- Full Text
- 831-1.0051328-fulltext.txt
- Citation
- 831-1.0051328.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0051328/manifest