* Tuesday, January 15:

Introduction. General information about the course, overview of its contents, its assignments, and choices of the projects to be done by the students etc. Please note that there will also be a written exam after the course, without the book nor notes.

All participating students were encouraged to send email to the teacher, including their name and other contact information. In this or in a later email you may also include information about your special interests and wishes related to the course, possible preference for subjects to work on in your small projects, and possible formations of groups with other students.

An overview of the chapters of the book, especially the first nine chapters, was given.

* Friday, January 18:

Convex hulls, Graham's scan (the efficient algorithm discussed in Chapter 1), Jarvis's march (the algorithm discussed in exercise 1.7), related problems with imprecise numerical computations.

* Monday, January 21:

Solving the exercises of Chapter 1. We went more or less through all the exercises at various speeds, except for exercise 1.10e (for the case when the circles have different radii), which we leave for the beginning of next problem solving session next Monday (on January 28).

Exercise 1.6b:
In this exercise it is implied that the vertices of the input polygon P are given in clockwise (or counter-clockwise) order as encountered when "walking" on the perimeter of P. We can use this given order to run a linear-time convex algorithm, rather similar to "Graham's scan", starting at, for example, the leftmost vertex of P, and following clockwise the edges of the polygon. When we arrive at the rithmost vertex of P, then we are done with computing the upper hull. When we process a new vertex v on the way, we update the upper hull accordingly. When updating the upper hull, all vertices which we remove are chopped off from the right end of the upper hull constructed so far, and therefore they are found and removed in constant time per edge. This ensures linear total time. (More details were commented during the problem solving session.)

Exercise 1.8a:
A way proposed by a student is to compute, for example, the upper common hull of the two convex polygons would be to extract the upper hulls of the two respective polygons in sorted order, according to their x-coordinates, then merge the two sorted lists to obtain one common list of vertices sorted according to x-coordinates, and then use Graham's scan to compute in linear time the common upper hull.
Another way would be to start by inserting a "bridge" connecting the two convex polygons, and then successively remove concavities on the perimeter by "filling in" triangles, until we arrive to the two tangents of the two convex polygons which are part of their common convex hull. Such a bridge can be found, for example, by looking looking at the possible intersections of the polygons with a the segment connecting any vertex from the first polygon to any vertex from the second polygon. If there are no intersections, then the connecting segment is itself a bridge. Otherwise, the part of this segment which is outside both polygons can be used as a bridge to start with.

Exercise 1.9: We can map each real number r in the input set of the real numbers to be sorted to a point with x-coordinate r and y-coordinate -r². In the convex hull of the points created in this way, all the points appear on the hull in the same order as their x-coordinates. Hence, once the convex hull has been computed, the sorted list of the input real numbers can be computed in linear time. (Squaring real numbers is allowed in the algebraic computation tree model which may be used to show an Omega(nlogn) lower bound for sorting, and therefore this reduction is valid to show an Omega(nlogn) bound for the convex hull problem as well.)

Exercise 1.10e: We leave it to the beginning of the next problem solving session (on January 28).

* Tuesday, January 22:

Chapter 2 (Computing line segment intersections, the plane-sweeping technique, the doubly connected edge list, computing the overlay of two subdivisions, etc.)

* Thursday January 24, time: 15.15-17.00:

