I'm writing in reply to David Avis and Komei Fukuda's message a couple of days ago. It's nice to see some discussion on this mailing list! Especially important discussion!

They raise an issue that was not addressed by the CG Impact Task Force Report: even basic problems like linear programming and convex hull cannot be considered solved outside of the most restrictive model of worst-case complexity. This is a good criticism; when you consider constants and output-sensitivity it is clear that there is a lot of theoretical work still to be done in the core areas.

But I think this is an effect of the dissociation of CG from practice, rather than the cause of the dissociation, as they argue. If the field becomes more concerned with providing convex hull programs, rather than convex hull algorithms, a more realistic model of complexity will take over the culture. If we push practice, theory will follow. So I think the emphasis of the Report was right.

Also I don't think work on LP and convex hull algorithms has been quite as skewed as they portray it to make their (generally valid) point. In LP, Clarkson, Seidel and Kalai / Matousek-Sharir-Welzl addressed the issues of the size of the constant, simplicity, and subexponential simplex algorithms. And Seidel and Avis both worked on output sensitive convex hull algorithms. The problem as I see it is that (except for Avis's qrs and Hohmeyer's LP program) none of this has lead to published software, so the *impact* has been minimal.

Finally, Avis and Fukuda write "We can find no evidence of the methods proposed in CG literature actually being used, in spite of the fact they have been widely known for many years." Two years ago we clocked 890 copies of qhull downloaded from The Geometry Center. I'd expect it's twice that now. Anyone else have any data points? I'd be really curious.

I hope we all get a chance to talk about these issues ``live'' at SCG and WACG (including the technical stuff about Motzkin's algorithm).

See you soon, Nina

PS Avis, Bremner, Seidel, ftp://mutt.cs.mcgill.ca/pub/doc/hgch.ps.gz is indeed pretty interesting!