Computational Geometry

SoCG Best Paper

Winners

2026 Anirban Ghosh, “Constructing Doppelgängers of Greedy Geometric Spanners in Practice” (practice)
Vincent Delecroix, Oscar Fontaine, and Arnaud de Mesmay, “On the size of k-irreducible triangulations” (theory)
2025 Timothy M. Chan and Isaac M. Hair, “A Linear Time Algorithm for the Maximum Overlap of Two Convex Polygons Under Translation”
2024 Sayan Bandyapadhyay and Jie Xue, “An O(n log n)-Time Approximation Scheme for Geometric Many-to-Many Matching”
History
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”
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 Paper

Winners

2026 Lotte Blank, “Fréchet Distance in the Imbalanced Case”
2025 Ángel Javier Alonso, “A Sparse Multicover Bifiltration of Linear Size”
2024 Rhuaidi Antonio Burke, “Practical Software for Triangulating and Simplifying 4-Manifolds”

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. A more detailed description of the criteria and procedure can be found in this document. The student presentation logo is available here in PDF and PNG format.

Winners

2026 Jonathan Conroy: “Dynamic Light Spanners for Doubling Metrics”
2025 Sarita de Berg: “Nearest Neighbor Searching in a Dynamic Simple Polygon”
2024 Isaac M. Hair: “Convex Polygon Containment: Improving Quadratic to Near Linear Time”
History
2023 Sarita de Berg: “The Complexity of Geodesic Spanners”
2022 Paul Jungeblut: “The Complexity of the Hausdorff Distance”
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 Outstanding Reviewer Award

Winners

2026 Nadav Dym, Ondřej Draganov, Elizaveta Streltsova
2025 Greg Aloupis, Robin Belton, Jeff Erickson, Daniel Frishberg, Matt Gibson-Lopez, Xavier Goaoc, Haoqiang Huang, Chaya Keller, Linda Kleist, Stephen Kobourov, Arnaud de Mesmay, Liz Munch, Yoshio Okamoto, Bastien Rivier, Morteza Saghafian, Frank Staals, Jack Spalding-Jamieson, Csaba D. Tóth, Mathijs Wintraecken, Da Wei Zheng

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

2025–2026
  • Pankaj K. Agarwal (Duke University)
  • Mark de Berg (TU Eindhoven)
  • Siu-Wing Cheng (HKUST)
  • Yusu Wang (UCSD)
History
2023–2024
  • Pankaj K. Agarwal (Duke University)
  • Siu-Wing Cheng (HKUST)
  • Raimund Seidel (Saarland University)
2020–2022
  • Pankaj K. Agarwal (Duke University)
  • Dan Halperin (Tel Aviv University)
  • Raimund Seidel (Saarland University)

Winners

2026 Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab S. Mirrokni, “Locality-Sensitive Hashing Scheme Based on p-stable Distributions” (20th SoCG, 2004)
Klara Kedem and Micha Sharir, “An Efficient Algorithm for Planning Collision-Free Translational Motion of a Convex Polygonal Object in 2-dimensional Space Amidst Polygonal Obstacles” (1st SoCG, 1985)
The journal version appeared in Discrete Comput. Geom. 1: 59–70 (1986).
2025 Raimund Seidel, “Linear Programming and Convex Hulls Made Easy” (6th SoCG, 1990)
The journal version appeared in Discrete Comput. Geom. 6: 423–434 (1991).
David Cohen-Steiner, Herbert Edelsbrunner, and John Harer, “Stability of Persistence Diagrams” (21st SoCG, 2005)
The journal version appeared in Discrete Comput. Geom. 37: 103–120 (2007).
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).
History
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).
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 Discrete 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 Discrete Comput. Geom. 4: 387–421 (1989).