Reaction Notes

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:

1. Summary:
   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).
2. Answer to Specific Question(s):
   A 1-2 paragraph answer to the specific question(s) associated with this paper.
3. 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 submitted using handin97 before 8:00pm the day before each class:

1. write-up your reaction notes in an ascii file.
2. submit them by running handin97 before 8:00pm the day before each class meeting
3. 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 and lpr:

% lpr file.ps
% mpage -2 -M-10 -dp file.ps | lpr

You can view (and print) pdf files using acroread:

% acroread file.pdf

For Thursday:

• 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 Sets ps

For Tuesday:

• 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

For Thursday:

• 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

For Tuesday:

• Finish chapter 2 of the text
• J. Hershberger and J. Snoeyink Speeding Up the Douglas-Peucker Line-Simplification Algorithm ps

For Thursday:

• 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.

For Tuesday:

• Chapter 5.6 on fractional cascading. Chapter 14 on Quad trees
• L. Palazzi and J. Snoeyink Counting and Reporting Red/Blue Segment Intersections pdf

For Wednesday:

• Project 1 is due at 11:59pm

For Tuesday:

• 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.

For Thursday:

• 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. For Tuesday:

• Chapter 7 in the text on Voronoi diagrams. We will also cover Chapter 6 from last week.

For Tuesday:

• 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.

For Thursday:

• Read 8.3/8.4 on Arrangements. No reaction needed. Spring break starts a bit early.

For Thursday:

• Read sections 1.1-1.4 pdf
• Project proposal due

For Tuesday:

• Read Eppstein, Goodrich, and Sun: The Skip Quadtree: A Simple Dynamic Data Structure for Multidimensional Data pdf

Thursday: No class For Tuesday:

• Read Jagadish: Linear Clustering of Objects with Multiple Attributes pdf

Thursday: Progress reports Tuesday: Progress reports

Thursday:

• Read Macmillan: Redistricting in a GIS environment: An optimisation algorithm using switching-points pdf

Tuesday:

• Read Eppstein et al.: Maintenance of a Minimum Spanning Forest in a Dynamic Plane Graph pdf

Thursday:

• Rough Draft of final project due.
• Read Bender and Farach-Colton: The LCA Problem Revisited pdf

Home Page

Last updated: Tuesday, September 22, 2020 at 01:07:44 PM