SoCG Test of Time

Award Winners

  2024

• Nina Amenta, Marshall W. Bern. Surface Reconstruction by Voronoi Filtering 14th Symposium on Computational Geometry 1998:39-48. The journal version appeared in Discrete Comput. Geom. 22(4): 481-504 (1999).
  
• David Avis, Komei Fukuda. A Pivoting Algorithm for Convex Hulls and Vertex Enumeration of Arrangements and Polyhedra. 14th Symposium on Computational Geometry 1991: 98-104. The journal version appeared in Discrete Comput. Geom. 8: 295-313 (1992).

Call for nominations

• The CGAL Project: www.cgal.org, started in 1996.
  
• Herbert Edelsbrunner, Leonidas J. Guibas, Micha Sharir. The complexity of many faces in arrangements of lines and of segments, 4th Symposium on Computational Geometry 1988:44-55. The journal version appeared in Discrete Comput. Geom. 5(2): 161-196 (1990).

Call for nominations

• Helmut Alt, Michael Godau. Measuring the Resemblance of Polygonal Curves. 8th Symposium on Computational Geometry 1992:102-109. The journal version appeared in Internat. J. Comput. Geom. Appl. 5(1-2): 75-91 (1995).
  
• Jiří Matoušek. Efficient Partition Trees. 7th Symposium on Computational Geometry 1991:1-9. The journal version appeared in Discrete Comput. Geom. 8(3): 315-334 (1992).

Call for nominations

• Tapas Kanungo, David M. Mount, Nathan S. Netanyahu, Christine D. Piatko, Ruth Silverman, Angela Y. Wu. The analysis of a simple k-means clustering algorithm. 16th Symposium on Computational Geometry 2000:100-109. The journal version appeared in IEEE Trans. Pattern Anal. Mach. Intell. 24(7): 881-892 (2002).
  
• L. Paul Chew. Constrained Delaunay Triangulations. 3rd Symposium on Computational Geometry 1987:215-222. The journal version appeared in Algorithmica 4(1): 97-108 (1989).

Call for nominations

• David Haussler, Emo Welzl. Epsilon-Nets and Simplex Range Queries. 2nd Symposium on Computational Geometry 1986:61-71. The journal version appeared in Discret. Comput. Geom. 2: 127-151 (1987).
  
• Kenneth L. Clarkson. Applications of Random Sampling in Computational Geometry, II. 4th Symposium on Computational Geometry 1988: 1-11, and
  Kenneth L. Clarkson, Peter W. Shor. Algorithms for Diametral Pairs and Convex Hulls That Are Optimal, Randomized, and Incremental. 4th Symposium on Computational Geometry 1988:12-17.
  The two papers were merged into a single paper in the journal version, which appeared in Discret. Comput. Geom. 4: 387-421 (1989).

Call for nominations