Re:The Genius of Binary Space Partitioning in Doom
by kqr on Tuesday November 22, 2022 @01:09AM
(#33702608)
Yes, it would average nlogn and worst case would be n², unless I'm thinking about it incorrectly.
But this is one of those cases where asymptotic complexity seems a bit too reductive. One of the "n" in the complexity is really a fraction of the n.
That said, if I understand your use case correctly, you might not benefit much from having a binary subdivision of space for this. It sounds like what you need is more of a plain ordered list. One of the ways to implement that is as a binary tree, but an array that is kept ordered may be fast enough due to locality etc.
But this is one of those cases where asymptotic complexity seems a bit too reductive. One of the "n" in the complexity is really a fraction of the n.
That said, if I understand your use case correctly, you might not benefit much from having a binary subdivision of space for this. It sounds like what you need is more of a plain ordered list. One of the ways to implement that is as a binary tree, but an array that is kept ordered may be fast enough due to locality etc.