Presentation in class (15 minutes + 5 minutes for discussion/questions).
These will be scheduled for the last 5 classes, Nov. 21, 23, 28, 30, Dec 5.
Written Report due December 16, 2020.
For your project you must read and report on at least one paper in computational geometry. Many suggestions have been given in the lecture slides, and you can find some more suggestions below.
You may pick a paper not on the list -- choose a paper from a reputable computational geometry (or algorithms or graphics) journal or conference, and check your choice with me. Note: make sure you use the journal version of your paper if there is one (use scholar.google.ca to check this).
You should not report on a survey paper, though you might use a survey paper to help you find a good paper on a particular topic.
An alternative to the single-paper report is to tackle an open problem, in which case you should survey what is known and suggest ideas of how to tackle the problem. You do not need to solve the problem.
Your presentation will be judged based on how well you comprehend and communicate the results in the paper. Keep in mind that your audience is the other students in the class. Specific criteria are: (1) quality of presentation; (2) understanding of the paper; (3) handling of questions.
Your written report should do two things: (1) summarize the paper you presented in class; and (2) discuss what comes next on the topic, either work that WAS done in the case of an older paper, or work that MIGHT be done next in the case of a newer paper. Aim for approximately 5 pages. Do not simply repeat the contents of the paper.
Suggestions, some from lectures, some extra. Click on triangle for list of papers:
this is not a comprehensive list, just some starting points!
visibility
Abrahamsen, Mikkel, Anna Adamaszek, and Tillmann Miltzow. "The Art Gallery Problem is $\exists\mathbb {R} $-complete." Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC). ACM, 2018. https://dl.acm.org/citation.cfm?id=3188868
Ben-Moshe, Boaz, Olaf Hall-Holt, Matthew J. Katz, and Joseph SB Mitchell. "Computing the visibility graph of points within a polygon." In Proceedings of the twentieth annual symposium on Computational geometry, pp. 27-35. ACM, 2004.
Eppstein, David, Michael T. Goodrich, and Nodari Sitchinava. "Guard placement for efficient point-in-polygon proofs." Proceedings of the twenty-third annual symposium on Computational geometry. ACM, 2007.
Biedl, Therese, Mohammad T. Irfan, Justin Iwerks, Joondong Kim, and Joseph SB Mitchell. "The art gallery theorem for polyominoes." Discrete & Computational Geometry 48, no. 3 (2012): 711-720.
Chazelle, Bernard, David P. Dobkin, Nadia Shouraboura, and Ayellet Tal. "Strategies for polyhedral surface decomposition: An experimental study." Computational Geometry 7, no. 5 (1997): 327-342.
Melkman, Avraham A. "On-line construction of the convex hull of a simple polyline." Information Processing Letters 25.1 (1987): 11-12. [convex hull of a simple polygon in O(n)]
Aronov, Boris, Otfried Cheong, Michael Gene Dobbins, and Xavier Goaoc. "The Number of Holes in the Union of Translates of a Convex Set in Three Dimensions." Symposium on Computational Geometry, 2016.
Chan, Timothy M. "Optimal output-sensitive convex hull algorithms in two and three dimensions." Discrete & Computational Geometry 16.4 (1996): 361-368.
Balzer, Michael, and Oliver Deussen. "Voronoi Treemaps." Proceedings of the Proceedings of the 2005 IEEE Symposium on Information Visualization. IEEE Computer Society, 2005.
Chan, Timothy M., and Mihai Patrascu. "Transdichotomous results in computational geometry, I: Point location in sublogarithmic time." SIAM Journal on Computing 39.2 (2009): 703-729.
Guibas, Leonidas, and Daniel Russel. "An empirical comparison of techniques for updating Delaunay triangulations." Proceedings of the twentieth annual symposium on Computational geometry. ACM, 2004.
Amenta, Nina, Sunghee Choi, and Günter Rote. "Incremental constructions con BRIO." Proceedings of the nineteenth annual symposium on Computational geometry. ACM, 2003.
[randomized incremental constructions in practice]
Loffler, Maarten, and Wolfgang Mulzer. "Triangulating the square and squaring the triangle: quadtrees and Delaunay triangulations are equivalent." SIAM Journal on Computing 41.4 (2012): 941-974.
van Kreveld, Marc, Maarten Löffler, and Lionov Wiratma. "On Optimal Polyline Simplification Using the Hausdorff and Fréchet Distance." Proc. Symposium on Computational Geometry. LIPIcs-Leibniz International Proceedings in Informatics. Vol. 99. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. http://drops.dagstuhl.de/opus/volltexte/2018/8769/
Chang, Hsien-Chih, and Jeff Erickson. "Untangling Planar Curves." LIPIcs-Leibniz International Proceedings in Informatics. Vol. 51. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016.
Cardinal, Jean, Timothy M. Chan, John Iacono, Stefan Langerman, and Aurélien Ooms. "Subquadratic Encodings for Point Configurations." Proc. Symposium on Computational Geometry. In LIPIcs-Leibniz International Proceedings in Informatics, vol. 99. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. http://drops.dagstuhl.de/opus/volltexte/2018/8733/
triangulating point sets
Aichholzer, Oswin, Victor Alvarez, Thomas Hackl, Alexander Pilz, Bettina Speckmann, and Birgit Vogtenhuber. "An improved lower bound on the number of triangulations." In 32nd International Symposium on Computational Geometry (SoCG 2016).
Remy, Jan, and Angelika Steger. "A quasi-polynomial time approximation scheme for minimum weight triangulation." Journal of the ACM (JACM) 56, no. 3 (2009): 15.
Shewchuk, Jonathan Richard. "Delaunay refinement algorithms for triangular mesh generation." Computational geometry 22.1 (2002): 21-74. [winner of Test of Time award]
Bern, Marshall, and David Eppstein. "Mesh generation and optimal triangulation." Computing in Euclidean geometry 4 (1995): 47-123. [a survey, but look here for many good papers]
Amenta, Nina, Sunghee Choi, and Ravi Krishna Kolluri. "The power crust, unions of balls, and the medial axis transform." Computational Geometry 19.2 (2001): 127-153.
Barequet, Gill, Michael T. Goodrich, Aya Levi-Steiner, and Dvir Steiner. "Contour interpolation by straight skeletons." Graphical Models 66, no. 4 (2004): 245-260.
Agarwal, Pankaj K., Lars Arge, and Frank Staals. "Improved Dynamic Geodesic Nearest Neighbor Searching in a Simple Polygon." Proc. Symposium on Computational Geometry. LIPIcs-Leibniz International Proceedings in Informatics. Vol. 99. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. http://drops.dagstuhl.de/opus/volltexte/2018/8717/
spanners
Gao, Jie, Leonidas J. Guibas, John Hershberger, Li Zhang, and An Zhu. "Geometric spanners for routing in mobile networks." IEEE journal on selected areas in communications 23, no. 1 (2005): 174-185.
LaValle, Steven M. Planning algorithms. Cambridge university press, 2006.
Demaine, Erik D., Sándor P. Fekete, Phillip Keldenich, Christian Scheffer, and Henk Meijer. "Coordinated Motion Planning: Reconfiguring a Swarm of Labeled Robots with Bounded Stretch." Proc. Symposium on Computational Geometry. LIPIcs-Leibniz International Proceedings in Informatics. Vol. 99. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. http://drops.dagstuhl.de/opus/volltexte/2018/8742/
O'Rourke, Joseph. "Edge-Unfolding Nearly Flat Convex Caps." Proc. Symposium on Computational Geometry, LIPIcs-Leibniz International Proceedings in Informatics. Vol. 99. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. http://drops.dagstuhl.de/opus/volltexte/2018/8777/
Connelly, Robert, Erik D. Demaine, Martin L. Demaine, Sándor P. Fekete, Stefan Langerman, Joseph SB Mitchell, Ares Ribó, and Günter Rote. "Locked and unlocked chains of planar shapes." Discrete & Computational Geometry 44, no. 2 (2010): 439-462.
Hawkes, Elliot, B. An, N. M. Benbernou, H. Tanaka, S. Kim, E. D. Demaine, D. Rus, and R. J. Wood. "Programmable matter by folding." Proceedings of the National Academy of Sciences 107, no. 28 (2010): 12441-12445.
Schreiber, Yevgeny, and Micha Sharir. "An Optimal-Time Algorithm for Shortest Paths on a Convex Polytope in Three Dimensions." Discrete & Computational Geometry 1.39 (2008): 500-579.
Dror, Moshe, Alon Efrat, Anna Lubiw, and Joseph SB Mitchell. "Touring a sequence of polygons." In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pp. 473-482. ACM, 2003.
Bereg, Sergey, Prosenjit Bose, Adrian Dumitrescu, Ferran Hurtado, and Pavel Valtr. "Traversing a set of points with a minimum number of turns." Discrete & Computational Geometry 41, no. 4 (2009): 513-532.
