For most papers we read, you will post reaction notes prior to our
class meeting to help prepare you for discussing the paper. You will
also have an opportunity read other student's reaction notes prior to
the class meeting.
Reaction notes should should reflect your critical reading of the paper.
Some questions to think about as you read:
Did the authors do what they said they were going to do? What are the
important ideas (just because an author says something is important doesn't
mean it necessarily is)? Do their results make sense? Are their methods
sound? Are there weaknesses in their solution? What assumptions are they
making? How does their work fit in with other similar work? What improvements
and/or extensions to the area do they contribute? Are there terms, ideas,
techniques, that you don't understand?
Your reaction notes should be structured in the following way:
A 1 paragraph summary of the paper. A summary
of what the work is, what problem(s) it addresses, and the results
or new technique (if applicable). Also, include a short list of
the strengths and weaknesses of the work, and list how it is
related to other work we have read (when applicable).
- Answer to Specific Question(s):
A 1-2 paragraph answer to
the specific question(s) associated with this paper.
- A list of questions you have about this paper:
If there are terms, ideas, techniques that you don't understand,
list them here. However, for terms you don't understand
also try to find the answer yourself by using on-line sources.
If you find an answer, please leave the listing of the term on your
reaction notes; it is helpful to me to see which terms are new to
students so that I can make sure that we discuss their meaning.
Submitting Reaction Notes
The papers listed below should be read prior to the class meeting
for which they are assigned, and your reaction notes should be
using handin97 before 8:00pm the day before each class:
- write-up your reaction notes in an ascii file.
- submit them by running handin97 before 8:00pm the
day before each class meeting
- by 8:10pm you can run update97
to get a copy of every student's reaction notes. These are good to look at
prior to our class meeting to help prepare you for discussion.
For guidelines on how to read a research paper, check out Prof. Newhall's reading tips
Self-Evaluation and Summary
After each class discussion, you will complete a self-evaluation of
your participation in discussion and you will write a 1 paragraph summary
of the class's critical evaluation of the paper as we discussed it. Details to appear.
Viewing and Printing Papers
You can view most postscript files (and gziped postscript files)
using gv on our system:
% gv file.ps.gz
gv cannot handle some versions of compressed postscript, in this case you should
save a copy of the paper.ps.gz file, gunzip it, and
then either view it using gs or convert it to pdf and view it using acroread:
% gunzip file.ps.gz
% gs file.ps
% ps2pdf file.ps
% acroread file.pdf
You can print postscript using lpr, or print 2-up postscript files using mpage
% lpr file.ps
% mpage -2 -M-10 -dp file.ps | lpr
You can view (and print) pdf files using acroread:
% acroread file.pdf
- Read chapter 1 of the text. Make sure you follow the two convex hull
algorithms. Make a note of any questions you may have.
- Read W. Eddy A New Convex Hull Algorithm for Planar
- Read F. P. Preparata and S. J. Hong Convex hulls of Finite Sets of Points in Two and Three Dimensions pdf
- Read G. Toussaint Solving Geometric Problems with the Rotating Calipers ps
- Read chapter 2 of the text with emphasis on line segment intersection
- Read T. Chan Optimal Output-Sensitive Convex Hull Algorithms in Two and Three Dimensions ps
- Finish chapter 2 of the text
- J. Hershberger and J. Snoeyink Speeding Up the Douglas-Peucker
Line-Simplification Algorithm ps
- Review Hershberger and Snoeyink. Can you construct a non-intersecting polyline that will have self-intersections after simplification?
- Read Chapter5 of the text excluding 5.6 on fractional cascading. In your reaction describe the tradeoffs between the range tree and the kd-tree and describe a situation where you might prefer one over the other.
- Chapter 5.6 on fractional cascading. Chapter 14 on Quad trees
- L. Palazzi and J. Snoeyink Counting and Reporting Red/Blue Segment Intersections pdf
- P. Lindstrom and V. Pascucci Visualization of Large Terrains Made Easy pdf. A longer version of this paper is also available if you want to follow up on some detail.
L. Arge et al. The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree pdf.
The Priority R-Tree has many similarities to the kd-tree (the database version of kd-tree is a kdb-tree, which is extremely similar to the PR-tree), but the authors claim that a standard R-tree can visit all nodes of the tree and report zero results. This does not happen in the kd-tree. Briefly explain in your reaction how this is possible and be prepared to draw an example in class.
Chapter 6 on Planar point location. You may skip 6.4
N. Sarnak and R. Tarjan Planar Point Location Using Persistent Search Trees ps.
If you aren't a big fan of red-black trees but like B-trees, you can read Arge et al. I/O-efficient point location using persistent B-trees pdf
. It's the same idea, but the balancing is a bit easier in my (biased) opinion.
- Chapter 7 in the text on Voronoi diagrams. We will also cover Chapter 6 from last week.
- Chapter 8.2 on Duality and 9.1-9.4 on Delaunay Triangulations.
- DT have connections to Voronoi Diagrams through duality and QuadTrees though mesh triangulations. In your reaction discuss at least one situation where one approach (QuadTrees, Voronoi, Delaunay) might be preferred over another similar approach.
- Read 8.3/8.4 on Arrangements. No reaction needed. Spring break starts a bit early.
- Read sections 1.1-1.4 pdf
- Project proposal due
- Read Eppstein, Goodrich, and Sun: The Skip Quadtree: A Simple Dynamic Data Structure for Multidimensional Data pdf
Thursday: No class
- Read Jagadish: Linear Clustering of Objects with Multiple Attributes pdf
Thursday: Progress reports
Tuesday: Progress reports
- Read Macmillan: Redistricting in a GIS environment: An optimisation algorithm using switching-points pdf
- Read Eppstein et al.: Maintenance of a Minimum Spanning Forest in a Dynamic Plane Graph pdf
- Rough Draft of final project due.
- Read Bender and Farach-Colton: The LCA Problem Revisited pdf