Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Approximation algorithms for guarding 1.5 dimensional terrains King, James Alexander 2005

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.

Item Metadata

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

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 THE DEGREE OF MASTER OF SCIENCE in The Faculty of Graduate Studies (Computer Science) THE UNIVERSITY OF BRITISH COLUMBIA August, 2005 © James Alexander King, 2005 A b s t r a c t 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 upward-looking guards, i.e. when guards cannot see vertices that are below themselves. Contents iii Contents Abstract 1 1 Contents iii List of Figures v Acknowledgements vi 1 Introduction 1 1.1 Problem Statement 2 1.2 Motivation 4 1.2.1 Applications 4 1.2.2 Minimizing the Approximation Factor 4 1.2.3 Failure of Trivial Methods 4 1.3 Related Work 6 1.3.1 The Art Gallery Problem 6 1.3.2 1.5-Dimensional Terrain Guarding 6 1.3.3 2.5-Dimensional Terrain Guarding 8 1.3.4 Watchtower Problems 8 1.4 Organization 9 2 Preliminaries 10 2.1 Terminology and Notation 11 2.2 Elementary Lemmas 11 3 Upward Looking Guards 13 3.1 Introduction to the Upward Looking Case 14 3.2 The T G - U P Algorithm 14 3.3 Modifications for T G - T T - U p 16 3.4 Time Complexity 16 4 The General Case 17 4.1 Introduction to the General Case 18 4.2 Preliminaries 18 4.3 Finding a Good Left Vertex 21 4.4 The Terminal Case • 22 4.5 The Recursive Case 22 Contents iv 4.6 Modifications for TG-TT 23 4.7 Time Complexity 23 5 Dominat ion of Directed Acycl ic Graphs . . . 27 5.1 Motivation 28 5.2 NP-Hardness and Inapproximability 28 6 Future Work 30 6.1 NP-Completeness 31 6.2 Characterization of Terrain Graphs 31 6.3 Reductions Between Restricted Visibility Problems 32 Bibl iography 33 List of Figures List of Figures 1.1 An example of a 1.5D terrain, d can see 6, c, and e but not a or / . 2 1.2 A terrain for which the greedy method achieves a logarithmic approximation factor [4] 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 19 4.2 L'(v) and R(v) must be in the shaded region 20 4.3 The shaded region is terrain free, so every left vertex in [L(v), R'(v)] must see v 21 4.4 The nested interval [L(y)t R(L(y))] can be handled independently with the help of a dominant outside vertex 23 Acknowledgements v i Acknowledgements I w o u l d l i k e t o t h a n k m y s u p e r v i s o r , W i l l E v a n s , f o r h i s g u i d a n c e t h r o u g h o u t m y M a s t e r ' s d e g r e e a n d i n p a r t i c u l a r f o r t h i s p r o j e c t . I w o u l d a l s o l i k e t o t h a n k m y s e c o n d r e a d e r , D a v i d K i r k p a t r i c k , f o r h i s m a n y h e l p f u l c o m m e n t s . I a m v e r y g r a t e f u l t o B o a z B e n - M o s h e f o r t a k i n g t h e t i m e t o a s s i s t m e w i t h t h i s p r o b l e m . I w o u l d l i k e t o t h a n k a l l o f m y c o l l e a g u e s a t U B C , e s p e c i a l l y t h e s t u d e n t s a n d f a c u l t y o f t h e B E T A l a b . F i n a l l y , I w o u l d l i k e t o t h a n k M e l i n d a f o r a l l o f h e r l o v e a n d s u p p o r t . Chapter 1. Introduction 1 Chapter 1 Introduction Chapter 1. Introduction 2 1.1 Problem Statement In the 1.5-dimensional terrain guarding problem we are given as input a ter-rain T that is an x-monotone polygonal chain. An 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: An 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. With 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 C = V ( T ) and S T = V ( T ) . 2. T G - T T : S G = T and S T = T . Chapter 1. Introduction 3 I n t h i s p a p e r o u r m a i n f o c u s i s 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 b e p l a c e d o n v e r t i c e s a n d o n l y v e r t i c e s n e e d t o b e g u a r d e d ; t h i s c a n b e t h o u g h t o f a s t h e d i s c r e t e v e r s i o n o f t h e p r o b l e m . W e w i l l o f t e n r e f e r t o t h i s p r o b l e m s i m p l y a s T G . 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 o f t h e p r o b l e m , t h o u g h m i n o r m o d i f i c a t i o n s a r e r e q u i r e d t o a p p l y t h e m t o T G -T T . Chapter 1. Introduction 4 1.2 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 r o a d , p e r h a p s w i t h s e c u r i t y c a m e r a s o r s t r e e t l i g h t s . 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 . I t s p r o v e n i n -t r a c t i b i l i t y a n d i n a p p r o x i m a b i l i t y , h o w e v e r , m o t i v a t e u s t o l o o k t o w a r d s t h e 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 t h e p a t h b e t w e e n t w o p o i n t s o n a p o l y h e d r a l t e r r a i n . I t h a s b e e n p o i n t e d o u t [5] t h a t t h e 1 . 5 D 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 . 5 D 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 t h a t 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 a l g o r i t h m s e x i s t f o r T G . E f f o r t s t o d e s i g n a n e x a c t p o l y n o m i a l - t i m e a l g o r i t h m f o r T G h a v e b e e n u n s u c c e s s f u l a n d i t i s 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 . I f T G i s N P - h a r d , t h e n t h e b e s t a l g o r i t h m r u n n i n g i n p o l y n o m i a l t i m e w i l l b e t h e a p p r o x i m a t i o n a l g o r i t h m w i t h 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 i s s i g n i f i c a n t m o t i v a t i o n t o m i n i m i z e t h e a p p r o x i m a t i o n f a c t o r . 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 e l e m e n t s . S i m i l a r l y , t h e n a t u r a l g r e e d y a l g o r i t h m f o r t e r r a i n g u a r d i n g r e p e a t -e d l y p i c k s t h e g u a r d t h a t s e e s t h e m o s t u n g u a r d e d v e r t i c e s . I t i s n o t a t a l l o b v i o u s t h a t t h i s m e t h o d w o u l d n o t a c h i e v e a c o n s t a n t a p p r o x i m a t i o n f a c t o r . 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 a l g o r i t h m a c h i e v e s a l o g a r i t h m i c a p p r o x i m a t i o n f a c t o r . 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 3 t i m e s a s m a n y v e r t i c e s a s t h e b o w l t o i t s r i g h t . H a l f o f t h e v e r t i c e s o f 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 l e f t t o r i g h t t o a c h i e v e a n a p p r o x i m a t i o n f a c t o r o f O ( l o g n ) . T h e r e a r e o t h e r n a t u r a l g r e e d y - l i k e a l g o r i t h m s t h a t o n e m i g h t c o n s i d e r . F o r e x a m p l e , o n e c o u l d r e p e a t e d l y p i c k t h e g u a r d t h a t m a x i m i z e s t h e l e f t m o s t u n -g u a r d e d v e r t e x o r t h e l o w e s t u n g u a r d e d v e r t e x . T e r r a i n s e x i s t f o r t h e s e a l -g o r i t h m s t h a t p r o v e t h e y d o n o t a c h i e v e c o n s t a n t a p p r o x i m a t i o n f a c t o r s . T h e Chapter 1. Introduction 5 Figure 1.2: A terrain for which the greedy method achieves a logarithmic ap-proximation factor [4]. apparent absence of simple algorithms that achieve constant approximation fac-tors motivates us to consider more sophisticated techniques. Chapter 1. Introduction 6 1.3 Related Work 1.3.1 The Art Gallery Problem The 1.5D terrain guarding problem is similar to a well-studied polygon guard-ing problem known as the art gallery problem. This problem, posed by Vic to r Klee i n 1973, asks for the min imum number of security cameras (that can ro-tate to obtain a full field of vision) required to guard a given art gallery. The 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 them is contained wi th in the polygon. The size n of a problem instance is the number of vertices of the polygon. Chvatal ' s Art Gallery Theorem [10] states that |_§J cameras are always suf-ficient and sometimes necessary for guarding a polygon. Kooshesh and Moret [23] give a linear-time algori thm for guarding a polygon wi th |_§J cameras that is based on 3-colouring the triangulated polygon. F ind ing the min imum number of cameras required to guard a given polygon is N P - h a r d , as proven by Aggarwal [2]. The variation of the art gallery problem in which cameras must be placed on the perimeter of the polygon is more closely related to 1.5D terrain guarding. L^J cameras are s t i l l sufficient and sometimes necessary, and Kooshesh and Moret ' s algori thm works in this variation since it actually places cameras on vertices. Th i s variation is s t i l l NP-complete as proven by Lee and L i n [24]. Eidenbenz et al. [17] prove that the art gallery problem is APX-comple t e , regardless of restrictions on guard placement. This means that there is some positive constant 5 such that no polynomial-t ime algori thm wi th an approxima-t ion factor less than 1 + S exists. In other words, the problem does not admit a polynomial-t ime approximation scheme unless P = N P . They provide an even stronger result i n the case of polygons wi th holes: no polynomial-t ime algorithm can have a sub-logarithmic approximation 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 hul l of the terrain). If only the vertices of the terrain need to be guarded this bound drops to Every instance of T G is an instance of SET COVER, but we know that SET COVER is NP-complete (see, e.g., [20]) and no sub-logarithmic approximation factor can be obtained unless N P C D T I M E ( n l o g l o g n ) [19]. In general it is not part icular ly difficult to modify a T G - V V algori thm to solve instances of T G - T T , though this often involves some polynomial increase in time complexity. Chapter 1. Introduction 7 It is unknown whether or not T G is N P - h a r d . In 1995 Chen et al. [9] proposed an NP-hardness proof obtainable v ia a modification of Lee and L in ' s proof [24]. However, the proof, whose details were omitted, was never completed successfully. Since then, attempts to find a polynomial-t ime algori thm for T G and attempts to prove that it is N P - h a r d have both been unsuccessful. The first constant-factor approximation algori thm for the 1.5D terrain guard-ing problem was given by Ben-Moshe et al. [5]. Their algori thm works by first placing guards to divide the terrain into independent s u b t e r r a i n s . Each sub-terrain 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 . For each such sub-terrain that is not completely guarded they then proceed wi th steps that either reduce the s u b t e r r a i n or split it into multiple independent subterra inSv They made no attempt to minimize their algorithm's approximation factor; as such it is very large (at least 48). It could be brought down possibly as low as 6 wi th some minor modifications and careful accounting, but due to the inevitable cost incurred by repeatedly dividing the terrain it does not seem that it could be brought any lower than 6. Our approach differs from that of Ben-Moshe et al. in that ours is completely iterative. B y avoiding a divide and conquer approach we are able to get the approximation factor as low as 4. We need to work differently than they do their iterative steps since we cannot depend on the desirable properties that their divis ion offers. Ben-Moshe et al. also give a reduction from T G - T T to T G - V V . They 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 which any set of vertices that guards every vertex must guard the entire terrain. They then show that any edge guard can be replaced by two vertex guards, essentially saying that a c-approximation algori thm for T G - V V can be applied to one of these augmented terrains to give a 2c-approximation algorithm for T G - T T . Another constant-factor approximation algorithm is given by Clarkson and Varadarajan [11]. Consider a part i t ion of a 1.5D terrain into maximal 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 wi th the leftmost point that sees it and read the labels from leftmost interval to rightmost interval, Clarkson and Varadarajan note that we end up wi th an (n, 2) Davenport-Schinzel sequence [25]. Such a sequence must have length at most 2n. This characterization of the lack of complexity in 1.5D terrains allows them to efficiently find appropriate e-nets [21] for instances of T G . They then apply the SET COVER method of Bronnimann and Goodr ich [8] to solve the problem using these e-nets. The end result is a constant-factor approximation algori thm that runs i n polynomial 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 [ 4 "g 4 J are sometimes necessary. Efficient algorithms for achieving these bounds for vertex guards and edge guards are given by Bose et al. [6]. 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 NP C DTIME(n l o s . I o s n ) [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). 1.3.4 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 9 1.4 Organization T h e r e s t o f t h e p a p e r i s o r g a n i z e d a s f o l l o w s . I n C h a p t e r 2 w e i n t r o d u c e n o t a t i o n a n d s o m e s m a l l b u t f u n d a m e n t a l l e m m a s . I n C h a p t e r 3 w e g i v e o u r 2 - a p p r o x i m a t i o n a l g o r i t h m f o r t h e u p w a r d - l o o k i n g c a s e . I n C h a p t e r 4 w e g i v e 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 f o r t h e g e n e r a l c a s e . I n C 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 S E T o n d i r e c t e d a c y c l i c g r a p h s t o s h o w t h a t o u r 2 - a p p r o x i m a t i o n a l g o r i t h m f o r t h e u p w a r d - l o o k i n g c a s e i s s i g n i f i c a n t . I n 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 f o r f u t u r e w o r k r e g a r d i n g 1 . 5 D t e r r a i n g u a r d i n g . Chapter 2. Preliminaries 10 Chapter 2 Preliminaries Chapter 2. Preliminaries 1 1 2.1 Terminology and Notation A n i n s t a n c e o f t h e 1 . 5 D t e r r a i n g u a r d i n g p r o b l e m i s 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,..., vn}, s u c h t h a t i s t o t h e r i g h t 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 e a s i e r t o d e s c r i b e r e l a t i o n s h i p s b e t w e e n t h e m . F o r e x a m p l e , 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 a s i m i l a r m a n n e r . 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 v e r t i c e s i n t h e g e n e r a l c a s e , w h e t h e r x i s a v e r t e x o r n o t ( t h i s i s n o t n e c e s s a r i l y 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) 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 [ x , vn\. 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 ) a n d u s e C H R ( X ) f o r t h a t o f T R ( X ) . I f a v e r t e x x s e e s e v e r y u n g u a r d e d v e r t e x t h a t a n o t h e r v e r t e x y s e e s w e s a y 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 d o m i n a t e s a v e r t e x x i f e v e r y u n g u a r d e d v e r t e x s e e n b y x i s a l s o s e e n b y s o m e v e r t e x i n S. W e s a y t h a t x d o m i n a t e s y w i t h r e s p e c t t o a c e r t a i n r e g i o n o f T i f x s e e s e v e r y u n g u a r d e d v e r t e x i n t h a t r e g i o n t h a t y s e e s . W e c o n s i d e r a m i n i m u m g u a r d i n g s e t G O P T f o r t h e t e r r a i n T . W e a s s u m e t h e r e i s s o m e m a p p i n g g o f v e r t i c e s o f T t o g u a r d s i n G O P T s u c h t h a t , f o r 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 u s e i t t o s i m p l i f y t h e e x p l a n a t i o n o f o u r a c c o u n t i n g s c h e m e . O u r a l g o r i t h m s 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 a l g o r i t h m s . 2.2 Elementary Lemmas H e r e w e s t a t e a n d p r o v e s e v e r a l s m a l l b u t f u n d a m e n t a l l e m m a s t h a t w e w i l l u s e i n t h e r e s t o f t h e p a p e r . T h e y a p p l y t o b o t h t h e g e n e r a l c a s e a n d t h e u p w a r d - l o o k i n g c a s e . T h e s e l e m m a s a n d c o r o l l a r i e s c a n b e u s e d w i t h l e f t a n d r i g h t i n t e r c h a n g e d ; t h i s i s s t a t e d e x p l i c i t l y f o r C o r o l l a r y 1 a s a n e x a m p l e b u t i s n o t s t a t e d f o r t h e o t h e r s . L e m m a 1. (Order Claim) [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. Preliminaries 1 2 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 s e e s c a n d b s e e s d w o u l d b e v i o l a t e d ) . T h i s m e a n s t h a t t h e t w o l i n e 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 c a s e 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 i f a s e e s c a n d b s e e s d t h e n o m u s t b e b e l o w d s o t h e l e m m a h o l d s . • 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 13 Chapter 3 Upward Looking Guards Chapter 3. Upward Looking Guards 14 3.1 Introduction to the Upward Looking Case We consider a restricted version of the 1.5-dimensional terrain guarding prob-lem 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 ver-tices 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 DAGs 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 NP C D T I M E ( n l o s l o s n ) . 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 sig-nificance 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. 3.2 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 TR(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 TR(R{P)). 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. • 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 = R(p) 2. L(p) =p< R(p) or L(p) <p = R(p) 3. L ( P ) <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 ap-proximation factor below 2. The number of local minima is one more than the number of intermediate maxima, since there is exactly one local minimum be-tween 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 be-low 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. Chapter 3. Upward Looking Guards 16 Pseudocode for our algorithm is as follows: Algorithm 1 T G - U P ( 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 Ben-Moshe points out [3] this can be done in 0(n2) 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(n2) time. 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(n2) and can be constructed in 0(n2) time. Our algorithm therefore runs in 0(n2) time for T G - T T - U P . Chapter 4. The General Case 17 Chapter 4 The General Case Chapter 4. The General Case 18 4.1 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 precondi-tions 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 un-guarded 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 CH(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 indepen-dent 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. • Corol lary 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)]. An 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 X R(x) L'(v) , / »R(v ) Figure 4.1: The order of some vertices related to an open vertex v. Chapter 4. The General Case 2 0 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 r e s t f o l l o w s t r i v i a l l y . • ,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 s e e 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 l e m m a . • 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. 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 t h e n v c a n n o t s e e a n y v e r t e x t o t h e l e f t o f u s o u d o m i n a t e s v w i t h r e g a r d t o TL(U). 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, w e c a n s e e t h a t TL(u) U [L(R(x)), x) U TR(x) = T. T h e r e f o r e { c , u} d o m i n a t e s v. • 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 pseudo-independent 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 compli-cated 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 hori-zontally: 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 Chapter 4. The General Case 2 3 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)) x R(x) , , - ;>R(L(y) ) L(y)^T •> y 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 i n d e p e n d e n t l y w i t h t h e h e l p o f a d o m i n a n t o u t s i d e v e r t e x . I n t h i s w a y w e c a n d o a s o r t o f r e c u r s i v e z i g - z a g g i n g w h e r e e a c h c a l l 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 4 g u a r d s a n d , i f w e n e e d t o , s t a r t a b 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 r e a l m o d i f i c a t i o n s n e e d t o b e m a d e t o a p p l y o u r T G a l g o r i t h m t o 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 f m 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 e f f i c i e n t l y a s p o s s i b l e . T h i s i s d i s c u s s e d i n S 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 24 Algor i thm 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 lgor i thm 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)) then 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 Chapter 4. The General Case 25 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(n2) t i m e . W e c a n t h e r e f o r e g i v e a n u p p e r b o u n d o f 0(n3) f o r t h e r u n n i n g t i m e o f T G - V V . 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 s l i g h t l y ; o n a g i v e n i t e r a t i o n , x i s n o t n e c e s s a r i l y u n g u a r d e d s o 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 v e r t e x . I f t h e r e i s 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 G U A R D R l G H T ( 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 o f o p e n v e r t i c e s ) t o f i n d a n a p p r o p r i a t e b a n d d f a s t e r i n e a c h i t e r a t i o n . A c a l l t o GUARDR IGHT (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(n2) 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 b o u n d e d b y O ( n l o g n ) . A l l o t h e r o v e r h e a d i n c u r r e d b y t h e a l g o r i t h m c a n b e d e a l t w i t h i n 0[n2) 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(n2). 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. W h e n d e a l i n g w i t h T G - T T t h e o n l y r e a l p r o b l e m i s f i n d i n g b a n d d a t e a c h 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 i s n o t d i f f i c u l t t o s e e t h a t f o r e a c h e d g e o f t h e t e r r a i n , a t m o s t o n e c o n t i g u o u s s e c t i o n w i l l b e o p e n a n d a t m o s t o n e w i l l b e c l o s e d . F r o m l e f t t o r i g h t o n a n e d g e , w e c a n h a v e a g u a r d e d s e c t i o n , a c l o s e d s e c t i o n , a n o p e n s e c t i o n , a n d a n o t h e r g u a r d e d s e c t i o n , t h o u g h n o t a l l o f t h e s e s e c t i o n s w i l l n e c e s s a r i l y e x i s t . F o r a n o p e n s e c t i o n , t h e 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 w e c a n k n o w w h e r e o p e n s e c t i o n s e n d a n d c l o s e d s e c t i o n s b e g i n . F o r e v e r y e d g e , o u r a l g o r i t h m a l s o k e e p s t r a c k o f w h e r e t h e u n g u a r d e d s e c t i o n s t a r t s a n d e n d s ( i t 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 e v e r y e d g e c a n b e d o n e q u i t e e a s i l y i n l i n e a r t i m e . A s s u m e w e h a v e j u s t 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 X 2 , 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 c a n p r o c e e d t o u p d a t e t h e u n g u a r d e d s e c t i o n o f e a c h e d g e i n l i n e a r t i m e . S i n c e Chapter 4. The General Case 26 Algorithm 4 G U A R D R i G H T ( a ; , c) ( E F F I C I E N T V E R S I O N ) ~ . • c sees every unguarded vertex in (L(R(x)), x) R e ^ i r 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 G U A R D L E F T ( 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(n2). 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 TG-TT than in TG-VV. The running time therefore remains 0(n2). Chapter 5. Domination of Directed Acyclic Graphs 27 Chapter 5 Domination of Directed Acyclic Graphs Chapter 5. Domination of Directed Acyclic Graphs 2 8 5.1 Motivation D O M I N A T I N G 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 f o r g e n e r a l u n d i -r e c t e d g r a p h s [ 2 0 ] . 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 , s o t h e p r o b l e m i s N P - c o m p l e t e f o r g e n e r a l d i r e c t e d g r a p h s a s 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 D O M I N A T I N G S E T [ 1 2 ] . 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 D O M I N A T I N G S E T p r o b -l e m o n d i r e c t e d a c y c l i c g r a p h s ( D A G s ) , w h i c h w e w i l l a b b r e v i a t e a s D O M - D A G , i s N P - c o m p l e t e a n d c a n n o t b e e f f i c i e n t l y 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 f a c t o r . W h i l e t h e g e n e r a l 1 . 5 D t e r r a i n g u a r d i n g p r o b l e m i s a r e s t r i c t i o n o f D O M -I N A T I N G S E T o n g e n e r a l g r a p h s , t h e u p w a r d - l o o k i n g c a s e i s a r e s t r i c t i o n 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 i s t h e r e f o r e n a t -u r a l t o c o n s i d e r t h e c o m p l e x i t y o f D O M - D A G b e f o r e t r y i n g t o s o l v e T G - U P . T h e 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 D O M - D A G s u p p o r t t h e r e l e v a n c e o f a 2 - a p p r o x i m a t i o n a l g o r i t h m f o r T G - U P . 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 D T I M E ( 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 S E T C O V E R . R e c a l l t h a t a n i n s t a n c e I o f S E T C O V E R i s a s e t 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 . F o r e a c h e l e m e n t i n S w e c r e a t e a v e r t e x w i t h n o o u t g o i n g e d g e s . W e w i l l c a l l 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 e d g e s a n d w i t h a n o u t g o i n g e d g e t o e v e r y s e t v e r t e x . 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 s e t o f G s i n c e i t h a s n o i n c o m i n g e d g e s . S e c o n d l y , f o r a n y d o m i n a t i n g s e t A o f G t h a t c o n t a i n s a n e l e m e n t v e r t e x , a d o m i n a t i n g s e t B o f e q u a l o r l e s s e r c a r d i n a l i t y c a n b e c o n s t r u c t e d t r i v i a l l y b y r e p l a c i n g e a c h e l e m e n t 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 a m i n i m u m d o m i n a t i n g s e t o f G t h a t c o n t a i n s t h e s o u r c e a n d d o e s 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 i s 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 s o u r c e , p l u s t h e m i n i m u m s u b s e t o f s e t n o d e s r e q u i r e d t o c o v e r a l l o f t h e e l e m e n t Chapter 5. Domination of Directed Acyclic Graphs 2 9 n o d e s . I t 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. S E T C O V E R i s 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 t o w i t h i n a f a c t o r o f o ( l o g | S | ) 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 s n ) [ 1 9 ] . A l s o , t h e s i z e o f 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 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 i s a t 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 b e 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 t o w i t h i n a f a c t o r o f 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 ' ° s l o s n ) . • Chapter 6. Future Work 30 Chapter 6 Future W o r k Chapter 6. Future Work 3 1 6.1 NP-Completeness T h e m o s t p r e s s i n g a n d o b v i o u s q u e s t i o n r e g a r d i n g t h e 1 . 5 D t e r r a i n g u a r d -i n g p r o b l e m i s w h e t h e r o r n o t i t i s N P - c o m p l e t e . A l l o f o u r a t t e m p t s 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 y t h e O r d e r C l a i m . O n t h e o t h e r h a n d , a t t e m p t s a t d e s i g n i n g a n e x a c t p o l y n o m i a l - t i m e a l g o r i t h m h a v e a l s o b e e n u n -s u c c e s s f u l . I f 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 s 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 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 F P T A S . 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 < ... < vn 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 f a 1 . 5 D t e r r a i n ( s p e c i f i c a l l y , a n i n s t a n c e o f T G - V V ) . I t i s e a s y t o s e e t h a t e v e r y t e r r a i n g r a p h i s a n o r d e r e d g r a p h , b u t n o t e v e r y o r d e r e d g r a p h i s a t e r r a i n g r a p h . T h e O r d e r C l a i m s e e m s t o c a p t u r e m u c h o f t h e r e s t r i c t i o n o f t e r r a i n g r a p h s . H o w e v e r , i t i s 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 i s a t e r r a i n g r a p h ( c o n s i d e r , f o r e x a m p l e , a c y c l e o f 4 o r m o r e v e r t i c e s ) . W h a t a d -d i t i o n a l r e s t r i c t i o n s m u s t w e p l a c e o n o r d e r e d g r a p h s t o e n s u r e t h e y a r e t e r r a i n g r a p h s ? C o n s i d e r t h e f o l l o w i n g l e m m a f o r 1 . 5 D t e r r a i n s : 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 l i k e t o k n o w w h e t h e r t h e O r d e r C l a i m a n d t h e M i d p o i n t C l a i m t o g e t h e r a r e r e s t r i c t i v e e n o u g h 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 b o t h c l a i m s i s a t e r r a i n g r a p h . I f t h i s i s 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 o f t e r r a i n g r a p h s t h a t w e c o u l d e x p l o i t i n o u r s e a r c h f o r a p o l y n o m i a l - t i m e t e r r a i n g u a r d i n g a l g o r i t h m . Chapter 6. Future Work 32 6.3 Reductions Between Restricted Visibility Problems T e r r a i n g u a r d i n g i s e a s y w h e n g u a r d s c a n o n l y s e e t o t h e r i g h t . I t a l s o s e e m s t h a t m a n y t r o u b l e s o m e s c e n a r i o s a r e e l i m i n a t e d w h e n g u a r d s c a n o n l y s e e u p -w a r d s . W h e n g u a r d s c a n o n l y l o o k d o w n w a r d s , h o w e v e r , t h e p r o b l e m s e e m s a s c o m p l e x a s t h e u n r e s t r i c t e d c a s e i f n o t m o r e s o , t h o u g h i t s e e m s t h a t o u r a l g o r i t h m f o r t h e g e n e r a l c a s e c a n s o l v e t h i s v a r i a n t . W e w o u l d b e i n t e r e s t e d i n r e d u c t i o n s b e t w e e n u p w a r d - l o o k i n g , d o w n w a r d -l o o k i n g , a n d g e n e r a l t e r r a i n g u a r d i n g . F o r e x a m p l e , w o u l d a p o l y n o m i a l - t i m e a l g o r i t h m f o r 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 i s 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 f o r t h e u p 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 i s N P - h a r d ? I n p a r t i c u l a r i t 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 a t l e a s t a s h a r d a s t h e g e n e r a l c a s e . H o w e v e r , o u r e f f o r t s t o p r o v i d e r e d u c t i o n s o f t h i s k i n d h a v e b e e n u n s u c c e s s f u l . Bibliography 33 Bibliography P. Agarwal, S. Bereg, O. Daescu, H. Kaplan, S. Ntafos, and B. Zhu. Guard-ing a terrain by two watchtowers. In Symposium on Computational Geom-etry, 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 approxima-tion 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 poly-gons 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. Com-putational 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. 

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

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}]}"
                            data-media="{[{embed.selectedMedia}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0051328/manifest

Comment

Related Items