And it's OUT !!!!

54, count 'em, 54 juicy sausages at the 2006 sausage fair in Sedona. Alas, I submitted a hot dog.

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.

It's worth noting that the latter two papers are both about a rigorous analysis of well known heuristics. Sariel has more notables.

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".

Categories:

• socg