Optimistic and Pessimistic Shortest Paths on Uncertain Terrains by Yury Kholondyrev B.Sc, The University of British Columbia, 2005 A THESIS SUBMITTED IN PARTIAL F U L F I L M E N T OF T H E REQUIREMENTS FOR T H E D E G R E E O F Master of Science in The Faculty of Graduate Studies (Computer Science) The University Of British Columbia October 12, 2007 © Yury Kholondyrev 2007 11 Abstract In the U n c e r t a i n T e r r a i n Shortest P a t h p r o b l e m we consider a t r i a n g u l a t e d t e r r a i n w i t h vertices h a v i n g u n c e r t a i n Z - c o o r d i n a t e s : each v e r t e x is d e n n e d as a (xj y, z~, z ) + t u p l e , where the z c o o r d i n a t e of a vertex is u n c e r t a i n a n d c a n be a n y w h e r e i n the range f r o m z~~ to z . + W e are l o o k i n g for a p a t h (defined b y its p r o j e c t i o n to the X y - p l a n e ) s u c h t h a t , over all possible t e r r a i n s , t h e p a t h is as s h o r t as possible. W e l o o k a t b o t h pessimistic ( t e r r a i n a r r a n g e s itself t o m a x i m i z e the l e n g t h of the p a t h t h a t we choose) a n d o p t i m i s t i c ( t e r r a i n takes the state t h a t m i n i m i z e s the l e n g t h of o u r p a t h ) scenarios. W e restrict ourselves to walk o n l y a l o n g the edges of the t e r r a i n . T h e u n r e s t r i c t e d p r o b l e m (when we are allowed to w a l k o n t h e faces of t h e terrain) has been p r o v e n to be N P - h a r d i n b o t h pessimistic a n d o p t i m i s t i c scenarios. W e prove t h a t the edge-restricted pessimistic p r o b l e m is N P - h a r d by p r o v i d i n g a r e d u c t i o n f r o m the S U B S E T - S U M p r o b l e m a n d give 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 the edge-restricted o p t i m i s t i c p r o b l e m . iii Contents Abstract ii Contents iii List of Figures iv Acknowledgements v 1 1 Introduction 1.1 1.2 1.3 1.4 2 4 A , Pessimistic E d g e - R e s t r i c t e d Shortest P a t h 2.1 2.2 2.3 2.4 2.5 2.6 2.7 3 Problem Statement Motivation Related Work Thesis Layout Introduction and Basic Observations Gadgets NP-hardness of pessimistic path Precision Issues Exponential Algorithm Approximation Algorithm . . Dijkstra-based Approximation Algorithm 1 2 2 3 4 4 5 7 9 10 11 12 O p t i m i s t i c E d g e - R e s t r i c t e d Shortest P a t h 14 3.1 3.2 3.3 3.4 3.5 3.6 14 15 17 17 22 23 Introduction and Basic Observations Algorithm design attempt Discarding sub-optimal pseudo-straight paths Polynomial-time Algorithm Proofs Polynomial-time algorithm Handling Uncertain Source and Target Conclusions and Future W o r k 24 4.1 4.2 24 25 Edge-Restricted Problems Unrestricted Problems P r o v i n g t h e constant factor o f 10 for t h e g a d g e t * Bibliography 27 29 iv List of Figures 1.1 Some uncertain terrain with 4 faces and 5 vertices 2 2.1 2.2 2.3 2.4 2.5 2.6 Terrain can be adjusted to make the path longer by moving v up. 4 A gadget incrementing both UP and DOWN by the same constant. 6 A gadget changing UP - DOWN by a given constant 7 Ci + C is greater than 2C = 2V2H for any non-zero Q 8 Some reduction from SUBSET-SUM. On the bottom half of the Figure, the line segments that are shifted down correspond to v 's, while the line segments that are shifted along Y-axis (moved up on the picture) correspond to v\S. Note that the gatgets only look the same on the picture and actually have different parameters 6 9 Splitting some vertex's uncertainty range into 4 buckets 11 3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 The traversal can be made shorter if the angles are different. . . Any optimal path must be piecewise pseudo-straight A possible reduction from SUBSET-SUM Growing cones starting at the lower extreme of v All cone two rays above the dotted ray are dominated. The rays in C below the dotted line are dominated Short-cutting the rays above BOTTOMi Two cones that only differ in their distances to the end point. . . 14 15 16 18 19 20 21 21 4.1 4.2 Triangles A and B are both dependent on the vertex v The slope of the line ab can be arbitrarily large as both a and b are getting close to t; 25 2 0 2 2 2 26 Acknowledgements First of all, I want to thank my supervisor, W i l l Evans, for introducing this problem to me and guiding me through all the aspects of writing this thesis and submitting it as a paper for a conference. Next, I'm very grateful to David Kirkpatrick for agreeing to read my thesis and making a number of useful suggestions, including pointing out that the NP-hardness proofs in this thesis would not be complete without bit-complexity analysis. I would also like to thank Jack Snoeyink, whom I met at the Canadian Conference on Computational Geometry 2007, and who pointed out the weakness of the worst-case scenario model used in this thesis (additional measurements result in longer and longer worst-case length). Finally, I want to thank my A C M I C P C teammates, in particular Matthew Chan, Bartholomew Furrow and Anton Likhtarov, who agreed to listen to my ideas for the NP-hardness proofs and the algorithms presented in this thesis and made very useful comments. 1 Chapter 1 Introduction P r o b l e m Statement 1.1 Consider the following situation: you have a 3-dimensional model representing a terrain and you need to go from point s to point t on the terrain as fast as possible. The problem seems quite natural for any area that has a lot of hills/mountains/valleys, making it impossible to walk from s to t in a straight line (in 3D). We will assume that the fastest route from s to t is equivalent to the shortest path that lies on the surface of the terrain. It can be argued that going uphill requires more time than going downhill but we will only consider the problem of minimizing the path's length. It is very common in real life that the model (or map) of an area is inexact. We will try to account for any errors that a map may contain by introducing uncertainty. A commonly used model for a fixed (certain) terrain is a 3-dimensional triangular mesh. We will stick to the triangular mesh representation and let the vertices of the mesh account for uncertainty. We will mostly look at the paths that follow the edges of terrains, so it will be convenient to us to think of an uncertain terrain as a graph. An uncertain terrain is an undirected graph G = (V, E) and an uncertainty interval for each vertex v G V that is specified by its two extreme points v~ and v in 3D. The X arid Y coordinates of v~ and v are identical but their Z-coordinates may differ (v~ has smaller z-coordinate). The graph G embedded in the XY-plane using the XY-coordinates of its vertices forms a triangulation, possibly with holes. It is worth noting that the ability to have holes in the triangulation is not important from the point of view of finding the shortest path. Any hole can be patched by introducing an a very high mountain on its place, ensuring that no shortest path can go through it. An uncertain terrain defines a set of feasible fixed(certain) terrains; those whose projections to the XY plane match the projection of the uncertain terrain and whose vertices lie within the corresponding Z ranges. We will use the terms lower terrain (upper terrain) to refer to the case when all the vertices are placed at the lower (upper bounds) of their Z ranges. + + Within the model described above, a number of shortest path problems can be formulated. The problem can be unrestricted, when you are allowed to traverse the faces of the terrain, or edge-restricted, when you are only allowed to travel along the edges. The problem can be solved with the optimistic assumption, Chapter 1. Introduction 2 Z Figure 1.1: Some uncertain terrain with 4 faces and 5 vertices. when we assume that the actual terrain is the one that minimizes the length of the path that we choose, or the pessimistic assumption, when we assume that the terrain will have the worst shape possible. We will mainly look at the edge-restricted versions of the optimistic and the pessimistic shortest path problems. 1.2 Motivation The model only considers uncertainty of Z coordinates (and not X, Y) because it is natural to have a large altitude error and a much smaller latitude and longitude error when constructing a terrain based on satellite images of mountainous areas [4]. 1.3 Related W o r k The unrestricted version of the shortest path on an uncertain terrain was considered by Chris Gray [1] in 2004. He proved that finding either optimistic or pessimistic shortest paths on an uncertain terrain is NP-hard using the techniques similar to those Canny and Reif [2]' used to prove NP-hardness of Euclidian shortest path among polyhedral obstacles in 3D. Our NP-hardness proof in Chapter 2 can be modified slightly (by replacing all triangles with holes, as described earlier) to become an alternative to Gray's proof for the pessimistic case. The problem of finding the shortest path on fixed (certain) terrains is well studied and there are a number of algorithms that solve it in polynomial time. Mitchell et al [3] showed how to solve the more general problem of finding the shortest path on an arbitrary polyhedral surface, which does not even have to be a terrain, in 0(n log(n)) time; where n is the number of edges in the polyhedra. The edge-restricted problem of finding the shortest path on a fixed terrain can be solved with Dijkstra's algorithm in 0(E + V log V) time. 2 Chapter 1. Introduction 1.4 3 Thesis Layout In Chapter 2, we prove that the pessimistic edge-restricted version of the problem is NP-hard and give an e-approximation algorithm. Chapter 3 looks into the optimistic edge-restricted version of the problem and provides a polynomial time algorithm that solves it exactly. Finally, Chapter 4 summarises the results and mentions some intuitive attempts (that did not succeed) to design approximation algorithms for the unrestricted versions of the problem. 4 Chapter 2 Pessimistic Edge-Restricted Shortest P a t h 2.1 Introduction and Basic Observations In the pessimistic case, we are looking for the "guaranteed" shortest edgerestricted path (a sequence of edges) between two vertices on an uncertain terrain. In other words, among all possible paths, we are trying to find the one that will be the shortest in the worst case over all possible terrains (a pessimistic assumption). We assume that the distance from any vertex to itself is zero, no matter what the vertex's uncertainty range is. Note that the worst case terrain for any path has vertices that lie at one of the extreme points of every vertex's Z range that the path goes through. To see that, first note that no shortest path will use the same vertex twice. Now, look at the Figure 2.1. The length of the path pq as a function of x is pq(x) = \/x + a + \J(c — x) + b . The second derivative of pq with respect to x is a /(a + x ) / + b /(b + (c — or) ) / > 0. Because the second derivative is always positive, pq{x) cannot have maximums other than at the extreme points of the range on which it is evaluated. 2 2 2 2 2 2 3 2 2 2 2 2 3 2 Figure 2.1: Terrain can be adjusted to make the path longer by moving v up. Chapter 2. Pessimistic Edge-Restricted Shortest Path 5 It is the uncertainty of vertices that makes the problem more difficult than the standard shortest path problem in a graph. We cannot even tell what the distance from a fixed point to any given vertex is. Vertices are actually ranges and may contain an infinite number of points, so we would have to provide a distance to every one of those points to specify the distance to a vertex. Fortunately, as we noticed above, in the pessimistic case only the distances to the extremes of every vertex are interesting to us. Most shortest path algorithms work in polynomial time by computing a shortest path tree from the source vertex to all the vertices in the graph by gradually expanding the set of vertices to which the shortest paths are known. That works because, in most cases, the shortest paths are composed of smaller shortest paths. Our case is quite different, we cannot just store the shortest distance to a vertex as we grow our shortest path tree. We should take into account where in the Z range that path ends. Knowing that it must end at one of the extreme points, let us define a path measure that consists of two values, UP and DOWN, for a path from the source to a given vertex v that guarantees distance of at most UP to v and at most DOWN to v~. + These measures, in contrast to the distances that are used when running Dijkstra's or Bellman-Ford's algorithms, are no longer totally ordered scalars. There is no way to say, for example, which measure is better, (1,3) or (3,1), even though (1,1) is obviously better than (3,3). As a result, we cannot solve the pessimistic edge-restricted shortest path problem directly by Bellman-Ford's or Dijkstra's algorithms because we cannot always compare two measures to decide which one is smaller. We say that (1,1) dominates (3,3) and, in general, (a,b) dominates (c, d) if a < c and b < d or o < c and b < d. We also say that the path with measure (a, b) dominates the path with measure (c, d) and that measure (a,b) is better than measure (c, d). 2.2 Gadgets Potentially, every path that does not visit the same vertex twice and goes from the source vertex to the target vertex may have a distinct measure. It seems natural that if we can prevent those paths from being dominated by one another and make sure that there are an exponential number of them, we will end up with a "hard" problem instance. Looking at every possible non-dominated path will be inefficient and we will not be able to use a standard shortest path algorithm for the reasons outlined in the previous paragraph. Consider the chain of three vertices in Figure 2.2, which are evenly spaced along the X-axis. All of them have the same Z uncertainty range. Note that we can rotate vertices u and w around the Z-axis at the vertex v as we wish without changing the distances C and D. Chapter 2. Pessimistic Edge-Restricted Shortest Path F i g u r e 2.2: A gadget i n c r e m e n t i n g b o t h UP and L e t ' s assume t h a t there is a p a t h w i t h measure DOWN 6 b y the s a m e c o n s t a n t . (UP, DOWN) to t h e vertex W h a t d i s t a n c e c a n we guarantee to the t o p / b o t t o m of vertices v a n d w? u. Taking into a c c o u n t t h a t we desire the worst case p a t h l e n g t h , the v e r t e x v w i l l get a p a t h w i t h measure (max( UP + D, DOWN + C), m a x ( UP + C, DOWN + £>)). UP a n d DOWN is negligible If the absolute value of the difference between c o m p a r e d to the absolute value of the difference between C a n d D (i.e. DOWN\ < \C - D\), then vertex v because C is c l e a r l y greater t h a n D. reached i n a gadget F o l l o w i n g the s a m e i d e a , v e r t e x w c a n be (UP + 2C, DOWN + 2 C ) . (let's call it (UP, DOWN) at u gadgetl) In other words, we have j u s t c o n s t r u c t e d t h a t allows us to t r a n s f o r m a p a t h m e a s u r e into a p a t h measure (UP + a, DOWN + a) .at w, a = 2 C , subject to the restrictions m e n t i o n e d above. preserves (UP — DOWN) | UP — (DOWN + C, UP + C) c a n be reached i n : a n d increments N o t e t h a t this (UP + DOWN) by 2a where gadget as some p a t h goes t h r o u g h it. A l s o note t h a t the p r o j e c t i o n s of the vertices u, v, a n d w o n the X, F - p l a n e need not be colinear since it is o n l y the lengths C a n d D that matter. N o w , consider a slightly different c h a i n s h o w n i n F i g u r e 2.3. O n c e again, the three vertices m a y not be colinear i n the X, y - p l a n e . L e t ' s n a m e t h e longer C\ a n d the shorter cross-link Ci- T h e n a p a t h m e a s u r e (UP, DOWN) u w i l l get c o n v e r t e d into (UP + 2C\,D0WN + 2C2) at v e r t e x w (this t i m e we assume t h a t | UP — DOWN] <C IC2 — B\). In other words, this c h a i n (gadget2) converts a p a t h measure (UP, DOWN) at vertex u into (UP + a + b, DOWN + a - b) at vertex w if we set a = C\ + C a n d b = C i - C . N o t e , t h a t the t r a n s f o r m a t i o n i n c r e m e n t s (UP + DOWN) b y 2a (just as gadgetl) a n d i n c r e m e n t s (UP - DOWN) b y 2b. cross-link at vertex 2 2 Chapter 2. Pessimistic Edge-Restricted Shortest Path ... B 7 B c,/ w '••A ... B B Q H X Figure 2.3: A gadget changing UP — DOWN by a given constant. With four vertices, u, vi, v and w, we can build a gadget* that combines gadgetl and gadget2 in parallel; that is, u, vi and w form gadgetl while u v and w form gadget2. In this way a path to u with measure (UP', DOWN) creates two paths with measures (UP+a, DOWN+a) and (UP+a+b, DOWN+ a — b) at w. 2 2 Let us define the gadget* with a parameter b more precisely. First, we create a gadget2 with u = (0,0, [0,H]), v = (H,0,[-Q,H - Q}) and w = (2H,0, [0,H]). In order to satisfy the condition C\ — C = b, Q should be set to b /(8H - b )/(4H - b )/2. Once the gadget2 is fixed, we have to choose the location for the vertex v\ of gadgetl such that C\ + C = 2C (this will make the parameter a for both gadgets the same). We place v\ at (H, y\, [0, H]), where yi = \J((C\ + C )/2) — 2H . Note that y\ will always be a positive real number since C\ + C is greater than 2y/2H (by triangle inequality, see Figure 2.4). We must also set H to be large enough so that we force any pessimistic path to alternate top and bottom points of the vertices as it goes through both gadgets. It can be shown that, if both \UP — DOWN] and b are at most some constant 3, setting H = 108 will force any pessimistic path to alternate the top and bottom points (See Appendix). 2 2 2 2 2 2 v 2 2 2 2 2 2.3 NP-hardness of pessimistic path If we connect N gadget*'s into a chain and choose appropriate (for example, powers of 2) values of b for each gadget*, we will create an exponential number Chapter 2. Pessimistic Edge-Restricted Shortest Path 8 H u. H H Figure 2.4: C\ + C is greater than 2 C = 2V2H 2 2 0 for any non-zero Q. (2 , in the powers of 2 case) of non-dominated paths from the first gadget to the last gadget. Any of those paths can be forced to be the only possible prefix of the optimal pessimistic path to an appropriately (see step 3 of the following construction) placed target vertex t, connected to the last gadget. We can now use that property to reduce SUBSET-SUM to our problem. N The pessimistic edge-constrained shortest path problem on uncertain terrain is NP-hard. T h e o r e m 1. Proof. Given a set 5, of N positive integers and a target sum, T, construct a shortest path problem instance, as shown in Figure 2.5, in the following way: 1. Set the parameter H of all gadget*'s to H = 20 Ylxes x 2. Construct a chain of N gadget*'s from a vertex s to a vertex w such that the parameter for the k-th gadget equals the k-th number in 5. Note that our construction guarantees that | UP — DOWN\ will never become greater than 2 ^ a ; for any of the path measures along the chain. I g S 3. Create a vertex t, and put it at distance H + T from w~ and at distance H — T from w , set t = t~ and connect t and w with an edge. + + Let A = J2k=i b °f ' f° gadgets. Feed the shortest path problem into a black box to get the shortest path distance between s and t. If the answer equals A + H, there is a way to make up the target sum using the numbers in 5, otherwise (you can only get a bigger answer) it is impossible. A shortest path of length A + H implies that there is a way to get to the last vertex of the chain via a path with a measure (A + T, A — T) or better. By construction, we can only guarantee path measures of the form (A + x, A — x) at the last vertex, w, of the chain. Clearly, the only x that can give us the required a k e t n e s u m t n e a s r a u Chapter 2. Pessimistic Edge-Restricted Shortest Path F i g u r e 2.5: S o m e r e d u c t i o n f r o m SUBSET-SUM. 9 O n t h e b o t t o m h a l f of t h e F i g u r e , t h e line segments that are shifted d o w n c o r r e s p o n d t o V2's, w h i l e t h e line segments that are shifted a l o n g Y - a x i s ( m o v e d u p o n the p i c t u r e ) c o r r e s p o n d to vi's. N o t e t h a t the gatgets o n l y look the same o n t h e p i c t u r e a n d a c t u a l l y have different p a r a m e t e r s b. distance is T. A l s o , because we s t a r t e d w i t h the measure (0,0) at t a n d o n l y {UP,DOWN) -* {UP - f a , DOWN f a ) a n d (UP, DOWN) -> (UP + a + b,DOWN + a-b), where 6's are t h e n u m b e r s f r o m a p p l i e d t r a n s f o r m a t i o n s of the f o r m S a n d A is t h e s u m of a l l a's, we must have f o r m e d T b y a d d i n g some elements of 5 . If T is a subset s u m of S, one c a n traverse t h e c h a i n f r o m t h e source b y following make up gadgetl if the c o r r e s p o n d i n g n u m b e r i n S s h o u l d T a n d gadget2 otherwise. C l e a r l y , the r e s u l t i n g p a t h n o t be used t o w i l l have l e n g t h A + H. 2.4 • Precision Issues T h e N P - h a r d n e s s proof, as presented, assumes t h a t we c a n p e r f o r m exact (infinite precision) a r i t h m e t i c o p e r a t i o n s s u c h as t a k i n g square root of a real number, i n constant time. I n real life that is n o t t h e case because we are r e s t r i c t e d t o use o n l y a finite n u m b e r of bits to represent each c o o r d i n a t e . W e have to s p e n d some n o n - c o n s t a n t , b u t still p o l y n o m i a l o n t h e n u m b e r of bits, a m o u n t of t i m e for every a r i t h m e t i c o p e r a t i o n . T o m a k e t h e p r o o f c o m p l e t e , we need to show how to choose the n u m b e r of bits t o use for every c o o r d i n a t e i n o u r r e d u c t i o n s u c h t h a t it still takes o n l y p o l y n o m i a l t i m e t o c o n s t r u c t t h e shortest p a t h p r o b l e m instance that solves a given subset s u m p r o b l e m instance. If we r o u n d a l l t h e coordinates t o have a finite n u m b e r of bits of p r e c i s i o n , we m i g h t n o t get t h e exact integer l e n g t h for some p a t h s g o i n g t h r o u g h t h e c h a i n . Chapter 2. Pessimistic Edge-Restricted Shortest Path 10 However, as long as our use of approximate coordinates does not change the length of any path by 0.5 or more, we can round the length of the shortest path to the closest integer and still have the solution to the subset sum problem. Every path fr<om s to t through the chain that we construct during the reduction will have exactly 2N + 1 edges. If each coordinate differs from its exact value by at most e then we introduce an error of at most 2e\/3 per edge or 2es/3{2N + 1) for the whole path. Solving 2e 3(2iV + 1) < 0.5 for epsilon, we get e < 0.25/(v 3(2A + 1)), which means that it is sufficient to store FS = 1 - log (0.25/(v 3(2Ar + 1))) = 3 + log (V3(2N + 1)) bits to represent the fractional part of each coordinate with sufficient precision. In addition, we need to store the integer part of each coordinate. The number of bits needed to store the integer part is IS = 1 + \og (H(2N + 1)). / v / r > 2 2 2 The size of the original subset sum problem is at least PS = N + log (iJ/20) because we set H = 2®J2xeS Note that \og (H/20) in the expression for PS is never negative. FS is polynomial on PS because it is polynomial on N. IS = 1 + log H + \og (2N + 1) is polynomial on PS because log H is polynomial on log (fl"/20) and log (2./V -f 1) is polynomial on TV. 2 x 2 2 2 2 2 2 It follows that the whole reduction is polynomial in space and time because we only need to do a linear number of polynomial-time computations to get the linear number of coordinates, each approximated up to a polynomial number of bits. 2.5 Exponential A l g o r i t h m Using the idea of (UP, DOWN) measures, we can generalize the Bellman-Ford algorithm to solve our problem. We start by associating a set of non-dominated path measures with every vertex. We initialize the source's set to contain only one path measure, (0, 0), while the rest of the vertices are initialized to contain empty sets. An edge relaxation step using the edge (u, v) takes every measure (UP, DOWN) from the set at vertex u and adds (UP*, DOWN*), where UP* = m&x(UP+\\u+ -v+\\,DOWN+\\u~ -v+\\) DOWN* = m a x ( £ / P + \\u+ -v~\\,DOWN + \\u~ -v~\\) to the set of measures at v as long as (UP*, DOWN*) is not dominated by an existing measure at v. By doing so, we will record the all the measures that correspond to shortest paths going through k or fewer edges after k-th iteration. If we relax all the edges - 1 times (the number of edges in the pessimistic shortest path can be at most | V | — 1), the sets of non-dominated path measures at every vertex are guaranteed to stop changing. At that point, we can compute the pessimistic shortest path distance to a vertex by looking at all the path measures in its set and choosing the measure that guarantees the shortest distance in the worst case. Note that a measure (UP, DOWN) guarantees the distance of max( UP, DOWN) in the worst case. 11 Chapter 2. Pessimistic Edge-Restricted Shortest Path We say that the algorithm is a generalization of Bellman-Ford only because it, just as Bellman-Ford, does | V | — 1 relaxation steps. That guarantees that we will consider every possible path that goes through at most | V | — 1 edges (possibly eliminating some dominated paths early on). It provides no polynomial bound on running time or memory usage since the number of non-dominated path measures associated with a vertex can be exponential, as we demonstrated earlier by the subset sum reduction. 2.6 Approximation A l g o r i t h m To construct an approximation algorithm, we limit the number of paths that can be stored at any vertex. Note that any path measure (UP, DOWN) at a vertex v will have the property: | UP — DOWN] < \\v — v~\\. We will allow every vertex to hold only Q measures. We introduce Q buckets of size 2| UP - DOWN\/Q covering all possible values of UP - DOWN and record only the "best" measure for every bucket. For example, if for some vertex v, \\v — v~\\ = z, then any measure's (UP — DOWN) will fall into the interval [—z, z]. For Q = 4, we would split that interval into buckets [—z,—z/2], (—z/2,0], (0,z/2] and (z/2,z\\ a measure (1,1) would fall into the second bucket, while (100,100 + z) would fall into the first. We decide which measure within the same bucket to keep by adding up its components and selecting the measure with the smallest sum. + + U-D =z U-D = -z Figure 2.6: Splitting some vertex's uncertainty range into 4 buckets. In Figure 2.6 there are four measures falling into the same bucket. Out of those, we retain only the measure ir and discard ip, 9 and p. Note that we can potentially discard a path measure whose path may be the prefix of a guaranteed shortest path. T h e o r e m 2. The approximation scheme that stores 1/e measures at every ver- tex (as described above) will find a path with guaranteed length at most (1 + 2e) 12 Chapter 2. Pessimistic Edge-Restricted Shortest Path times longer than the optimal path. Proof. Let's say that the optimal path goes through vertices v = s, v\, v , • • •, v — t with uncertainty ranges of ZQ, Z \ , Z , • •••, z . Call the measures of the prefixes of the optimal path {UP , DOWN ), (UP DOWN),... ,(UP , DOWN ). We claim that after iteration i the approximation algorithm introduces a path measure (UPi + e Y^l=i k, DOWNi + e Ylk=i k) better at vertex t>j. First, note that our claim is obviously true for i = 0. Assume that we introduced a measure ( W i - i + e y j f e = i k, DOWN i-i+eY?k~2\ k) ( better) at Vi-i at iteration i — A t iteration i, we relax the edge (vi^iVi). The relaxation operator applied to (UPi-i, DOWNusing the edge ( u i _ i , U j ) results in the measure (UPi, DOWNi) at the vertex Vi, where: UPi = max( UP^ + \\vf_! - v+lDOWN^ + \\v~_, - v+||); DOWNi = max( + ||w,t - v7\\, DOWN i-i + IK^ - v~\\); Because max is a linear operator, if the same operation is applied to a measure (UPi.x+C, DOWNi-i+C), it will get transformed into (UPi+C, DOWNi+C), for any constant C. For that reason, a measure (UPi-i+e ]Cfc=i k, DOWNi-i + 0 0 2 n n 2 0 u n z z n o r z o r z 1 z E I = \ -*fc) (UPi + 6^1=1 z ,DOWNi + e'£X} z ) at u . It is quite possible that we had a better measure at but that can only make the induced measure at Vi better. The induced measure, however, might not get stored at a bucket and, if stored, might be over-written later during the same iteration. In both cases, the measure that stays in the bucket at the end of the iteration i cannot be more than ez greater (in either component) than the originally induced measure because the value of UP + DOWN will be no greater than that of the originally induced measure. The worst case arises when two measures fall close to the opposite ends of a bucket and have exactly the same UP + DOWN. Note that the length of the optimal pessimistic path is at least z\/2 + z /2 + • • • + z /2 because, even if the vertices were infinitely close, the path can be forced to go through the further extreme point at each step (remember, we are looking at the worst case). Here is what we have: the length of the optimal path is at least (z\ + z + ... z )/2. The extra length due to discretization is at most e(zi + z + ... z ). • a t e w i l 1 i t l d u c e k 1 4 k t 2 n 2 2 n n Theorem 2.shows that we can utilize the Bellman-Ford-like algorithm described above to get a solution that is at most (1 + e) times worse than the optimal in 0(|jE||V|/e) time, assuming that each arithmetic operation takes a constant time. 2.7 Dijkstra-based Approximation A l g o r i t h m We can relax edges around a single bucket (as opposed to relaxing all the edges at the same time) to get a Dijkstra-based algorithm. Let (d£(v), d^(v)) be the path measure in the 6-th bucket (6 = 1... Q) at vertex v. In the beginning, we initialize all the buckets to contain measure (oo, oo) (except one bucket within , Chapter 2. Pessimistic Edge-Restricted Shortest Path 13 the source vertex, which we initialize to (0, 0)) and put them into a set S. At each step we choose a bucket 6 at a vertex v such that d£(v) + d^(v) is minimum among all the measures that are still in S. We then relax all the edges around v using the measure (d£(v), d^(v)), possibly improving some measures that are still in S, and remove the measure (d£(v), d^(v)) from S. Once (djj"(u), d^(v)) is removed from 5, no pair with smaller sum for that bucket can be discarded because the relaxation operator can only increase the sum of the pair. The resulting algorithm is somewhat simular to Dijkstra's algorithm on a graph with \E\Q edges and \ V\Q vertices (buckets). The algorithm finds a solution that is at most (l + e) times worse than the optimal and runs in 0 ( | £ | Q + |V|Qlog(|V|Q)) time. Note that, similar to what we often do in the Dijkstra's algorithm, we can terminate early after removing all the path measures of the destination vertex from S. 14 Chapter 3 Optimistic Edge-Restricted Shortest P a t h 3.1 Introduction and Basic Observations Having realized that the pessimistic version is NP-hard, we will look at the optimistic version of the problem. Now the problem is to find a path between two points such that, over all feasible terrains, its length is as short as possible. Within this formulation, the problem seems to become even more difficult — the best-case terrain no longer have to take a shape such that the optimal path traverses only the extreme points of a vertex's Z range. But, at the same time, if some optimistic shortest path traversal does not go through an extreme point, it should preserve its slope relative to the ground (XY-plane) as it passes through the vertex. Otherwise, it would be possible to find a consistent terrain on which the path is shorter, see Figure 3.1. AZ X —=»- Figure 3.1: The traversal can be made shorter if the angles are different. Note that even though the above example is really 3-dimensional and can, in general, be not planar, we can always flatten a path by rotating it around the Chapter 3. Optimistic Edge-Restricted Shortest Path 15 Z-axis at every vertex that the path goes through so that the edges of the path become co-planar with the XZ plane. 3.2 A l g o r i t h m design attempt A pseudo-straight traversal of a path <j> = v\, v , • •. ,«fc (a sequence of uncertain terrain vertices) is a sequence of points (in 3D) p\,P2, • • • ,Pk such that pi lies in Vi's uncertainty interval and the line segments Pi-iPi and Pipl+T obey the incoming—outgoing angle property for all i = 2,..., k — 1. We call a pseudostraight traversal that starts at an extreme point of some vertex a pseudo-straight ray. If it also ends at an extreme point, we call it a pseudo-straight path. 2 It follows from our earlier observation that any optimal path (assuming both source and destination points have a zero Z range) will be composed of one or more pseudo-straight paths connected at extremes of some vertices. The picture below shows some possible shortest path traversals from s to t. Note that the paths have been flattened. Figure 3.2: Any optimal path must be piecewise pseudo-straight. Keeping the properties of any shortest path in mind, the most intuitive attempt to solve the problem is to find all the pseudo-straight paths and treat them as the only edges that can be used to traverse the uncertain terrain. All that we need to do (provided we have pre-computed all the pseudo-straight paths) is to run any shortest path algorithm on the resulting graph (with 2n vertices). Unfortunately, not only can the number of pseudo-straight paths be exponential, but also the problem of deciding if there is a pseudo-straight path between any two given points is NP-hard. T h e o r e m 3. The problem of deciding if there is a pseudo-straight path between two certain (zero Z range) points on an uncertain terrain is NP-complete. Chapter 3. Optimistic Edge-Restricted Shortest Path 16 Proof. The idea is to use (again) a reduction from S U B S E T - S U M . If we construct an uncertain terrain in such a way that there is an exponential number of pseudostraight paths from a (zero Z range) vertex s to a (zero Z range) vertex g, then the slopes of those paths will be determined by the paths' lengths only. We can then add a vertex t (also zero Z range) and connect it to the vertex g in such a way that only the pseudo-straight paths with a certain slope (length) can make it through while remaining pseudo-straight. If we use the idea of the earlier NP-hardness proof of creating a chain such that every pseudo-straight path from s to g corresponds to a subset sum of a given set of numbers, we can decide the S U B S E T - S U M problem by reducing it to the pseudo-straight path existence problem. The picture below illustrates what a reduction may look like. The horizontal distance difference between going through a triangle using its top two sides and using its bottom side corresponds to a number from the set. Figure 3.3: A possible reduction from S U B S E T - S U M . More strictly, given a set S of N numbers and a target number T , we set H = 1 0 y j a ; and create a sequence of n triangles as in Figure 3.3. The base of each triangle will have length H. Vertices s and g are placed at s = s~ = (0,0,0) and g = g~ = (NH,0,1) (we use x,y,z order). All the vertices between s and g will have z = [0,1]. The greater-y vertex of the i-th triangle in the construction is placed in such a way that traversing the z-th triangle using it (the vertex) takes di units of horizontal length more than traversing the same triangle using its base, where di is the i-th number from S. For example, if the first element of S is d, we will set u = (H/2, \/2Hd + d /2, [0,1]). The vertex t is placed in such a way that the slope of the line gt is exactly 1/(NH + T) (note that we have ruled out cycles with our choice of H). A pseudo-straight path between s and t will exist if and only if some subset of S adds up to T. Same as in the pessimistic edge-restricted shortest path NP-hardness proof, we cannot represent all of the coordinates exactly, but we can approximate them with only a polynomial (yet sufficient) number of bits and set the uncertainty range of t such that only paths whose slopes are close to 1/(NH + T) can make it through. • xeS + + 2 Chapter 3. Optimistic Edge-Restricted Shortest Path 17 An important thing to notice about the terrain produced in the above reduction is that while deciding the existence of a pseudo-straight path from s to t is NP-hard, finding the optimistic shortest path from s to t is trivial. All you have to do is to follow the lower (smaller y) sides of the triangles to get to vertex g from vertex s in a straight line and then follow the edge (g,t). You don't really care if that path traversal is pseudo-straight, it will be an optimal optimistic edge-restricted shortest path even if it does not have a pseudo-straight traversal. 3.3 Discarding sub-optimal pseudo-straight paths In the previous example, we have an exponential number of pseudo-straight paths from s to g, but only one of them is potentially the prefix of an optimistic shortest path to t. All of the paths from s to g have the same starting and ending points and, out of those, only the shortest one can be optimal (or be a prefix of an optimal shortest path). The rest cannot be a part of any shortest path because they can be short-cut, i.e., replaced by a path with a shorter optimistic length. A pseudo-straight traversal pi, p ... pk of a path <f> = vi, v •. • is dominated if there exists a path <j>' from vi to Vk with a shorter optimistic length from p\ to pt. Note that the optimistic length from p\ to pk via <p' might not be realized by a single pseudo-straight traversal. 2 2 We already know that we can find the optimistic shortest path distance by running Dijkstra's algorithm on a graph that connects two extreme points of two vertices with an edge of length D if there exists a pseudo-straight path of length D between them. We also know that some of the pseudo-straight paths (the dominated ones) cannot contribute to any optimistic shortest path; so we will try to build a graph that contains all the non-dominated pseudo-straight paths and (possibly) some dominated ones. If we manage to build a graph that has the properties described above in polynomial time (that also implies that the size will be polynomial), we will be able to solve the optimistic shortest path problem in polynomial time by running Dijkstra's algorithm on that graph. 3.4 Polynomial-time Algorithm Proofs We will build a graph of pseudo-straight paths with the desired properties by finding all non-dominated pseudo-straight paths from one extreme point at a time. For that one extreme point, we will compute all the pseudo-straight paths with non-negative slope independently from the ones with non-positive Chapter 3. Optimistic Edge-Restricted Shortest Path 18 slope. Note that if we can find all the non-dominated pseudo-straight paths with non-negative slope that start at a given extreme point in polynomial time, we can repeat this 4|V| times to compute all the non-dominated pseudo-straight paths. The cone C((j>) for a path cp = vi,v , • • • ,Vk is the set of all pseudo-straight rays through <p starting at a specified extreme point e of v\. We will sometimes restrict cones to only contain rays with non-positive (or non-negative) slope. Starting at an extreme point e of some vertex v, we will grow cones of potential non-dominated pseudo-straight rays with non-negative slope (the non-positive case is symmetric). Each such cone will have the point e at its origin and two bounding points that limit the maximum and minimum slopes of the cone. We will store the horizontal distances to both bounding points and the bounding points (those must be extremes of some vertices) for every cone. We will also store the ending vertex / and the horizontal distance to that vertex for every cone. In other words, with each cone we store a 7-tuple (e,u,l, f,d(u),d(l),d(f)), where e is the origin, u and / are upper and lower bounding vertices, and d(f) is the horizontal distance to vertex / from e. We call the first four entries of the 7-tuple the label of the cone. We call two cones identically labeled if e,u,l and / are the same for the two cones. There might be no lower-bounding point for some cones (because we restrict ourself to nonnegative slopes). In that case we set the lower bounding label I = 0. 2 Figure 3.4: Growing cones starting at the lower extreme of v. There are 4 different cones in Figure 3.4. The cones ending at the vertices n, m and p are very simple — they all have their bounding points belonging to their final vertex. The cone that ends at the vertex q has its bounding points as p and p~~. + 19 Chapter 3. Optimistic Edge-Restricted Shortest Path We will call a cone dominated if every pseudo-straight ray belonging to the cone is dominated. The lemmas 1 through 4 are dealing with cones restricted to non-negative slopes. L e m m a 1. If two cones are identically labeled then either one of them is domi- nated or they are exactly equivalent (if we continue growing the cones, they will be indistinguishable). We will use the following lemmas to prove Lemma 1. L e m m a 2. If there are two identically labeled cones and they have different distances to the upper-bounding point, then the cone with the greater distance to the upper-bounding point is dominated. X Figure 3.5: All cone two rays above the dotted ray are dominated. Proof. Figure 3.5 shows two identically labeled cones, C\ = (e, u, I, /, d\(u), d\(l), di(f)) and C = (e,u,l,f,d (w),d (/),^(f)), whic have been flattened. C\ is the cone that has shorter distance to u; it is bounded by the pseudo-straight rays TOP and BOTTOM (TOP and BOTTOM bound cone C ) . The two thick lines indicate the subset of the Z-range at vertex u that lies within both cones. There are two lines since the the projection of the Z-range at vertex u occurs at two different X-coordinates, d\(u) and d (u). Since d\(u) < d (u), the thick lines indicate points in the Z range at u that can be reached via pseudo-straight lines from C\ before any pseudo-straight line from C . Even though this might look like a very specific example, any two identically labeled cones will have an overlapping region at the upper bounding vertex. It should be clear that the cone whose distance to the upper bounding vertex 2 x 2 x 2 2 2 2 2 2 2 Chapter 3. Optimistic Edge-Restricted Shortest Path 20 is greater will always have that region dominated. The only pseudo-straight rays in C that are not dominated in this way lie below the dotted ray. Note that the dotted ray will never have slope greater than the ray BOTTOM\ (by construction). That implies that if any ray of C is still not dominated, then the distance to the lower-bounding vertex is greater for C . If there is no lowerbounding vertex for both cones, then we are done. 2 2 2 z(Cl dfl) df) Figure 3.6: The rays in C below the dotted line are dominated. 2 Figure 3.6 shows that any ray of C that lies below the dotted line can be short-cut. Consider the ray eq within C , where q is a point in Vs uncertainty interval. All we have to do is to go from e directly to the lower-bounding point l~ via C i and, once we reach the vertex, w, that precedes I at the point p of IU'S uncertainty range, go to the destination qi in a straight line. Note that qi and q are the same point within I's uncertainty interval. Because (w, I) is an edge of the terrain, this creates a traversal composed of a pseudo-straight ray and a pseudo-straight traversal of edge (w, I) that dominates the corresponding ray in C . • 2 2 2 2 2 2 L e m m a 3. If there are two identically labeled cones whose distances to the upper-bounding point are the same, but the distances to the lower-bounding point are different, then the cone with greater lower-bounding distance is dominated. Proof. Note that in this case all the rays lying below or at BOTTOMi will be dominated by the same reason as was shown in the second part of the proof to Lemma 2. For the rays that have greater slope we can use a similar technique, see Figure 3.7, ||e — p\\ + \\p — q\\\ is always shorter than ||e — 92II- d L e m m a 4. If there are two identically labeled cones and they only differ in the distance to their final vertex, then the cone with the longer distance is dominated. Chapter 3. Optimistic Edge-Restricted Shortest Path 21 d(f} d(fA Figure 3.8: Two cones that only differ in their distances to the end point. Proof. On Figure 3.8 the final (identical) vertices are named f\ and f for the two cones. This case is almost identical to the previous two, \\e — p\\ + \\p — q\\\ is always shorter than 11 e — qr 1j. • 2 2 It should be clear that two identically labeled cones that have exactly the same parameters are equivalent. Lemmas 2 through 4 together prove Lemma 1. Chapter 3. Optimistic Edge-Restricted Shortest Path 3.5 22 Polynomial-time algorithm Lemma 1 leads immediately to a polynomial time algorithm. We can compute a graph that contains all the pseudo-straight paths we need (there is only a polynomial number of them) by expanding cones of pseudo-straight rays from every extreme point (both non-negative and non-positive slopes). Algorithm 1 shows how we expand an extreme point e assuming that we are looking for non-negative slopes. The function dominant(C\, C ) returns C\ if C\ dominates C> and returns C otherwise. 2 2 Algorithm 1 Single Extreme Positive Slope Extention Algorithm Let A be an associative array of cones indexed by cone label. Input: G = (V, E), extreme point e of some vertex v € V. Initialize A to contain C((v,r)) for all edges (v,r) € E. for i = l,i< \V\ do A' = A (iteration starts) for all C £ Ado Let / be the final vertex of C. for all edges (/, r) £ A d o let C be C extended to r. if C" ^ 0 t h e n let (e,u,l,r) be the label of C A'[(e, u, I, r)] — dominant(A'[(e, u, I, r)],C) e n d if e n d for e n d for A = A' (iteration ends) e n d for. For every extreme vertex e and for either non-positive or non-negative slope, we use Algorithm 1 to calculate a set of pseudo-straight paths that contains all non-dominated pseudo-straight paths starting at e. We add these paths as edges to a graph G . We then run the Dijkstra's algorithm on G to find the edge-restricted optimistic shortest path on the uncertain terrain. ps ps We can find the edge-restricted optimistic shortest path on an uncertain terrain G = (E, V) in 0(\V\ \E\) time. T h e o r e m 4. 4 Proof. We run Algorithm 1 0(|V|) times. Algorithm 1 does 0(|V|) iterations, each of them taking 0 ( | V | | £ | ) time, assuming |V| < \E\. Fetching the pseudostraight paths after Algorithm 1 is done takes 0 ( | V | ) , as we only look at all possible cone labels that originate at e. The final application of Dijkstra's algorithm takes 0 ( | V | ) time because G contains 0(|V|) vertices (extreme points). That adds up to 0 ( | V | | £ | ) total running time, dominated by the time required to construct G . • 2 3 2 ps 4 ps Chapter 3. Optimistic Edge-Restricted Shortest Path 3.6 23 Handling Uncertain Source and Target We can generalize our approach to handle uncertain source, s, and target, t, vertices. Note that any optimistic path to an uncertain vertex t whose traversal does not end at a vertex's extreme point should be co-planar to the XY-plane at the point where it reaches t. That means that the pseudo-straight ray that forms the last link of the traversal has zero slope. All such zero slope pseudo-straight rays will belong to a cone from the set A that we get after running Algorithm 1 from some extreme point. We can look at all of the pairs of extreme points (s , t') and, assuming that the optimal path goes to s' from s and comes to t from t' along pseudo-straight rays with zero slope, find the optimistic edge-restricted shortest path between s and t. We allow s' = t'. Note that there will always be a solution that includes at least one extreme point. 1 During the construction of G we computed all the pseudo-straight path distances as well as all the zero-slope pseudo-straight rays, so we can compute all-pair shortest paths between extreme points in 0 ( | V | ) time. That means that the running time of our generalized algorithm will remain unchanged at 0 ( | 1 / | | £ | ) since trying all possible (s',t') takes only 0(\V\ ). ps 3 4 2 24 Chapter 4 Conclusions and Future Work 4.1 Edge-Restricted Problems We have shown that the pessimistic edge-constrained problem is NP-hard. The same proof can be used to confirm Chris Gray's result for the pessimistic unrestricted case. Any edge-restricted shortest path problem can be reduced to an unrestricted shortest path problem by replacing each triangle with 3 new triangles: we introduce a new vertex (with a large Z-coordinate) in the middle each triangle. That forces any shortest path to stay off the face, effectively making the problem edge-restricted. It also seems that many real terrains will be "hard" instances. The difficulty of the problem comes from the potentially exponential number of non-dominated path measures. If there are an exponential number of paths between two points of a terrain and they have roughly of the same length (measured in XY plane), the chance is, most of those paths' measures will be distinct (it would be naive to expect that two different paths will produce exactly the same measures) and most of those paths will be non-dominated (because they are roughly of the same length). An almost flat terrain with little noise will exhibit such properties. In fact, it is possible to do an NP-hardness construction similar to the one used in the Chapter 2 on a terrain that has a uniform grid as its XY projection, just by varying uncertainty ranges and Z-coordinates of the vertices. The pessimistic assumption is probably not a very good one. Imagine a uniform sequence of vertices, with the same Z-coordinates and uncertainty ranges, aligned in a line, with edges between every pair of neighbouring vertices. The length of a pessimistic shortest path though such a chain will increase, indefinitely, as we increase the number of intermediate vertices. In other words, we will be getting a longer path length as we get more measurements of the terrain, unless we manage to decrease the uncertainty ranges at the same time. We presented a polynomial time algorithm for the optimistic edge-constrained problem. The algorithm was not designed for performance, but rather to show that the problem can be solved in polynomial time. There are almost certainly some faster algorithms to be found. Chapter 4. Conclusions and Future Work 4.2 25 Unrestricted Problems Both optimistic and pessimistic unrestricted shortest path problems are NPhard, but what about approximating them? We cannot introduce too many new uncertain vertices to reduce the problem to an edge-restricted one because, as we mentioned before, it increases the length of the optimal path if we add more vertices without decreasing uncertainty. Another difficulty is that, for any approach to the unrestricted case, working locally is not sufficient. If you cross one triangle in the beginning of your path, you might restrict some of the triangles that you will be visiting later. Figure 4.1 shows that at the time when we traverse the triangle B, we would have to remember about restrictions we have put on the vertex v when we traversed the triangle A. That makes it very difficult to come up a reasonable measure for a path because that measure would have to capture not just the possible lengths of the path, but also how that path has restricted our choice of feasible terrains. Figure 4.1: Triangles A and B are both dependent on the vertex v. It might look that the optimistic unrestricted problem can be approximated by finding (approximately) a path from source to sink in 3D between the lower and the upper terrains and then choosing the positions for the vertices of the optimal terrain such that the path lies on it's surface. Unfortunately, that does not work - some of the paths (even some of the straight paths) that lie in between the lower and the upper terrains are not be feasible. Look at the Figure 4.2. It is quite possible that the shortest path between some two points, s and t, is a straight line that lies completely in between the lower and the upper terrains and goes through both point a and point b. The line segment ab can be arbitrarily steep, while the slope of the triangle vup is bounded. Chapter 4. Conclusions and Future Work 26 Figure 4.2: The slope of the line ab can be arbitrarily large as both a and b are getting close to v. That means we will not always be able to find a feasible terrain that contains our shortest path in 3D. It is unclear how to bound the resulting error to get an approximation algorithm for the optimistic unrestricted shortest path problem. 27 Appendix A Proving the constant factor of 10 for the gadget* We will prove that the pessimistic shortest path traversal through gadget* must alternate the top and bottom extremes of the vertices as it goes through, as long as the parameter b and | UP — DOWN] at the vertex v are both upper bounded by 8 and H is set to 10/3. Since | UP - DOWN] < 8, we need only show that the alternating traversal is always longer than any other traversal by at least 8. First, look at the gadget2 (Figure 2.3). We label the lengths of the traversals with (siS2S$)b = d(u v ) + d(v w ), where b is the parameter used for gadget*. We need to show that for any b € [0,8], Sl S2 S2 S3 (+-+)& > max{(+++) , (~++)b, ( +)b} + B and (A.l) (-+-)b )b} + P (A.2) b > max{(++-) , (+ ), ( h b By symmetry, (+ ) = ( +) , () = (+++)(,, and (++-) = (-++)(,, and since C\ > C , (H l-)& = 2Cj > 2C = (—H—) - Thus, it suffices to prove (A.2). The maximum in (A.2) is achieved by (H ){, since b 6 b 2 (++-)& = B + C <C]+B 2 ( 6 2 = (+—) b because C > C b x ) = 2B < Ci + B = (+—) b x which leaves us with a single inequality, (—I—);, > (H (-+-)b ~ (+—)b 2 because C > B, b ){, + 8, to prove: = 2C - (Ci + B) 2 = 2y/(H - QY + H 2 > 2y/(H-8) 2 (V{H + QY + H + ^JH + Q ) 2 2 2 + H - (y/(H + 8) + H + ^JW + 8 ) 2 2 2 2 = /3(2\/l81 - V22T - %/ioT) > 8, where we have used the fact that Q = b/2^{%H - b )/{4H - b ) 2 2 2 2 < /?,/800/1596 < 8 for b e [0,8]. Now look at gadgetl (Figure 2.2). By symmetry, we only need to show Appendix A. Proving the constant factor of 10 for the gadget* 28 that 2 C - 2D > B: C - D > C 0 -- DD = V2H - \JC 2 - H 2 (see Figure 2.4) (because••C >C > V2H - XJC\ - H 2 l = (C + C )/2 since C > C ) ¥ = V2H - y/(H + Q) + 2 H -H 2 2 = V2H -{H + Q)> (3(^200 - 11) > 3/2. 1 2 x 2 29 Bibliography [L] Chris Gray, "Shortest Paths on Uncertain Terrains," Master's thesis, (Vancouver, B C , Canada: University of British Columbia, August 2004). [2] John Canny and John Reif, "New lower bound techniques for robot motion planning problems," Proceedings of the 28th Annual Symposium on Foundations of Computer Science, (Los Angeles, C A , USA: I E E E Computer Society Press, October 1987): 49-60. [3] Joseph S. B. Mitchell, David M . Mount, and Christos H. Papadimitriou, "The Discrete Geodesic Problem," SIAM Journal on Computing, (Volume 16 Issue 4), (Society for Industrial and Applied Mathematics, 1987): 647-668. [4] Andreas Kaab, "Monitoring high-mountain terrain deformation from repeated air- and spaceborne optical data: examples using digital aerial imagery and A S T E R data," ISPRS Journal of Photogrammetry & Remote Sensing, 57:3952, 2002.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Optimistic and pessimistic shortest paths on uncertain...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Optimistic and pessimistic shortest paths on uncertain terrains Kholondyrev, Yury 2007
pdf
Page Metadata
Item Metadata
Title | Optimistic and pessimistic shortest paths on uncertain terrains |
Creator |
Kholondyrev, Yury |
Publisher | University of British Columbia |
Date Issued | 2007 |
Description | In the Uncertain Terrain Shortest Path problem we consider a triangulated terrain with vertices having uncertain Z-coordinates: each vertex is denned as a (x,y,z―,z+) tuple, where the z coordinate of a vertex is uncertain and can be anywhere in the range from z― to z+. We are looking for a path (defined by its projection to the XY- plane) such that, over all possible terrains, the path is as short as possible. We look at both pessimistic (terrain arranges itself to maximize the length of the path that we choose) and optimistic (terrain takes the state that minimizes the length of our path) scenarios. We restrict ourselves to walk only along the edges of the terrain. The unrestricted problem (when we are allowed to walk on the faces of the terrain) has been proven to be NP-hard in both pessimistic and optimistic scenarios. We prove that the edge-restricted pessimistic problem is NP-hard by providing a reduction from the SUBSET-SUM problem and give a polynomial time algorithm for the edge-restricted optimistic problem. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2011-03-17 |
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.0052001 |
URI | http://hdl.handle.net/2429/32577 |
Degree |
Master of Science - MSc |
Program |
Computer Science |
Affiliation |
Science, Faculty of Computer Science, Department of |
Degree Grantor | University of British Columbia |
Campus |
UBCV |
Scholarly Level | Graduate |
Aggregated Source Repository | DSpace |
Download
- Media
- 831-ubc_2007-0454.pdf [ 1.45MB ]
- Metadata
- JSON: 831-1.0052001.json
- JSON-LD: 831-1.0052001-ld.json
- RDF/XML (Pretty): 831-1.0052001-rdf.xml
- RDF/JSON: 831-1.0052001-rdf.json
- Turtle: 831-1.0052001-turtle.txt
- N-Triples: 831-1.0052001-rdf-ntriples.txt
- Original Record: 831-1.0052001-source.json
- Full Text
- 831-1.0052001-fulltext.txt
- Citation
- 831-1.0052001.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-0052001/manifest