
CS 763 Project, University of Waterloo



Presentation (15 minutes + 5 minutes for discussion/questions) to be done in class.



Written Report due December 5 (later if I'm allowed to).



For your class presentation you must read and report on one paper in computational geometry. A list of suggestions is 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. 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 singlepaper report is to tackle an open problem, in which case you should survy what is known and suggest ideas of how to tackle 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.



Your written report should summarize the paper you presented in class PLUS 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.



For ideas and collections of papers try the following links:




The Open Problems Project  you could pick an open problem and report on the background/partial results





the Handbook of Computational Geometry has survey articles on many topics (I have a copy you may borrow)





computational geometry journals:




Discrete and Computational Geometry





Computational Geometry: Theory and Applications





Journal of Computational Geometry





International Journal of Computational Geometry





Symposium on Computational Geometry




Some possible topics (click on triangle for list of papers):



this is not a comprehensive list, just some starting points!




visibility




BenMoshe, Boaz, Olaf HallHolt, 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. 2735. ACM, 2004.





Kawamura, Akitoshi, Sonoko Moriyama, Yota Otachi, and János Pach. "A Lower Bound on Opaque Sets." Symposium on Computational Geometry, 2016.





Eppstein, David, Michael T. Goodrich, and Nodari Sitchinava. "Guard placement for efficient pointinpolygon proofs." Proceedings of the twentythird 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): 711720.





simple polygons




Akitaya, Hugo A., Greg Aloupis, Jeff Erickson, and Csaba Tóth. "Recognizing Weakly Simple Polygons." In LIPIcsLeibniz International Proceedings in Informatics, vol. 51. Schloss DagstuhlLeibnizZentrum fuer Informatik, 2016.





triangulating polygons and planar graphs




Amato, Nancy M., Michael T. Goodrich, and Edgar A. Ramos. "Lineartime triangulation of a simple polygon made easier via randomization." Proceedings of the sixteenth annual symposium on Computational geometry. ACM, 2000.





Bishop, Christopher J. "Nonobtuse triangulations of PSLGs." Discrete & Computational Geometry (2016): 150.





decomposing polygons/polyhedra




Lien, JyhMing, and Nancy M. Amato. "Approximate convex decomposition of polygons." Computational Geometry 35.1 (2006): 100123.





Zuckerberger, Emanoil, Ayellet Tal, and Shymon Shlafman. "Polyhedral surface decomposition with applications." Computers & Graphics 26.5 (2002): 733743.





Chazelle, Bernard, David P. Dobkin, Nadia Shouraboura, and Ayellet Tal. "Strategies for polyhedral surface decomposition: An experimental study." Computational Geometry 7, no. 5 (1997): 327342.





convex hull and problems on convex polyhedra




Avis, David, David Bremner, and Raimund Seidel. "How good are convex hull algorithms?." Computational Geometry 7.5 (1997): 265301.





Chan, Timothy M. "Dynamic planar convex hull operations in nearlogarithmic amortized time." Journal of the ACM (JACM) 48.1 (2001): 112.





Melkman, Avraham A. "Online construction of the convex hull of a simple polyline." Information Processing Letters 25.1 (1987): 1112. [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 outputsensitive convex hull algorithms in two and three dimensions." Discrete & Computational Geometry 16.4 (1996): 361368. We did 2D in class already.





Voronoi diagrams, Delaunay triangulations




Edelsbrunner, Herbert, and Raimund Seidel. "Voronoi diagrams and arrangements." Discrete & Computational Geometry 1.1 (1986): 2544.





Balzer, Michael, and Oliver Deussen. "Voronoi Treemaps." Proceedings of the Proceedings of the 2005 IEEE Symposium on Information Visualization. IEEE Computer Society, 2005.





Allen, Sarah R., Luis Barba, John Iacono, and Stefan Langerman. "Incremental Voronoi diagrams." Symposium on Computational Geometry, 2016.





Chan, Timothy M., and Mihai Patrascu. "Transdichotomous results in computational geometry, I: Point location in sublogarithmic time." SIAM Journal on Computing 39.2 (2009): 703729.





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): 941974.





curves in the plane




Chang, HsienChih, and Jeff Erickson. "Untangling Planar Curves." LIPIcsLeibniz International Proceedings in Informatics. Vol. 51. Schloss DagstuhlLeibnizZentrum fuer Informatik, 2016.





min spanning tree




Chazelle, Bernard. "A minimum spanning tree algorithm with inverseAckermann type complexity." Journal of the ACM (JACM) 47.6 (2000): 10281047.





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





Mulzer, Wolfgang, and Günter Rote. "Minimumweight triangulation is NPhard." Journal of the ACM (JACM) 55.2 (2008): 11.





Remy, Jan, and Angelika Steger. "A quasipolynomial time approximation scheme for minimum weight triangulation." Journal of the ACM (JACM) 56, no. 3 (2009): 15.





meshing




Shewchuk, Jonathan Richard. "Delaunay refinement algorithms for triangular mesh generation." Computational geometry 22.1 (2002): 2174. [winner of Test of Time award]





Bern, Marshall, and David Eppstein. "Mesh generation and optimal triangulation." Computing in Euclidean geometry 4 (1995): 47123. [a survey, but look here for many good papers]





surface reconstruction and related




Edelsbrunner, Herbert, and Ernst P. Mücke. "Threedimensional alpha shapes." ACM Transactions on Graphics (TOG) 13.1 (1994): 4372.





Amenta, Nina, Sunghee Choi, and Ravi Krishna Kolluri. "The power crust, unions of balls, and the medial axis transform." Computational Geometry 19.2 (2001): 127153.





Barequet, Gill, Michael T. Goodrich, Aya LeviSteiner, and Dvir Steiner. "Contour interpolation by straight skeletons." Graphical Models 66, no. 4 (2004): 245260.





range searching




Agarwal, Pankaj K., Lars Arge, and Jeff Erickson. "Indexing moving points." Journal of Computer and System Sciences 66.1 (2003): 207243.





Agarwal, Pankaj K., and Jeff Erickson. "Geometric range searching and its relatives." Contemporary Mathematics 223 (1999): 156. [this is a survey]





planar point location




Seidel, Raimund, and Udo Adamy. "On the exact worst case query complexity of planar point location." Journal of Algorithms 37.1 (2000): 189217.





Arge, Lars, and Jan Vahrenhold. "I/Oefficient dynamic planar point location." Computational Geometry 29.2 (2004): 147162.





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): 174185.





motion planning and folding




LaValle, Steven M. Planning algorithms. Cambridge university press, 2006.




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): 439462.





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): 1244112445.





robustness, perturbations




Seidel, Raimund. "The nature and meaning of perturbations in geometric computing." Discrete & Computational Geometry 19.1 (1998): 117.





Schirra, Stefan. "Robustness and Precision Issues in Geometric Computation." Handbook of Computational Geometry. Elsevier, 2000. 597632. [a survey]





shortest paths




Schreiber, Yevgeny, and Micha Sharir. "An OptimalTime Algorithm for Shortest Paths on a Convex Polytope in Three Dimensions." Discrete & Computational Geometry 1.39 (2008): 500579.





Dror, Moshe, Alon Efrat, Anna Lubiw, and Joseph SB Mitchell. "Touring a sequence of polygons." In Proceedings of the thirtyfifth annual ACM symposium on Theory of computing, pp. 473482. 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): 513532.



