# Mod-01 Lec-01 Introduction  problems It is going to be somewhat different and more challenging than some of the algorithms you have implemented in other courses, especially you may have implemented search algorithms, standard computer algorithms like sorting, some graph algorithms, m s t The main difference between implementing a geometric algorithm this cemetery algorithms is that you are dealing with points in Euclidian space when therefore; you have dealing with real numbers. So, once you deal with real numbers which are actually very unreal because the computers do not have real numbers, then you have to struggle with issues like over flow, under flow, stability; all those things, the things that you normally learn in numerical analysis course, something that will encounter when you try to actually implement the algorithms that we will design in the developing the class And to tackle those problems, you know of to some handle those problems, you will need to think beyond just the aspects of the algorithms, but also see how the points will be represented in, what kind of precision we need etcetera So, those also will become issues and these are serious issues when people try to implement geometrical algorithms In this course, we are not we are going to kind of avoid those issues for most parts, may be once I will maybe elsewhere a lecture to just trying to give you an over view of what are the kind of problems that arise when you implement geometric algorithms, but the theory of actually trying to implement algorithms in a way where you minimize errors, I said is very similar to numerical computing and that requires completely separate discussions In fact, I would go as far as to say although this area is about a that a more than thirty years old now, but I think people are still trying to come up with a clean model of implementing geometric algorithms So, it is very much a research topic you know how to do the clean implementation given that you have to handle real numbers. Anyway so, outline of what I expect from you in terms of assignment. So, there will be two or three written assignments and I would say one or two programming assignments depending you know I have not decided yet how big, but they will take some time. I will probably limit myself to one midterm exam rather two minus and we will have a major exam. So, I haven’t quite given much thought to how the marks we will distributed, but let us say, I am I am just saying, let us say. So, have minors sorry let say midterm actually not a minor, in the midterm you have a major, you have assignments. So, there are three components and I am saying assignments, there will be some basic theoretical assignments in problems and some programming assignments. So, let see. So, maybe I will do something like perhaps something like this looks let us say, twenty-five, forty and may be twenty and fifteen; that decides up to two hundred. So, let say, this is about the rough distribution that that we have in the course. I have described the syllabus in details in the in the course page I do not want to go through it because most of the terms would not make sense today. Rather I would give you start with an example of a geometric problem. Also let me also clarify that I said computation geometry is about designing and implementing algorithms for problems that are geometric in nature and that is quite distinct from trying to prove geometric theorems automatically So, that as that is completely different area That is done by also there is a community of people doing that who do research in theorem proving and actually they have done impressive work, but like any other theorem proving exercise, this actually trying to prove a new theorem is extremely hard and certainly not feasible algorithmically for most of the algorithms So, people are struggling with that, but just to even get that frame work going you know it is a very impressive achievements, but that is done again by I am saying that people in the theorem proving community So, we are not going to try to prove theorems using computers. We will try to prove the theorems by hand. Whatever we prove about the algorithms are the running time the analysis we will do by hand Feel free to ask me any questions if I miss something that is very relevant. So, let me proceed with an example to illustrate in what kind of what geometric problems mean to us in what kind of techniques people try to use So, let me take up a very natural example like which is essentially a navigating. So, navigating in a geometric environment which is basically that you have given. So, you can think about this room as a geometric environment where there are all of us can be describe with some geometry primitives So, the furniture, the people, the cameras; whatever. So, this entire that geometric description of this room is what a mean the geometric environment and then we may want to move some object from one part of the room to the other part. That is what a mean by navigation And of course, this navigation has to be done in a way such that it is not allowed to pass through solid objects. So, you can pass through the air, but you cannot pass through a solid object. So, you cannot. So, if you collide, you can only set of at best you have to circumvent that object So, to make things easy and for also you know from the point of view of we have to draw So, let me draw the 2 dimensional log of this So, suppose I take the projection of this room on the plane. So, what does it look like? So, it could look like. So, it could look like, we have his people sitting on this like this here, some rows of this here, again other row and here is where I am seated and we want to move let us say, let us say to begin with, it is just a point, which is easier because it has zero width. So, suppose I want to move a point and it may indicate that by cross, from this point to let us say to this corner of the row. This is the starting point start and this is the end. So, this is the game well. So, there are various ways of doing this. Let me choose different color. So, start walking, start walking you I cannot I have to way around this. So, I go, I go here may be I have to go around this. Alright I found a path So, this is how I have navigated from the start to end. Someone else we decide to do in some other way. So, here, there we will go, that is also a legal path. Someone more may want to do this way and this is not a legal path. It just crashes into furnaces, we cannot do that, one has to go around So, what is observed about these paths is that you can have several ways of navigating from this starting point to the end point without colliding into the obstacles, but which is the way that you are going to choose? Suppose you know I have write a program. So, I can certainly describe these objects in some way, these are let us say for simplicity all these are rectangles. So, how do I move this point and how do I write a program that moves this point from the starting to the end point that goes around obstacles. So, on what on it is to choose a random path, even to choose a random path I have to ensure in the minimum that it does not collide with the with the obstacles So, somehow we need to capture that fact and the one difficulty or let us say one initial difficulty is that the possible number of paths seems to be just too large. In fact, the possible numbers of paths that will infinite because I can take any legal path here and may just decide to just perturb this little bit just move it like this and that is it So, that is another legal path. So, with every small perturbation of one path, I can get another legal path. So, I am dealing with an infinite number of paths and this is what sets it to path from a path problem in graphs So, if I have a graph. So, suppose I have a graph like… So, I could have lots of edges in this graph does not matter I can have lots of edges this. This starting point and this is the ending point, but still the number of different ways I can move from the starting to the end point is finite. So, I could do like this, I could go like this, but again it just a infinite number and how a large it is it is till finite It may be exponential that it suppose I have n vertices there could be you know it could have you know this is a very common example to show that the number of paths could be exponential So, you could have these choices at every point, this is the starting point, this is the end point. Every point you have two possibilities to pursue and in if there are n such rhombus, you basically have 2 to the power n possibilities to provides, but still it is a finite number, it’s exponential, but still finite Here if a parameter is my problem by seeing that have n obstacles, I have n obstacles, I were knew obstacles, I cannot say that I have less than 2 d power n paths. It is not true is not true in the case of geometry So, the first difficulty that we will face in trying to model any geometric problem is to somehow cut down the number of possibilities something that we can deal with. You cannot deal with infinite numbers So, somehow we need to restrict that. So, we need to base on observations. So, let us try to make certain observations about this particular problem navigating a point from the start to the end through these obstacles and when you do that we must also may be just define some kind of a more clean objective function. It is not simply about let us say going from a start to the end point, but let us say we would like to economies something You know may be we would like to economies space, sorry economies time or the cost of travel somehow that. So, let us say. So, in the shortest path probably may try to we have actually a weights on the edges and we try to seek a path that will minimize the sum of the weights on the edges of the path So, similarly here we can think about the solve trying to solve the shortest path problem between start to end and the national notion of the distance here is equidistance. So, whatever is the path, I will just consider that well I mean strictly speaking, you have to prior define measures because it may be it can be any kind of path, but you understand what I mean. Basically the total length of the path is what we would like to minimize with. That you could go to do of the object function. The other objective function could be that I really do not care as long as it is some path, but here if you can let us try to solve the some more interesting problem, we want to actually minimize or find the shortest path find shortest path .So now, it becomes a better defined problem And when you talk about shortest paths. So, the shortest path between two points in a Euclidean space is what. A straight line segment right, well great. So, at least we are getting somewhere, but the straight line segment between this probably passes through or collides in to some obstacles. So, that does not seem like the solution to this problem, but it is a good starting point. So, this red line is not possible, but then we would like to be as close to this is possible. That that is basically what we give as a shortest path in tutorial shortest path and if that is so, then one way to think about it is that, suppose this red segment is like a rubber band that we can bend around the obstacles So, if it is allowed to bend, then this you know it would not pass through the objects, but my first attempt could be I bend it something like this. So, there are these two bends and that seems to set of be fairly close to the straight line, but do you think this is a shortest path why. Because that shortest path between the starting point and the first bend point will be a straight line Great. So, is this an intrusion you use basically because you live in the geometric world? You know exactly it is not like if I live in a graph world, you would not be able to figure out, but you were in the geometric world So, to quickly figure out that something like something like you know. So, this bend, let me blow this up. So, if I blow that up, it is like you have a rectangle and we are talking about a path. So, we do a path like this Now what you are saying is that, this bend that you took, why did you take this bend because if I take something like this, this the doted should be a short cut of these two bends and why is that? What is the property that you are using; the triangle inequality exactly. So, you are using triangular inequality. So, you already have a kind of a proof that this dotted line, it should be shorter than this plus this and therefore, the one that we had before, the solid line cannot be the shortest path So, this is another observation that then we will clean up this shortest path that we are trying to find between the start and the end point should have this property that one is that can it consists of curves, can that path have some curves like this No same thing, if there is a curve we know that the shortest distance between two points is straight lines I am going to short cut the curve. So, there is no, so, we do not have to deal with any curves. So, we can leave it ourselves to only straight lines and therefore, the shortest path between the starting and the end point is going to be a piece wise linear curve essentially piecewise linear, now, even that piecewise linear, we have further properties that we do not have to look for things like this Where are the bends, where can the bends occur the bends can only occur, where, see here there was a bend basically when we collide with an object,, but then that bend is not a bend that should appear in the shortest path the bend can be moved or pushed till it meets a corner point Right in other word what I am saying is this red line; let me draw a dotted line again So, this red line instead of this solid line we should be probably looking for something like this of course, that may crash in to other thing. So, the places that it can bend are only the corners. So, in other words we blew this up you know if I am trying to get from let us say here to here around just suppose we had only one obstacle. So, this straight line when you actually distort and think about it like a rubber band it is going to be basically bend here So, the bends only going to be appear at the corner points and we are actually argued in kind of proved it. So, with these two observations in mind now we can business why. So, now, I can actually model this problem, the shortest path problem as a graph problem where the edges or the vertices are defined by the corner points of the obstacles the four. So, these are rectangular obstacles. So, I can consider the corner points, the rectangles as vertices and the edges must be basically are defined the piecewise linear path. So, the edges must be between two such vertices because there cannot be any other bends, but then there is this thing that not all of them of a legal edges because some. So, the straight line segment between this and this these two points is not legal between it actually crashes in to an obstacle But that again we can verify that you know we will try. So, suppose as I said there are n obstacles, which means that there are 4 n corner points or which I am basically calling the vertices. So, 4 n corner points and then out of the 4 n choose two segments there are some we will define some legal edges that do not crash into obstacles. So, clearly the number of… So, number of vertices. So, if you go back to the graph terminology the number of vertices is 4 n corner points number of edges is bounded by 4 n choose to. So, about let us say about some order n square So, if this is or let me use v square etcetera So, now, you are in the in the graph world and once we are in the graph world some of you find it easier to deal with So, we have a graph with number of vertices I am saying 4 n vertices where n is the number of obstacles. So, this is a special case of course, we have the obstacles all rectangles essentially the corner points. So, all they have obstacles will be the set of vertices, and the number of edges is less than or let us say I will use big o notation, is big O of n square and you still need another parameter which is basically the weights on the edges So, the weights on edges should be what, Euclidean distance. So, the Euclidean distance between the end points let us say v 1, v 2 and every such end point or corner point, v 1 is defined by a coordinate pair. So, there is some x coordinate of v 1 and there is some y coordinate of v 1 So, when I am saying refer to the Euclidean distance between the end points v 1 and v 2, essentially we are finding the distance between and the corresponding v 2 and y v 2.So the Euclidian distance between these two points should be the weights on the edges So, there is a formula for the Euclidean distance; the square root of the sum of the difference of the… So, x v 1 v 2 minus v 1 square plus y v 2 minus y v 1 square the square root of that And if you do not like square roots you may not even want to do the square roots you compute the shortest paths in this squares because after it is just a relative computation you want to know the shortest path you may not want to know the exact distance. So, we are happy to find a shortest path. So that is it. So now, you are you done your favorite shortest path algorithm on this graph. So, from that space of infinite possible paths you got it down to a very finite description some something like that we are familiar with it in terms of graphs and then you run your shortest path algorithm algorithm can be done because actually all the distance are non-negative So, any questions till now I mean. So, what did we do, we I mean if you want to write a formal proof whatever I have said can be    