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 or a laptop using a campus wireless connection; or after connecting 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''.

• Th Jan 6: 2D BSP trees. Read Chapter 12.1-12.4. You can skip the proof of Lemma 12.3, since it uses some ideas we won't see until later. We will review the analysis in Lemma 12.1 in class.
  • At the bottom of page 262, 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), with f(n) < g(n), and prove the statement by describing a how to construct such a set of segments, given any n (it is OK to require n to be a power of two, or divisible by 3, or something like that, so long as n goes to infinity). Note: finding an f(n) = o(g(n)) is a more difficult problem.
  • In the paragraph under the proof of Lemma 12.1, on page 266, it says that the expected size of a BSP is n + 2n ln n, and that at least half of all permutations lead to a BSP tree of size n + 4n ln n. Notice that the two bounds are different. Why? Which one is proved by Lemma 12.1? Can you think of a way to prove the other one? Hint: Google Markov's inequality.
• Tues. Jan 10: Read Section 12.5. Note that this is not in Editions 1 or 2 of the book, so if you have an old edition use the library link to get it online.
  • If we changed the word "square" in Lemma 12.6 to the word "rectange", it would no longer be true. Draw an example showing that the modified Lemma would be false.
  • We will discuss the the following question in class: would the algorithm described in Section 12.5 be better in practice than the traditional BSP tree algorithm of Section 12.3? Write a couple of sentences on this question, and be sure to define what you mean by "in practice".
  Added later: survey paper including Toth's lower bound construction for line segments in the plane (Section 3).
• Th Jan 12: Section 1.1 of Edelsbrunner's book, Geometry and Topology of Mesh Generation (handout).
  • Reading question (short answer): In Figure 1.4, which of the two Voronoi cells shown belongs to the big circle, and which belongs to the small circle?
  • Reading question (short answer): In Figure 1.5, the Acyclicity Lemma proves that the triangulation shown is not Delaunay. How does it violate the definition of Delaunay triangulation as the triangulation connecting input sites that share Voronoi edges?
• For Tues, Jan 24, read Section 1.2. We will discuss the following questions in class, so it would be useful to think about them before that, but since I am posting these so late you are not required to hand in the answers.
  • The Delaunay tetrahedralization in R³ can also be defined using a "lifted sphere claim", analogous to the lifted circle claim on page 10. Describe this claim.
  • Consider two tetrahedra that share a common triangular face. What is the analog of a flip in the 3D case?
• For Thurs, Jan 26, read Chapter 11, up through Chapter 11.2, in the de Berg, et al. textbook. Think, as you read, how this algorithm is generalized to higher dimensions. We will do the analysis in arbitrary (small) dimension d.
  • If the input points are not added in random order, the running time of the convex hull algorithm can be quite large. Can you think of an example of a set of points and a bad ordering for which O(n²) triangular faces are created?
  • Consider the convex hull of a set of points in 4D; it has 3D cells, 2D faces, 1D edges and 0D vertices. The analog of Euler's theorem for such a cell decomposition is:
    
    v - e + f - c = 0
    
    where c is the number of cells, etc. For a 3D convex hull, we could prove that that f is linear in v. In 4D, can you get any polynomial bound for c as a function of v? Hint: What other facts relating v,e,f and/or c can you bring into the argument? For example, can you see a polynomial bound on e in terms of v?
  Added later: handout on the analysis of convex hull conflict lists.
• For Tues, Feb 1, Please read Chapter 4, Sections 4.1, 4.3, 4.4 and 4.6. You can skip 4.2 and 4.5, and, if you are really busy, 4.1.
  • Notice the similariy of the proof of Lemma 4.8 to the proof we did in class that the total number of facets created during the computation of a convex hull is O(v^floor(d/2)). What is the "easy" random variable whose expectation we can bound, upon which the analysis is built, in each case?
  • Lemma 4.11 is central to the idea of the algorithm. The book says it is a straightforward generalization of Lemma 4.5. Give the proof for the general dimensional case, in your own words.
• Thurs, Feb 3, application of Delaunay triangulation to surface reconstruction, medial axis, distance function. Slides. Here is the crust applet we looked at. Note that homework is due on Tues Feb 15.
• Tues Feb 8 and 10, guest lecturer Xinwei Shi, on the application of Voronoi diagrams and Delaunay triangulations to molecular modeling.
  slides!
• For Tues, Feb 15, Read Chapter 14 on Quad-trees.
  • Theorem 14.4 shows that balancing a quad-tree blows up the size by a factor of at most eight. The 3D analog of a quad-tree is an octree, in which a cube is split by dividing it into eight sub-cubes. An octree can be balanced in a similar way; what is the blow-up factor in 3D? Explain in a few sentences how the proof of Lemma 14.4 would have to be changed for the 3D case.
• For Thurs, Feb 17, we will do the proof at the end of these lecture notes, on the running time for priority search in an octree of bounded depth. No other reading.
• For Tues, Feb 22, we will read a paper on nearest-neighbor finding due to Liao, Lopez, and Leutenegger. Lemma 1 is difficult; we will go over it in class, so do not worry if it does not sink in when you read it.
  • Consider the algorithm in the plane, and let delta be the distance from query q to its true nearest neighbor. Give a lower bound on the size of the cell containing q in any one of the shifted quadtrees. Lemma 2 implies an upper bound on the size of the smallest cell containing q. What is it?
• For Thurs, Feb 24, read Chapter 5; we will discuss Section 5.1 and 5.2, and if we have time Section 5.3. No reading questions, since I am posting this so late.
• For Tues, Mar 1, no reading. I will discuss the geometry of lines in three-dimensional space. Here are some lecture notes. Many more references can be found in this survey paper by Marco Pellegrini.