Readings and reading questions.

You do not have to copy the questions.

Note on finding papers:
When I say something is available ``online through the library'', here is what I mean. You have to access it from a UCD IP address, ie a workstation plugged into the wall on campus; it won't work from home. Go to Harvest, and search for the name of the journal. Follow the link on the journal's page saying ``electronic resources internet''.

• Due Th Jan 11: 2D BSP trees. Read Chapter 12 up through section 12.3
  • At the top of page 255, it says, "..although autopartitions cannot always produce minimum-size BSP trees..." A more formal way of saying this, so that we could actually prove it, might be:
    "For any n, there exists a set of non-intersecting line segments in the plane for which some BSP tree has size f(n), while any autopartition must have size at least g(n)."
    Fill in the functions f(n) and g(n), and prove the statement by describing a how to construct such a set of segments, given any n.
  • Give a one or two sentence justification for each of the three lines of the computation of the bound on E[number of cuts generated by s_i] on page 258.

• Due Tu Jan 16: Read Sections 7-7.1, and Sections 9-9.1.
  • Look up Thales Theorem and describe its relation to Theorem 9.4
  • There are two key arguments about Euler's theorem on planar graphs in these sections. In dimension three, the analog of Euler's theorem says that:
    
    -c + f - e + v = 1
    
    where c is the number of full-dimensional cells in a decomposition of a ball in 3-space, f is the number of faces, e is the number of edges and v is the number of vertices. (You can verify this formula for a solid cube and a solid tetrahedron, just to get a feel for it; do not hand this in).
    
    Consider a solid decomposed into tetrahedra, the analog of a triangulation of a point set in 2D. In the 2D case, we could prove that that the number of triangles is linear in the number of vertices. Is this possible for the number of tetrahedra in 3D? Can you get any polynomial bound for c as a function of v? Hint: What other easy facts relating v,e,f and/or c can you bring into the argument?
  • Last time we looked at the alternate BSP tree algorithm, described at the beginning of Section 12.4, for which Kenny will present the proof in 3D. Give an example of a set of segments in the plane, and an insertion order, for which the alternative algorithm produces a smaller BSP tree than the standard algorithm.

• Due Th Jan 18: Read Section 9.2, and the one-page handout, page 10 from Edelsbrunner's book. Section 9.2 should be easy except for the proof of Theorem 9.8. We will go over this theorem in class, so don't agonize over it too much. In class we will discuss the following statement. You do not have to hand anything in.
  • A terrain in 3D is called convex if the line connecting any two points on the terrain lies entirely on or above the terrain. Consider the terrain formed by taking any set of points in the plane, assigning each point the z coordinate z = x²+ y², as described in the handout, and interpolating them using the 2D Delaunay triangulation, as described at the beginning of Chapter 9. The resulting terrain is convex.

• Due Tu Jan 23: Read Section 9.3 and 9.4, up until Lemma 9.13.
  • After reading the proof of Lemma 9.10, write a short proof that every new triangle in the Delaunay triangulation created by the insertion of p_r has point r as a vertex.

• Due Thur Jan 25: Finish Section 9.4.
  • The middle of page 198 describes a scheme for charging each node visited in the search structure during point location to a triangle that appeared in the Delaunay triangulation of some earlier subset of the input points. Looking at the example on page 195, consider inserting a new point whose search path goes through the nodes for triangle 2, then triangle five and finally triangle 6. To which triangles in the top triangulation (triangles 1,2,3) are these steps charged?
  • Let Del(r) be the Delaunay trianglulation after inserting a random subset of r points. Pick any arbitrary triangle T in Del(r). Use the backwards analysis idea to bound the probability that T is in Del(r) but was not in Del(r-1).

• Due Tues Jan 30: Chapter 8, through the end of Section 8.2.
  • Review question on Delaunay triangulation construction. We discussed in class an alternative method for point location, called "conflict lists". Initially we begin the algorithm with a single large triangle, which all the un-inserted points fall into. We keep these points in a list associated with the triangle. Whenever a triangle t is destroyed, either by having a point inserted into it or by flipping with another triangle, we distribute the list of un-inserted points which previously fell into t to the two or three new child triangles whose surface now covers t. When inserting a new point, we just need to look at which list it belongs to. Argue that the total time required for maintaining these lists with every triangle can also be bounded by Expression (9.1).
  • Argue that a regular grid of 16 points in the unit square has discrepancy at least 1/5.

• Finish Chapter 8, up through 8.5. Nothing to hand in.

• Handout: Pages 36-46 from Mulmuley, Computational Geometry: an Introduction Through Randomized Algorithms.
  • We are given a set of line segments in the plane, and asked to determine whether there exists a staight line intersecting all of the segments. Use the duality transform from Chapter 8 to transform this problem into one involving arrangements, and describe how to solve it in O(n²) time.
  • Consider the silhouette of the unit sphere, as seen from a point p outside the unit sphere in 3D. It consists of the the set of points on the sphere whose tangent planes contain p. Using the duality transform T defined on pages 41 and 42 of the handout, what is the dual of the silhouette?

• Read handout from Matousek's Lectures on Discrete Geometry.
  • Think about the following question, but you do not need to write it up or hand it in. A vertex of a four-dimensional simplex is contained in four (d-1)-dimensional facets. How many 3,2, and 1 dimensional faces is it contained in? In general, how many faces of dimension k contain a vertex of a d-dimensional simplex?
  • Look at these ideas for projects, and think about what you want to do on your own.

• Skim 4.1, then read 4.3 and 4.4. Skim 4.6, just to get the idea and the result; we will discuss a simpler version of the algorithm in lecture.
  • What is the expected number of times the minimum vertex of the polytope changes, in the algorithm in Section 4.4? That is, what is the expected number if indices i such that v_i-1 is not contained in h_i?

• Feb 15 and Feb 20: I will give two lectures on using Delaunay triangulation to model molecules, based on the skin surfaces paper. You do not need to read it, but if you are interested in molecular modeling and you'd like to work on the project involving the mixed complex, you should.

• Feb 22: Skim Section 5.1, then read Section 5.2 carefully. Here is a writeup of the search method for nearest-neighbors and some great animations.
  • In writing, give an example of a set of n points in the plane, and a rectangle query, for which k, the number of points in the rectangle is zero, but O(sqrt(n)) cells of the kd-tree have to be examined. For discussion in class, think about how many cells might have to be examined for a query circle. Fewer or more?

• Feb 27: I will lecture on the paper: Kd-trees are best when cut on the longest side. The piercing Lemma was originally proved in the classic paper An optimal algorithm for approximate nearest neighbor searching in fixed dimensions. No reading required. Work on your reading for your project.

• Feb 29: Read section 14.2, on quad-trees.
  • Consider the quadtree in the figure below. If the two points in the upper left quadrant were closer together, the quadtree would have more leaves. Now think about balancing the quadtree. Can the two points ever be close enough together that they force cells A, B or C to be split?

    WOOPS! Shubho points out that if we balance the given quad tree, A,B and C will be split....more in class tomorrow.

  • Mar 6: We will have presentations on Sections 10.1 and 10.3; you will get more out for them if you read the sections, but it is not required. I will begin talking about Timothy Chan's 2-page paper Closest-point problems simplified on the RAM, which uses quad-trees in a not-exactly explict way.