Reading questions for 289L

ECS 289L: Computational Geometry

Reading questions

Reading questions are due in class, in writing, on the day that the reading is due.

YOU DO NOT HAVE TO COPY THE QUESTIONS

2D BSP trees. 10/4: Pages 249-257 on BSP trees; we will go over the proofs of Lemma 12.1 and Theorem 12.2 in class.
- At the top of page 253, 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.
10/6: Probability and expectation.
10/8: Intro to 2D Delaunay triangulation. Begining of Ch 9 -- End of section 9.2. In class we will discuss duality with the Voronoi diagram (Theorems 9.6 and 9.7), and go over the proof of Theorem 9.7. Be prepared to state the definition of a "legal triangulation" from Section 9.1.
For Euler's theorem, take a look at David Eppstein's collection of seventeen proofs! If one is enough for you, it looks like number 4 is short and easy.
- Euler's formula applies to any planar graph (a planar graph is one which can be drawn in the plane with no crossing edges). Notice that any drawing of a planar graph can be triangulated, by adding (not necessarily straight) edges in faces which have more than three sides. Use this idea to argue that the number of edges in a planar graph is always O(n), where n is the number of vertices.
- The LegalTirangulation algorithm on page 185 (in my book) describes how to get from any triangulation to a legal one by flipping. Argue that you can get from any triangulation to any other by flipping.
There are a couple of nice 2D Delaunay triangulation/Voronoi diagram applets available. The one by Paul Chew has the nice feature of displaying the Voronoi circles. He is also known for his nice surface meshes, among other things.
10/11, Class postponed
10/13: No class.
10/15: No class.
10/18, 11 AM: Randomized incremental construction of the Delaunay triangulation. Section 9.3. Feel free to skim the part about special handling for the three points of the initial triangle.
10/18, usual time: Analysis of randomized incremental Delauany algorithm. Section 9.4
- We noted that in some applications it is not important for a BSP tree to be balance. Is it important that the DAG described in this algorithm should be balanced? Why or why not? Keep this question in mind as you read the analysis. We will discuss in class how the algorithm achieves, or fails to achieve, a balanced tree.
10/20: Finish up running time analysis for Delaunay, discuss relation of Voronoi diagram and halfspace intersection. Section 11.5.
10/22: Convex hull/halfspace intersection duality. Ben takes notes.
- Homework problem, using Delaunay analysis. Hand in in writing in class. Let q be a point inside the convex hull of a point set P. Give an upper bound on the expected number of times a new Delaunay triangle containing q is created, during the course of the incremental construction of the Delaunay triangulation of P. Hint: Consider the probability that a new triangle containing q is created by the r'th insertion.
10/25: Convex hull in 3D and higher. Begining of Ch. 11 - end of setion 11.2. Note that a ``conflict" in this chapter is the same thing as an ``incedence" in my lecture on Wds. We will not do the analysis; it is fundamentally the same as Delaunay triangulation analysis. While reading, think about how this algorithm corresponds to the Delaunay triangulation algorithm from Chapter 9. Scott takes notes.
- Written problem to hand in (warm up for higher dimensions): We can construct a square by taking the 2D convex hull of all the points (x,y) with all choices of x in {0,1} (x is either 0 or 1) and y in {0,1}. Similarly we get a cube if we take the convex hull of (x,y,z) with x in {0,1}, y in {0,1} and z in {0,1}. In 4D, we get a hypercube if we take the convex hull of all points (x,y,z,w) with x in {0,1}, y in {0,1}, z in {0,1} and w in {0,1}. How many vertices, edges, square faces and cube facets does the hypercube have? How many d-1 dimensional facets does a d-dimensional hypercube have?
  Ben points out this very useful applet on hypercubes.
10/27: Review of homework problem, bad examples of 3D Dealunay triangulation. No reading. Taylor takes notes.
10/29: Running time of 3D Delaunay triangulation.
- Written problem to hand in: We saw that the 3D Delaunay triangulation of n points can have Theta(n^2) tetrahedra, while a 2D Delaunay triangulation of n points has O(n). Which of the following statements are true of both 2D and 3D Delaunay triangulations? Give a brief explaination of each of your answers:
  - When the rth point is added to the triangulation, forming intermediate Delaunay triangulation Tr, all of the new Delaunay simplices created are adjacent to the new point.
  - The probability that an uninserted point q lies in a Delaunay simplex which is new in Tr (that is, the simplex is in Tr but not in Tr-1) is O(1/r)
  - The number of new simplices in Tr is constant.
  - The expected number of new simplices in Tr is constant.
