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/