We finish Chapter 2 (computing DCEL's, etc) and move on to Chapter 3 (triangulation of polygons, and "Guarding Art Galleries").

* Monday, January 28:

Copies of the first obligatory assignment were handed out.

We discussed exercise 1.10e, all exercises from 2.1 to 2.5 (inclusive), 2.12, 2.13 and 2.14.

Exercise 1.10e:
Two solutions were proposed. One incremental, where the circles are added on the convex hull one by one ordered by size, starting from the largest and ending with the smallest one. Let us look at the upper hull only, for simplicity. Its vertices are kept in a balanced binary search tree ordered by their x-coordinates. When visiting a node of the search tree, corresponding to some vertex v of the convex hull, first we check whether the vertex v should be removed or whether the arc incident to the vertex v should be updated because of the new circle which we are about to insert. If yes, then we make all necessary local updates according to the "left-turn" criterion, as in the book, and the time is only constant per removed vertex. If neither the vertex v nor its incident arc are affected by the new circle, then let C' be the circle which induces the arc incident to v, and let C be the new circle. If C is entirely inside C' or if C' blocks visibility to C from above, then we stop, because C does not appear on the final upper hull. Otherwise, we imagine a half-line starting from the center of C' and going through the center of C. If this half-line intersects the circle C' to the left of the arc incident to v, then we proceed down to the left branch of the search tree, otherwise we proceed down to the right branch of the tree, and so we continue recursively until we find, after at most O(log n) such checks, whether the new circle C induces any changes in the upper hull and, if yes, where these changes occur.
    Another option to solve Exercise 1.10e is by using divide and conquer: Split the set of circles into two approximately equal sets, compute the convex hull recursively for each of the sets, and merge the two resulting convex hulls. Two such convex hulls can be merged in time linear with respect to the vertices on them by using e.g. plane sweep. For example, the upper hull of the merged hull can be computed by performing a sweep of a vertical line from left-to-right in a way similar to Graham's scan in the book, removing vertices whenever left-turns are encountered. There is only a constant number of intersections per new vertex encountered during the plane sweep, and the work is constant time per encountered intersection plus constant time per removed vertex because of detected left-turns. Hence the total time is linear.

Exercise 2.5: The answers to the four statements are "yes", "yes", "no", and "yes", respectively. (Note that concerning the third statement, sometimes the equality may hold, but there are examples where it does not hold.)

Exercise 2.12: There were lively discussions about this exercise. After computing the DCEL (doubly connected edge list) for the triangles, an additional sweep can find out for each point in P which half edge is horisontally next to the left, and by seeing in the DCEL the face adjacent to it we can see whether it is the outer, infinite face. Another approach would be to start by getting rid of all nested triangles. That is, during the first sweep, whenever you encounter the first vertex of a new triangle, if you see that its right and left neighbors on the sweep line are two of the edges of a single triangle, then this means that the new triangle is nested within another one, and can therefore be deleted from the event list.

Exercise 2.13: A method to compute such a set of segments could be to start by triangulating the subdivision induced by the triangles and their convex hull. The segments to be drawn can then be picked among the edges of this triangulation. (A more plane-sweep-oriented approach without triangulation could be to start by drawing horisontal segments which connect vertices of triangles to other triangles, but we did not elaborate further on this approach.)

* Tuesday, January 29:

Additional copies of the first obligatory assignment were handed out.

Finished Chapter 3 (including how to handle degeneracies). Chapter 4: linear programming and the mentioned application to manufacturing with molds, including its generalisation to three dimensions.

* Thursday, January 31:

Unbounded linear programs.
Computing smallest enlosing discs (at the end of Chapter 4).
kd-trees from Chapter 5 (range searching).

* Monday, February 4:

Exercises from Chapter 3. The following problems were discussed: 3.1, 3.4, 3.5, 3.6, 3.11, 3.12, 3.13. 3.14.

Exercise 3.1:
Sketch: Let us take as an example a polygon with only one polygonal hole. We can connect the leftmost vertex which belong to this hole by a diagonal to a vertex of the boundary. This diagonal could be viewed as a "bridge", and we can regard it as consisting of two parallel edges infinetisimally close to each other, turning the polygon into a hole-free one, by duplicating the two vertices which are the endpoints of the bridge. Hence, the "new" hole-free polygon has two more vertices than the original one (including the hole vertices). More generally, we can turn a polygon with h polygonal holes and a total of n vertices (including the vertices of the holes) into a hole-free polygon with n+2h vertices by inserting h such "bridges". Triangulating this hole-free polygon we obtain n+2h-2 triangles.

Exercise 3.4:
First color the vertices with four colors, such no two vertices of the same quadrilateral have the same color. This can be done by coloring first any diagonal with two colors, and then proceed to color in a consistent way the remaining two uncolored vertices of any quadrilateral which which has only two vertices colored so far. In this way there will not be any conflicts, since the dual graph of the quadralisation is a tree. When all vertices have been colored, then place a camera on each vertex which is colored with the color which has been used the least number of times. These cameras see all quadrilaterals, and their number is not greater than n/4.

Exercise 3.6:
Skecth: First we compute a triangulation using the algorithm in the book (or any other efficient algorithm), with an associated DCEL-like data structure. We number the vertices in, say, counterclockwise order around the polygon. In this way we can compute for each diagonal in the triangulation in constant time how many vertices there are in each one of the two subpolygons in the partition induced by the diagonal. Next we start "walking" from triangle to adjacent triangle in the triangulation, in constant time per step, towards the diagonal which achieves the most balanced partition.

Exercise 3.11:
Sketch: Every interior corner of P of more than 180 degrees bounds the range of slopes of lines with respect to which P can be monotone, since this interior corner is not allowed to be a merge vertex or a split vertex with respect to any such line. So, can compute the intersection of the ranges of slopes which are admissible by all such interior corners. If the intersection is nonempty, then P is monotone with respect to any line whose slope is in this intersection.

Exercise 3.12:
Sketch: We can use the DCEL data structure for the triangulation to walk on the perimeter of the convex polygon P2 in clockwise order, detecting all the intersections between P2 and the edges of the triangulation, in constant time per such intersection. We observe that any edge of the triangulation can intersect the convex polygon P2 at at most two points. Therefore, the total number of intersections between the convex polygon P2 and the triangulation is O(m), and the total time to find them is O(m+n). At the same time, we can thus create the common DCEL for P2 overlayed on the triangulation. Finallly, we can use this common DCEL to walk around the boundaries of the pieces of the intersection of P1 and P2.

Exercise 3.13:
We can connect walk clockwise around the convex polygon connecting every second vertex with a diagonal to the vertex which lies two steps ahead. So, in one round we cut off approximately half the vertices. Proceeding in this manner, we create a full triangulation after O(log n) rounds.

Exercise 3.14:
Sketch: Imagine starting from the vertex of P which is farthest from p and building a high wall while walking along the perimeter of P in clockwise order. At the same time, we keep a doubly linked list of all vertices of the visibility area of p, sorted in clockwise order around p, i.e. of the parts of the wall which are seen from p. Whenever the wall builder disappears behind one of the visible walls, then the visibility area around p will not change until the wall builder appears at the same angle from p where he disappeared. Therefore, we wait until this happens, before we continue to update our doubly linked list. In this way we can follow how the wall builder, as long as he is visible, is changing the view around p, and it takes only constant time per update of a vertex of the visibility area. Every new wall segment of P gives rise to at most two new verices on our doubly linked list, therefore the total time is linear. (Although one new segment wall may cause us to delete lots of vertices which are blocked by this segment, the total number of deletions is still not greater than the total number of insertions, and is therefore still linear.)

* Tueday, February 5:

We finished Chapter 5 (kd-trees and range trees, including fractional cascading). We also commented extensions related to the following exercises in the book: 5.3(b), 5.5, 5.8, 5.13

* Thursday, February 7:

Point location (Chapter 6).

* Monday, February 11:

Discussed the following exercises from Chapter 4:
4.2, 4.5, 4.7, 4.16.

Exercise 4.2: First we can compute the convex hull of P in linear time by an algorithm similar to Graham's scan (see exercise 1.6). A necessary (although not always sufficient) condition for an edge e of P to be a top facet of a 2D-mold is that it is an edge of the convex hull, and that the angles of the two interior corners of the convex hull at e have a sum of at most 180 degrees. Since the convex hull makes such a sharp turn at each such edge e fulfilling these conditions, there can be at most a constant number of such edges. (By more precise arguments one could show that there are at most four such edges.) Hence, we need to test at most O(1) candidates for being top facets. By using the method in the book, each such test takes linear expected time. However, since this is a more restricted problem, according to the method of the book we would obtain a 1-dimensional problem with one halfline per edge of P, so computing the intersection of those colinear halflines can be done in deterministic linear time.

Exercise 4.5: Sketch: We considered as "adjacent" facets which share at least one edge of their boundary. Let us assume that the facets are given as a DCEL (or some similar data structure) which describes the planar graph corresponding to all the facets. Then, the time to make the test for any facet f is linear with respect to the number of edges of the facet, and so the total time to make the test for all the facets becomes O(n).

Exercise 4.7:
    (a) An example of a polygon which is castable and removable by a single translation but not with a rotation is a square. On the other hand, an example of a polygon P which is castable and removable by a single clockwise rotation but not with a translation can be contructed as follows:
     Let e be the top side of P, of length 8, and let the center of the clockwise rotation, call it p, be at distance 1 horisontally to the right of e. Apart from the two vertices of e, P has five additional vertices. Let (0,4) be the coordinates of the left endpoint of e. Thus, (8,4) are the coordinates of its right endpoint, and (9,4) are the coordinates of p. We follow the perimeter of P clockwise from (8,4): the next vertex has coordinates (8,3), the next (9,2), the next (10,2), the next (9,0) the next (4,0) and finally the next (0,4) (and so we are back to the left endpoint of e).
    (b) For the sake of simplicity we assume that we test one edge of P as a candidate for being the top edge, so that the position of P is fixed. Hence, we assume that this edge is horisontal and has higher y-coordinates than any other vertex of P. Now, according to this position of P, every side, call it e, of P defines a halfplane where the center of the clockwise rotation of P can be with respect to e, so that when the rotation starts no part of e would run into the wall of the mold which coincides with e. This halfplane is bounded by the line perpendicular to the first vertex of e which we encounter while traversing the boundary of P in clockwise order. Hence, the problem reduces to finding the intersection of the n halfplanes which correspond to the n sides of P. Finally, similarly as for Exercise 4.2 above, we can reduce the number of candidates for being top edges to only a constant number, by considering only segments which lie on the convex hull of P and where at least one adjacent corner of the convex hull is of no more than 90 degrees.

Exercise 4.16:
Regard a two-dimensional coordinate system where the horisontal axis stands for time and the vertical for the position of each train (at the corresponding moment of time). Hence, we have n half-lines, one half-line per train. Regard the corresponding n half-planes, which are bounded from below by the n halflines. A train will be leading at some moment of time if and only if its corresponding halfline induces a segment on the boundary of the intersection of these n halfplanes.

* Tuesday, February 12:

More about treating degeneracies and about the tail estimate for point location, from Chapter 6.
Voronoi diagrams (Chapter 7).

* Thursday, February 14, PLEASE NOTE CHANGED ROOM: E:3308! (third floor, eastern corridor)

We finished Chapter 7 (about Voronoi diagrams).
We considered also the following simpler problem, which is the most relevant ingredient of the graphics application described in Chapter 8, and in computing the discrepancy:
     Given a set S of n points in the plain, compute for each point p in S a sorted list of all the other n-1 points in S, sorted by angle around p. A familiar way to do it is, of course, by using an O(nlogn)-time algorithm for sorting around each point. This gives O(n^2 log n) total time for computing the n lists. We showed how the concept of duality can help us to improve on this time bound, by transforming the problem to an equivalent problem of computing intersections of lines in a line arrangement, in the order in which they appear on each line. We showed how the zone theorem guarantees that we can accomplish all this in total time O(n^2).

* Monday, February 18:

Discussed the following problems from Chapter 7.
     7.1, 7.2, 7.3, 7.5, 7.6, 7.7, 7.10, 7.11, 7.12, 7.13. Also, we related 7.10 and 7.11 to Euclidean Minimum Spanning trees (abbreviated EMST), showing that every edge of the EMST must connect Vononoi neighbors, i.e. two sites whose Voronoi cells share an edge. Hint: for every EMST-edge, the minimum disc which includes it cannot have any other input points (i.e. Voronoi sites) within it, neither at its boundary.
     About exercise 7.13: Note that the bisectors between two sites are not straight lines if the cost of the good is not the same at the respective site, and so Voronoi edges can be pieces of curves, rather than straight line segments. This even affects the structure and shape of the beachline, whose breakpoints follow these Voronoi edges. Some sites may even lack Voronoi cells, if it is more expensive to buy the good at some site p than to travel from site p to site p' and buy the good there. We showed, however, that the beachline is still always monotone with respect to the x-axis.

* Tuesday, February 19:

Finished Chapter 8. Also, discussed exercises 8.7 and 8.16b.

Exercise 8.7:
Whether a vertical separator exists is easy to check by looking at a leftmost and a rightmost red and blue point, respectively, i.e. a total of four points.
     Now, to check whether a non-vertical separator exists, we look at the dual problem, where for each red and blue point we have a corresponding red, respectively blue, line in the dual plane. A separator l in the primal plane corresponds to a point l* in the dual plane such that either all blue lines are above l* and all red lines below l*, or vice versa. Since the two cases are symmetrical, let us look at the first case. This means that l* has to be in the intersection of n "blue halfplanes", each one bounded from above by a corresponding blue line, and n "red halfplanes", bounded from below by a corresponding red line. The linear programming algorithm from Chapter 4 can give us in linear expected time a point in the intersection of these 2n halfplanes.

Exercise 8.16(b):
We may color the upper endpoint of each segment red and the lower endpoint blue. Now, a stabber for all the vertical segments exists if and only if there exists a separator which separates the blue from the red points, see Exercise 8.7 above. Such a separator can be found in linear time (see Exercise 8.7 above).

* Thursday, February 21:

We went through the main parts of Chapter 9, i.e. the properties of Delaunay and of legal triangulations, legal and illegal edges, angle vectors and that the only triangulations which maximize the angle vector are Delaunay (=legal) triangulations. We also described the incremental randomized algorithm for Delaunay triangulation and its (expected) time and space efficiency. We omitted almost all proofs.

We also discussed Exercises 8.15 and 8.16a:
Both exercises can be solved in a similar way. To see the idea, let us first assume that the input segments do not share endpoints, and that we don't consider vertical stabbing lines. First construct the line arrangement for the endpoints of the input segments, and store it by using the Doubly Connected Edge List data structure. Then, start by finding a face in the arrangement which is outside all wedges of all segments. Such a face can be located by taking the point dual to a line which does not cross any one of the input segments. Mark this face with the number zero. Then, starting from this face, propagate from face to adjacent face (by using the twins of the corresponding half-edges) and mark in this way the adjacent faces with the number corresponding to how many wedges of the input segments contain this face. Going from any face to any adjacent face like this means that the number to mark the adjacent face differs only by one. When we have finished with this propagation, we can see whether there is some line which "stabs" all the input segments by seeing whether we have marked at least one of the faces with the number n.
     The special case of vertical stabbing lines can be handled by looking only at x-coordinates of the endpoints of the input segments, and thus projecting the input segments vertically onto the x-axis. Other degeneracies, and the case when endpoints of input segments are shared between segments, can be treated by standard symbolic perturbation techniques. For example, we can slightly (infinetisimally, in a symbolic way) lengthen each segment, thus forcing their endpoints to move apart. Any computed line (with actual coordinates, i.e. not symbolic) stabs such a lengthened segment if and only if it stabs the original segment.
     Finally, to answer the queries of exercise 15, we can use the point location data structure from Chapter 6 for this line arrangement, where we use as edges the crossing free pieces of the line arrangement.

* Friday, February 22:

15.30 o'clock (please observe the time!), in room E:2116: A presentation, in ENGLISH, of a Master's thesis in Computational Geometry, about algorithms to help a company to place cameras with limited range to guard various kinds of areas and rooms. The report is in English, and both the presentation and the following "opposition" (or discussion) will be in English. This may also give you a hint for how to present and discuss about your own and other projects.

* Monday, February 25:

Preliminary schedule for presentations:
     First presentation by Cenn. Wenn., about NP-hard geometric problems and approximations. The material for the presentation can be found here.
     Second presentation by Gudmund. Hreid. (about Chapter 3)
     Third presentation by Rasmus and Sébast. about robots travelling in polygons (related to Chapter 13, possibly combining with computing shortest routes from Chapter 15)
     Fourth presentation by Anton. Anton. and Johanna P., based partly on the paper "An Optimal Algorithm for Determining the Visibility of a Polygon from an Edge, David Avis and Godfried Toussaint, IEEE Transactions on Computers, 1981". Here is a link to their report and code.

* Tuesday, February 26:

     - Presentation about geometric spanners, decompositions of point sets into well separated pairs of subsets, and approximate shortest path queries; by student M. Nilsson. Based partially on the paper "Mattias Andersson, Joachim Gudmundsson, Christos Levcopoulos: Approximate distance oracles for graphs with dense clusters. Comput. Geom. 37(3): 142-154 (2007)".
     - Presentation about producing fractals with the help of Voronoi diagrams, by student Paul Stapl.
     - Presentation about: ... (one more presentation is needed here, any volunteer?)...

* Thursday, February 28, OBSERVE THAT THE ROOM THIS DAY IS E:3308 !:

Presentations by students. The following presentations are scheduled:
     - Presentation about Chapter 14 (Quadtrees and non-uniform mesh generation), by students Ehs. B., Berek. Gich., and John Kir.
     - Presentation about Chapter 12 ("The Painter's algorithm" and Binary Space Partitions) by students Roub. Jhum. and Is. Beq. (from own laptop)
     - Presentation about Chapter 10: by students Hanna Mikh. and Has. H. Bal.
     - Presentation by Vish (the report can be downloaded here); equipment: projector and own laptop

* Friday, February 29, starting at 13.15 o'clock IN ROOM E:2116 (AS USUALLY)!!

Presentations by students. The room is reserved until 17.00 o'clock, but hopefully we will finish much earlier. Preliminary schedule:
     - Presentation about points on a sphere; computing and triangulating Voronoi-like cells on a sphere (by students by Ahr. Lang., Sim. Cr. and Url. Tom.)
     - Presentation about a special kind of trees for metric spaces, called "vp-trees"), by Jo. Åstr. A relevant reference is "Peter N. Yianilos, Data Structures and Algorithms for Nearest Neighbor Search in General Metric Spaces (1993)".
     - Braj. La. about acceleration structures for ray tracing, e.g. the uniform grid and bounding volume hierarchies, compared to three-dimensional kd-trees.
     - Computing convex hulls in time O(nlogh) by student Cu. D.
     - Some additional material from Chapter 10, by students Dennis L. and Pont. Granst.
     - Perhaps one or two additional presentations, e.g. to present the CGAL library and show the possibilities of it and how it can be used (by student Clém. Jov.)