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; 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''.
Jim points out that you can access library resources from off campus, using some well-known tricks.

• Due Tu April 7: 2D BSP trees. Read Chapter 12. You can skip the proof of Lemma 12.3, since it uses some ideas we will see 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), and prove the statement by describing a how to construct such a set of segments, given any n.
  • At the end of Section 12.3, it says, "...the algorithm described above is probably superior in practice." Consider the modified algorithm given in Section 12.4. Can you come up with an example of a set of line segments in the plane, and an ordering on those segments, for which the modified algorithm produces a BSP tree with fewer cells than the original algorithm? Here we do not need a set of segments for any n, just one set of segments. You do need to use the same order on the set of segments with both algorithms.

• For April 9: No additional reading if you read the whole chapter of the on-line version of the book; otherwise, print it out and read Section 12.5 which was not in the second edition of the book.
  • 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 short paragraph on this question, and be sure to define what you mean by "in practice".
  Here are some optional readings someone could present in a future class:
  • Pages 537-539 of the survey on BSP trees by Csaba Toth. This sketches a lower bound for the size of a the BSP tree on a set of line segments in the plane that almost matches the upper bound. You won't have time to do the whole proof (and it isn't in these few pages), but you can explain the bound and give some idea of how it works. The survey also contains a lot of interesting open problems.
  • Computer-generated pen-and-ink illustration, a classic paper on non-photorealistic rendering by Georges Winkenbach and David Salesin. Show some of the lovely pictures, and explain the three ways the system uses BSP trees.

• For Tues, April 14: Read Chapter 14 on Quad-trees. Answer the following questions in writing (the first one is a reading question, the second is to give you some practice in the kind of randomized analysis we did on Tuesday):
  • 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? Give at least a few sentences of arguement as to how the proof of Lemma 14.4 would have to be changed for the 3D case.
  • We are given as input a list of the integers 1...n, in shuffled order. We read the list from beginning to end, keeping track of the maximum number we have seen so far. How many times does the maximum change? Provide a detailed proof. Things you might use are some 0/1 random variables, the Linearity of Expectation, and a probabilistic argument like the one to get the bound on dist(i,j) in Lemma 12.1. Good background reading on random variables and expectaion is Section 13.3 of Kleinberg and Tardos, "Algorithm Design" (the textbook for ECS222a).
  Here are some additional readings for someone to present next week:
  • The kind of analysis in the second problem is sometimes attributed to the randomized closest pair algorithm of Rabin, which is covered in Section 13.7 of the Kleinberg and Tardos book. I would be happy to have one person present the algorithm and another person present the analysis, each in 15 minutes.
  • Francois Labelle and Jonathan Shewchuk's recent paper on Isosurface Stuffing is an octree-based tetrahedral meshing algorithm. While it is too complicated to present in 15 minutes, someone could read it and describe how it relates to the simpler 2D algorithm we studied.

• For Thursday April 16: Read Section 19.3 on spatial queries with quadtrees in Prof. Aluru's chapter in the Handbook of Data Structures and Applications (again, this is one of those UC-only links). This material is hard to follow, so we'll go over it in class.

• For Tues April 21: Read Section 19.2 on region quadtrees in the Aluru chapter. Skip the divide and conquor algorithm in 19.2.5, but do read the bottom-up construction in that section. This material is a little more understandable than Section 19.3 was.
  • The data structure described in Section 19.2.6 lets us locate the cell containing a query point in a quadtree in O(lg n) time, without making any assumptions on the depth d of the quadtree. It is also often useful, given any cell C, to be able to find C's neighbors of equal size, if they exist, or the cells containing them, if they do not exist. How quickly can we do this using this data structure?

• For Thurs, April 23, we will consider the paper, High dimensional similarity search with space filling curves by Liao, Lopez and Leutenegger.
  • Short answer question (three sentences, in writing): this method requires storing 4 copies of the data in R³. Is this more space than a pointer-based quad-tree requires? Is it practical? How about for higher values of d?

• For Tues, April 28, read Sections 5.1 and 5.2 in the book, on kd-trees.
  • Picky technical question: prove that the recurrence at the bottom of page 104 solves to O(sqrt(n)).
  • Reading question: Consider adapting Lemma 5.4 to the 3D case, in which the ranges are rectangular boxes, and each level of the kd-tree involves three splits, one in x-direction, y-direction and z-direction. What bound can you get on the time to answer a query?
  Here is a series of kd-tree applications papers, on traversig kd-trees for ray-tracing on the GPU, which I would like to see presented in class:
  • KD-tree acceluration structures for a GPU raytracer, by Foley and Sugerman, Eurographics '05.
  • Interactive kd-tree GPU raytracing", by Horn, Sugerman, Houston and Hanrahan, I3D '07.
  • Stackless kd-tree traversal for high-performance GPU raytracing, by Popov, Gunther, Seidel and Slusallek, Eurographics '07.

