CS 763 Project, University of Waterloo
 
Fall 2022, Anna Lubiw
 
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.
 
*
Google Scholar scholar.google.ca
*
The Open Problems Project -- you could pick an open problem and report on the background/partial results. Warning: this list is not up-to-date.
cs.smith.edu—TOPP
V
computational geometry journals:
*
Discrete and Computational Geometry
link.springer.com—454
>
Computational Geometry: Theory and Applications
www.sciencedirect.com—09257721
*
the Handbook of Computational Geometry has survey articles on many topics (I have a copy you may borrow)
books.google.com—books
*
Journal of Computational Geometry
jocg.org—jocg
*
International Journal of Computational Geometry
www.worldscientific.com—ijcga
*
Symposium on Computational Geometry
www.computational-geometry.org
For ideas and collections of papers try the following links:
 
*
the Handbook of Computational Geometry https://ocul-wtl.primo.exlibrisgroup.com/permalink/01OCUL_WTL/5ob3ju/alma9951544243505162
*
Symposium on Computational Geometry
www.computational-geometry.org
*
Google Scholar scholar.google.ca
V
computational geometry journals:
*
Discrete and Computational Geometry
link.springer.com—454
*
Computational Geometry: Theory and Applications
www.sciencedirect.com—09257721
*
Journal of Computational Geometry
jocg.org—jocg
*
International Journal of Computational Geometry
www.worldscientific.com—ijcga
 
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
V
*
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.
portal.acm.org—citation.cfm
V
*
Kawamura, Akitoshi, Sonoko Moriyama, Yota Otachi, and János Pach. "A Lower Bound on Opaque Sets." Symposium on Computational Geometry, 2016.
drops.dagstuhl.de—5938
V
*
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.
dl.acm.org—citation.cfm
V
*
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.
link.springer.com—s00454-012-9429-1
>
triangulating polygons and planar graphs
V
*
Bishop, Christopher J. "Nonobtuse triangulations of PSLGs." Discrete & Computational Geometry (2016): 1-50.
link.springer.com—s00454-016-9772-8
>
decomposing polygons/polyhedra
V
*
Lien, Jyh-Ming, and Nancy M. Amato. "Approximate convex decomposition of polygons." Computational Geometry 35.1 (2006): 100-123.
www.sciencedirect.com—S0925772105001008
V
*
Zuckerberger, Emanoil, Ayellet Tal, and Shymon Shlafman. "Polyhedral surface decomposition with applications." Computers & Graphics 26.5 (2002): 733-743.
www.sciencedirect.com—S0097849302001280
V
*
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.
www.sciencedirect.com—S0925772196000247
>
convex hull and problems on convex polyhedra
V
*
Avis, David, David Bremner, and Raimund Seidel. "How good are convex hull algorithms?." Computational Geometry 7.5 (1997): 265-301.
www.sciencedirect.com—S0925772196000235
V
*
Chan, Timothy M. "Dynamic planar convex hull operations in near-logarithmic amortized time." Journal of the ACM (JACM) 48.1 (2001): 1-12.
portal.acm.org—citation.cfm
V
*
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)]
www.ime.usp.br—melkman.pdf
V
*
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.
drops.dagstuhl.de—5902
V
*
Chan, Timothy M. "Optimal output-sensitive convex hull algorithms in two and three dimensions." Discrete & Computational Geometry 16.4 (1996): 361-368.
We did 2D in class already.
www.springerlink.com—uctv1yw58xpd7rkq
>
Voronoi diagrams, Delaunay triangulations
V
*
Edelsbrunner, Herbert, and Raimund Seidel. "Voronoi diagrams and arrangements." Discrete & Computational Geometry 1.1 (1986): 25-44.
link.springer.com—BF02187681
V
*
Balzer, Michael, and Oliver Deussen. "Voronoi Treemaps." Proceedings of the Proceedings of the 2005 IEEE Symposium on Information Visualization. IEEE Computer Society, 2005.
ieeexplore.ieee.org—1532128
V
*
Allen, Sarah R., Luis Barba, John Iacono, and Stefan Langerman. "Incremental Voronoi diagrams." Symposium on Computational Geometry, 2016.
drops.dagstuhl.de—5907
V
*
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.
epubs.siam.org—07068669X
V
*
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.
dl.acm.org—citation.cfm
V
*
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]
http://doi.acm.org.proxy.lib.uwaterloo.ca/10.1145/777792.777824
V
*
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.
epubs.siam.org—110825698
>
curves and polylines in the plane
*
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/
V
*
Chang, Hsien-Chih, and Jeff Erickson. "Untangling Planar Curves." LIPIcs-Leibniz International Proceedings in Informatics. Vol. 51. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016.
drops.dagstuhl.de—5921
>
encoding point sets
*
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
V
*
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).
drops.dagstuhl.de—5899
V
*
Mulzer, Wolfgang, and Günter Rote. "Minimum-weight triangulation is NP-hard." Journal of the ACM (JACM) 55.2 (2008): 11.
dl.acm.org—citation.cfm
V
*
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.
dl.acm.org—citation.cfm
>
meshing
V
*
Shewchuk, Jonathan Richard. "Delaunay refinement algorithms for triangular mesh generation." Computational geometry 22.1 (2002): 21-74. [winner of Test of Time award]
www.sciencedirect.com—S0925772101000475
V
*
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]
people.eecs.berkeley.edu—BernEppstein.pdf
>
surface reconstruction and related
V
*
Edelsbrunner, Herbert, and Ernst P. Mücke. "Three-dimensional alpha shapes." ACM Transactions on Graphics (TOG) 13.1 (1994): 43-72.
portal.acm.org—citation.cfm
V
*
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.
www.sciencedirect.com—S0925772101000177
V
*
Barequet, Gill, Michael T. Goodrich, Aya Levi-Steiner, and Dvir Steiner. "Contour interpolation by straight skeletons." Graphical Models 66, no. 4 (2004): 245-260.
www.sciencedirect.com—S1524070304000153
>
range searching
V
*
Agarwal, Pankaj K., Lars Arge, and Jeff Erickson. "Indexing moving points." Journal of Computer and System Sciences 66.1 (2003): 207-243.
www.sciencedirect.com—S0022000002000351
V
*
Agarwal, Pankaj K., and Jeff Erickson. "Geometric range searching and its relatives." Contemporary Mathematics 223 (1999): 1-56. [this is a survey]
compgeom.cs.uiuc.edu—survey.html
>
planar point location
V
*
Seidel, Raimund, and Udo Adamy. "On the exact worst case query complexity of planar point location." Journal of Algorithms 37.1 (2000): 189-217.
www.sciencedirect.com—S0196677400911015
V
*
Arge, Lars, and Jan Vahrenhold. "I/O-efficient dynamic planar point location." Computational Geometry 29.2 (2004): 147-162.
www.sciencedirect.com—S0925772104000434
>
nearest neighbours
*
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
V
*
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.
ieeexplore.ieee.org—1374969
>
motion planning and folding
*
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/
V
*
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.
link.springer.com—s00454-010-9262-3
V
*
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.
www.pnas.org—12441.short
>
robustness, perturbations
V
*
Seidel, Raimund. "The nature and meaning of perturbations in geometric computing." Discrete & Computational Geometry 19.1 (1998): 1-17.
link.springer.com—PL00009330
V
*
Schirra, Stefan. "Robustness and Precision Issues in Geometric Computation." Handbook of Computational Geometry. Elsevier, 2000. 597-632. [a survey]
Robustness and precision issues in geometric computation
>
shortest paths
V
*
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.
link.springer.com—978-0-387-87363-3_27
V
*
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.
portal.acm.org.proxy.lib.uwaterloo.ca—citation.cfm
V
*
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.
link.springer.com—s00454-008-9127-1