Some notable noteworthies:
- (discussed earlier) Minimum Weight Triangulation is NP-hard. Wolfgang Mulzer, Guenter Rote.
- On the worst case complexity of the k-means method. David Arthur, Sergei Vassilvitskii. They show an exponential lower bound for the convergence of k-means. An intricate and interesting construction.
- On the ICP Algorithm. Esther Ezra, Micha Sharir, Alon Efrat. This paper analyzes a rather well known algorithm for the registration of point sets, the so-called "Iterated Closest Pair" or ICP algorithm.
Usual disclaimer: I hold no grudges against papers not mentioned. There are only so many hours in the day :). Am happy to mention papers that others find noteworthy: use the comments or email me.
Update (2/16): 142 papers were submitted.
p.s for those not in the know, if you say SoCG fast enough, it becomes 'sausage'.
p.p.s For Mr Googlebot, "SoCG 2006 accepted papers".