• For Thursday, April 30, we will read kd-trees are best when cut on the longest side, by Dickerson, Duncan and Goodrich. A similar paper, more frequently cited, is It's OK to be skinny, if your friends are fat, by Maneewongvatana and Mount. You are only required to read the first paper, though. Both concern nearest-neighbor finding with kd-trees.
  • Reading questions (short answer): The upper bound on the time required to answer an approximate nearest-neighbor query with a kd-tree give here is not as good as the similar bound we got using a quadtree, under the assumption that the point distribution allowed the quadtree to have size O(n) and depth O(lg n). Why couldn't they get a bound of O(1/e lg n) using this data structure? Does this mean that this data structure is a worse choice than a quadtree?

• For Tues, May 5, no reading. We will begin discussing Voronoi diagrams and Delaunay triangulations.

• For Thurs, May 7, 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 given in Section 1.1?
  A paper for someone to present:
  • Nelson Max, Pat Hanrahan and Roger Crawfis, Area and volume coherence for efficient visualization of 3D scalar functions, SIGGRAPH 1990. Spend 5 minutes on sections 1-6, and 5 minutes on section 7 (which is the part relevant to what we're doing).

• For Tues, May 12, read Section 1.2 and 1.3 in the handout from the Edelsbrunner book.
  • Do exercises 2 and 4 at the end of the chapter (I believe 4 is more difficut, take a shot and we will discuss it in class).
  Some papers for someone to present (one of them mine!):
  • N Amenta, M Bern, D Eppstein, The crust and the Beta Skeleton: combinatorial curve reconstruction, Graphical Models and Image Processing, 1998. Gave the idea of using the Delaunay triangulation to reconstruct point-clouds a kick in the pants. It's a long paper, so focus on the definition of the crust, and the sampling definition, and what the results are (not how they're proved).
  • TK Dey, P Kumar, A simple provable algorithm for curve reconstruction, Proceedings of the tenth annual ACM-SIAM symposium Discrete Algorithms, 1999. Quickly improved on the paper above, in two short pages!

• For Thursday, May 14, think about the following question. You do not need to hand anything in.
  • Consider a decomposition of a solid in 3D into a set of tetrahedra, the analog of a triangulation in 2D. The analog of Euler's theorem in three dimensions is:
    
    v - e + f - c = 0
    
    where c is the number of full-dimensional cells in a decomposition of 3-space, f is the number of faces, e is the number of edges and v is the number of vertices. 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 facts relating v,e,f and/or c can you bring into the argument?

• For Tuesday, May 19, nothing to read. We will talk about duality and polytopes.

• For Thursday, May 21, read Raimund Seidel's article, "The upper bound theory for polytopes: a short proof of its asymptotic version". Computataional Geometry,5(2):115-116, 2005.

• For Tuesday, May 26. We will finish the analysis of general dimensional convex hulls, and then go back and discuss Section 1.4 from the handout on Delaunay triangulations from Edelsbrunner's book.
  • Homework question to hand in: We proved in class that the Delaunay triangulation of n points in dimension d is made up of O(n^ceil(d/2)) d-simplices. We also gave an example of a matching lower bound in R³: a set of points in 3D whose Delaunay triangulation has O(n²) tetrahedra. How did it work again? The points were distributed on two lines, l and m, not parallel and not touching, with n/2 points on each, called (say) l1, l2, l3,...l(n/2) and m1, m2, ...m(n/2). We considered a quadruple of the form li,l(i+1) and mj, m(j+1). The unique sphere S through that quadruple intersects line l in exactly two points, and m in exactly two points. Since there's no points between li and l(i+1), there are no points on l inside S. Similarly m. So S must be a Delaunay sphere and li,l(i+1),mj,m(j+1) the vertices of a Delaunay tetrahedron. Then we just counted how many ways there are to pick li and mj.

    Please generalize this example to give an example of a set of points in dimension d, (d odd), which has O(n^ceiling(d/2)) d-simplices in its Delaunay triangulation.