ECS 226: Computational Geometry
Readings and reading questions.
Answers to the
reading questions are due in class, in writing, on the day that
the reading is due.
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.
Added later: survey paper including Toth's lower
bound construction for line segments in the plane (Section 3).
- 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".
- 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
The Delaunay tetrahedralization in R3 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
We will do the analysis in arbitrary (small) dimension d.
Added later: handout on the analysis
of convex hull conflict lists.
- 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(n2) 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?
- 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(vfloor(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.
- 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.