On Fri, Jan 20, 2006 at 04:50:17PM -0500, Tom Lane wrote:
> I wonder if there is a way to improve on that.
http://www.cs.uwaterloo.ca/~tmchan/slide_isaac.ps:
The diameter problem has been studied extensively in the traditional model.
Although O(n log n) algorithms have been given for d = 2 and d = 3, only
slightly subquadratic algorithms are known for higher dimensions.
It doesn't mention a date, but has references to at least 2004-papers, so I'm
fairly sure nothing big has happened since that.
It sounds like we either want to go for an approximation, or just accept that
it's a lot of work to get it better than O(n^2). Or, of course, find some
special property of our problem that makes it easier than the general problem
:-)
/* Steinar */
--
Homepage: http://www.sesse.net/