Welcome to this course on geometric algorithms. When was the last time you used a geometric algorithm? While you think about the question, let me find coffee. So, here's a map of Eindhoven, and these are the coffee places on the map. So, Let's first have a look which coffee place is nearest. Okay. By the way, while walking here I actually saw a very nice coffee place, was that I crossing? So, let me overlay my track with a map. That's it. So, what we see here is that we're actually using geometric algorithms all the time in everyday life. Geometric algorithm also play a large role in applications. For instance, geometry processing and geometric modelling are important for computer graphics and computer-aided design. Geographic data by nature is spatial and therefore geometric, and also in robotics for what motion planning, algorithm play a large role and there are many more applications. So, if you look at the problems that we encountered while searching for coffee, the first problem was, from all coffee places around the world to find those on my map. So, in terms of geometry, we have points in two-dimensions and we are interested in finding the points with inner query rectangle and that's called range searching and will be the topic of module three. Now, if we think of the problem of finding the nearest coffee place, so what we would like here is a map showing for every location the closest coffee place. This results in a partition which was called the Voronoi Diagram and that will be topic of module two. Finally, I wanted to find the intersections between a track and the road network. So, let me discuss this by different application. So, this good mouse was tracked with GPS and the question is, where did this mouse cross the road? This will be the topic of this module. So, here's an overview of the course. The geometric problems that we're going to look at is the line segment intersection problem, Voronoi diagrams and Delaunay triangulations and range searching. We will use this also to introduce several algorithmic techniques for one plane sweep, then Randomized Incremental Construction and finally Geometric Divide and Conquer. So, for the remainder of this lesson, we will see a simple algorithm to find Line segment intersections and discuss shortcomings of that algorithm. So, we had this problem of finding the intersections of the track of this moose and the road network. The first thing we need to do is to extract the geometric problem. So, the geometric problem is given a set of line segments, report all the intersections between line segments. We are ignoring here the fact that actually we are only interested in the intersection between road, segments and segments of the track but for simplicity, let's simply report all the intersections. We are dealing here with simple geometric objects, so line segments in this case and then geometric algorithms generally will be dealing with points, lines, circles and other objects which can be described by a constant number of parameters, and then we say they have constant description complexity. If we do computations between a constant number of objects was constant description complexity, that will also take constant time. For instance, we can now simply assume that computing the intersection between two lines segments can be done in constant time. So, here's our problem. Given a set of n line segments, we plot all intersections. Here is a first simple algorithm. We simply take every pair of line segments, check whether they intersect or not and if so, we put the intersection. What is the running time of this algorithm? So, checking for two line segments where they intersect, we said we can do that in constant time also. We are ploting takes constant time. So, we do this for a quadratic number of pairs. Over all, the running time for this algorithm will be quadratic. Is this a good algorithm? So in terms of worst case complexity, it could be that all line segments intersect. So, in that case, we have a quadratic number of intersections and therefore we cannot have an algorithm that runs faster than in quadratic time. But if we think of mouse and where it crossed the road, we would expect much fewer intersections. Then, we would likely to have an algorithm that in this setting, runs faster. So, what we would like to have, is an Output-sensitive algorithm. So, the running time of the algorithm should not only depend on the input complexity, but also on the complexity of the output. We've seen various geometric problems, also various applications of geometric algorithms and on the line segment intersection problem, we saw first simple algorithm but also noticed that what we would actually like to have is an Output-sensitive algorithm. I wrap up every lesson with showing the sources used in that lesson and also a reference to a book on more on the problem studied.