11/1, 11 AM: Video about a four-polytope. We will see that the 2D-faces of the polytope form a flat torus, which you can play with in this applet by MacArthur award-winner Jeff Weeks. Video coming soon on DVD.
11/1, 11/3: Kd-trees. Read section 63.4-63.4.2 of this chapter by David Mount and Sunil Arya. We will talk in class about the bad cases for these practical algorithms. Here is an example, made with a kd-tree applet from the University of Maryland, by Brabec and Samet. Valerie takes notes.
- Question to hand in (very short): in the description of the search algorithm on page 63-15, it says "...it first computes the distance from the query point to the associated cell." Should this be the distance from the query point to the center of the cell, the nearest point on the cell, or the farthest point on the cell? One answer gives a correct algorithm, the others do not.
11/5: Kd-trees and range searching. Intro to Chapter 5, and the part of Section 5.2 from the SearchKdTree algorithm to the end of the section. Guest leader Vijay Natarajan will go over the proof of Lemma 5.4. He will also lead a discussion of 1) how does the proof generalize to 3D and higher? and 2) what if the query region is a circle rather than a rectangle?
11/8: Quad- and oct-trees. Read Chapter 14 up through Theorem 14.3. In class we discussed the paper by Marshall Bern, Approximate closest point queries in high dimensions, Information Processing Letters, vol 45, pp. 95--99, 1993. Available online through the library.
11/10: Balanced quad-trees. Read the rest of Chapter 14.
- Problem on quad-trees and nearest neighbors, to hand in on 11/15. Assume P is a nicely-distributed input point set in 2D (it works in any dimension, but we'll stick to 2), for which a quad-tree has depth O(lg n). We want to use the quad-tree to answer approximate nearest-neighbor queries, that is, for any query point q inside the bounding square of P, if p_i is the closest point of P to q, we want to return a point p_j such that dist(q,p_j) < c * dist(q,p_i), for some approximation factor c.
  Here is a geometric fact you can use. Say we locate q in the tree, in a leaf cell of size s. There has to be a point of P in the parent of s, so we know that we can find some p_j at distance at most 2s sqrt(2) from q. Within the ball of radius s sqrt(2) around q, there can be at most a constant number (49? fewer?) of cells of size s/2. Note that some of these cells might have children, some might be leaves, and some might not exist because there are larger leaves. Remember leaves might have points in them.
  Devise an algorithm to use the quad-tree to answer approximate nearest-neighbor queries. What is the approximation factor c you can achieve? I can get 4. How long does it take to answer a query? I can get O(lg n) (under the assumption above about having a nice point set as input).
11/12: We will begin discussion of the paper by Aristides Gionis, Piotr Indyk, and Rajeev Motwani, Similarity search in high dimensions via hashing, from the Proceedings of the 25th VLDB Conference, 1999. It is available through Citeseer, among other places. Deb takes notes.
11/15: Discussion of homework question.
11/17: Finish analysis of high-dimensional similarity search. Carlos takes notes.
11/19: Presentation of paper by Dominique Attali and Jean-Daniel Boissonnat, A Linear Bound on the Complexity of the Delaunay Triangulation of Points on Polyhedral Surfaces. Discrete and Computational Geometry. Vol. 31, No. 3, February, pages 369--384, 2004. The journal is available electronically through the library. Minya takes notes.
11/22: Power diagrams and multiplicativly weighted Voronoi diagrams. Chris takes notes.
11/24: Low-dimensional linear programming.
11/26: Holiday
11/29: Class postponed.
12/1: Final, in class. Open book, open notes, no computers.
12/3: Valerie and Ben.
12/6: 11 AM, Scott and Min Yu. 2PM, Carlos and Yue.
12/8: Chris and Minya.
12/10: Taylor and Deb.