SoCG Test of Time

Award Winners

• 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