Computational Geometry

SoCG Best Paper

Winners

2024 Sayan Bandyapadhyay and Jie Xue, “An O(n log n)-Time Approximation Scheme for Geometric Many-to-Many Matching”
2023 Mickaël Buchet, Bianca B. Dornelas, and Michael Kerber, “Sparse Higher Order Čech Filtrations”
2022 Daniel Rutschmann and Manuel Wettstein, “Chains, Koch Chains, and Point Sets with Many Triangulations”
History
2021 Peyman Afshani and Pingan Cheng, “Lower Bounds for Semialgebraic Range Searching and Stabbing Problems”
2020 Xavier Goaoc and Emo Welzl, “Convex Hulls of Random Order Types”
2019 Vincent Cohen-Addad, Éric Colin de Verdière, Dániel Marx, and Arnaud de Mesmay, “Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs”
2018 Xavier Goaoc, Pavel Paták, Zuzana Patáková, Martin Tancer, and Uli Wagner, “Shellability is NP-complete”
2017 Vincent Despré and Francis Lazarus, “Computing the Geometric Intersection Number of Curves”
2016 Boris Aronov, Otfried Cheong, Michael Gene Dobbins, and Xavier Goaoc, “The Number of Holes in the Union of Translates of a Convex Set in Three Dimensions”
2015 Jirí Matoušek and Aleksandar Nikolov, “Combinatorial Discrepancy for Boxes via the γ₂ Norm”
2014 Jirí Matoušek, Eric Sedgwick, Martin Tancer, and Uli Wagner, “Embeddability in the 3-Sphere is Decidable”
2013 Victor Alvarez and Raimund Seidel, “A Simple Aggregative Algorithm for Counting Triangulations of Planar Point Sets and Related Problems”
2012 Éric Colin de Verdière, Grégory Ginot, and Xavier Goaoc, “Multinerves and Helly numbers of acyclic families”
Natan Rubin, “On Topological Changes in the Delaunay Triangulation of Moving Points”

SoCG Best Student Presentation

Since 2012, SoCG has given an award for the best presentation(s) by a student. Candidates are full-time students (any level: undergrad, PhD student, etc.) at time of submission. The winner of the award is selected according to scores given by the audience based on their appreciation of the presentation, including its contents, the quality of the slides, and the presentation skills of the presenter. In case of a tie, several winners can be selected.

Winners

2024 Isaac M. Hair, “Convex Polygon Containment: Improving Quadratic to Near Linear Time”
2023 Sarita de Berg, “The Complexity of Geodesic Spanners”
2022 Paul Jungeblut, “The Complexity of the Hausdorff Distance”
History
2021 Sebastiano Cultrera di Montesano, “Counting Cells of Order-k Voronoi Tessellations in R³ with Morse Theory”
2020 Svenja Griesbach, “Book Embeddings of Nonplanar Graphs with Small Faces in Few Pages”
2019 Ivor van der Hoog, “Preprocessing ambiguous imprecise points”
2018 Ivor van der Hoog, “Dynamic Smooth Compressed Quadtrees” (about the 2018 award)
Aurélien Ooms, “Subquadratic Encodings for Point Configurations”
2017 Zuzana Masárová, “A Proof of the Orbit Conjecture for Flipping Edge-Labelled Triangulations”
2016 Hsien-Chih Chang, “Untangling Planar Curves”
2015 Luis Barba, “A Linear-Time Algorithm for the Geodesic Center of a Simple Polygon”
2014 Quirijn Bouts, “A Framework for Computing the Greedy Spanner”
2013 Luis Barba, “Bichromatic Compatible Matchings”
João Paixão, “Parameterized Complexity of Discrete Morse Theory”
2012 Adam Sheffer, “Counting Plane Graphs: Perfect Matchings, Spanning Cycles, and Kasteleyn’s Technique”

SoCG Test of Time

The SoCG Test of Time Award, instated in 2020, recognizes papers published in the Proceedings of the Annual Symposium on Computational Geometry (SoCG). An award is given to a paper published at SoCG no later than 2004. More than one paper may be selected for the award. Anyone in the Computational Geometry community may nominate a paper; the winners are selected by a committee appointed by the CG Week steering committee. In selecting the winner, the committee pays particular attention to long term impact. This impact can come in many forms and some possibilities are to: (i) open up a new area of research; (ii) introduce new techniques; (iii) solve a problem of lasting importance.

Committees

2023–2024
  • Pankaj K. Agarwal (Duke University)
  • Siu-Wing Cheng (HKUST)
  • Raimund Seidel (Saarland University)
History
2020–2022
  • Pankaj K. Agarwal (Duke University)
  • Dan Halperin (Tel Aviv University)
  • Raimund Seidel (Saarland University)

Winners

2024 Nina Amenta and Marshall W. Bern, “Surface Reconstruction by Voronoi Filtering” (14th SoCG, 1998)
The journal version appeared in Discrete Comput. Geom. 22(4): 481–504 (1999).
David Avis and Komei Fukuda, “A Pivoting Algorithm for Convex Hulls and Vertex Enumeration of Arrangements and Polyhedra” (7th SoCG, 1991)
The journal version appeared in Discrete Comput. Geom. 8: 295–313 (1992).
2023 The CGAL Project (cgal.org), started in 1996.
Herbert Edelsbrunner, Leonidas J. Guibas, and Micha Sharir, “The Complexity of Many Faces in Arrangements of Lines and of Segments” (4th SoCG, 1988)
The journal version appeared in Discrete Comput. Geom. 5(2): 161–196 (1990).
History
2022 Helmut Alt and Michael Godau, “Measuring the Resemblance of Polygonal Curves” (8th SoCG, 1992)
The journal version appeared in Internat. J. Comput. Geom. Appl. 5(1–2): 75–91 (1995).
Jiří Matoušek, “Efficient Partition Trees” (7th SoCG, 1991)
The journal version appeared in Discrete Comput. Geom. 8(3): 315–334 (1992).
2021 Tapas Kanungo, David M. Mount, Nathan S. Netanyahu, Christine D. Piatko, Ruth Silverman, and Angela Y. Wu, “The Analysis of a Simple k-Means Clustering Algorithm” (16th SoCG, 2000)
The journal version appeared in IEEE Trans. Pattern Anal. Mach. Intell. 24(7): 881–892 (2002).
L. Paul Chew, “Constrained Delaunay Triangulations” (3rd SoCG, 1987)
The journal version appeared in Algorithmica 4(1): 97–108 (1989).
2020 David Haussler and Emo Welzl, “Epsilon-Nets and Simplex Range Queries” (2nd SoCG, 1986)
The journal version appeared in Discret. Comput. Geom. 2: 127–151 (1987).
Kenneth L. Clarkson, “Applications of Random Sampling in Computational Geometry, II” (4th SoCG, 1988), and
Kenneth L. Clarkson and Peter W. Shor, “Algorithms for Diametral Pairs and Convex Hulls That Are Optimal, Randomized, and Incremental” (4th SoCG, 1988)
The two papers were merged into a single paper in the journal version, which appeared in Discret. Comput. Geom. 4: 387–421 (1989).