## [Algorithms] O(NlogN) spatial sort, O(logN)? spatial search, no spatial index

 [Algorithms] O(NlogN) spatial sort, O(logN)? spatial search, no spatial index From: bryan mcnett - 2007-04-30 08:13:59 Attachments: Message as HTML ```Hi, I've been having fun with this algorithm lately. Anyone who's worked with it before, please tell me what you've learned... so far I've had to figure this out by trial and error. The algorithm is an O(NlogN) spatial sort & O(logN)? spatial search, but no spatial index is required. Here's some more: http://www.mcnett.org/ Cheers! Bryan ```

 [Algorithms] O(NlogN) spatial sort, O(logN)? spatial search, no spatial index From: bryan mcnett - 2007-04-30 08:13:59 Attachments: Message as HTML ```Hi, I've been having fun with this algorithm lately. Anyone who's worked with it before, please tell me what you've learned... so far I've had to figure this out by trial and error. The algorithm is an O(NlogN) spatial sort & O(logN)? spatial search, but no spatial index is required. Here's some more: http://www.mcnett.org/ Cheers! Bryan ```
 Re: [Algorithms] O(NlogN) spatial sort, O(logN)? spatial search, no spatial index From: Jason Hughes - 2007-04-30 08:27:14 ```bryan mcnett wrote: > The algorithm is an O(NlogN) spatial sort & O(logN)? spatial search, > but no spatial index is required. > > Here's some more: http://www.mcnett.org/ > The 'article' is not informative, and neither is your description. A BSP tree is roughly logN for search with single planar rejection, isn't it? Start by describing how your algorithm differs from that. What do you mean by spatial index--do you mean explicit pointers to child nodes? That's probably a significant win only at the topmost several layers of a structure, and deeper nodes probably benefit more from a small MRU cache of recently visited nodes. Most sorts are NlogN, and with spatial sorts they can be much, much better due to spatial hashing. You should provide some more details if you want intelligent responses. Thanks, JH ```