Adding to my list of oddities in computer science.

CS folks are enamored of dividing 2D space in 2D space chunks? It makes all of the math needlessly harder, even if it makes the math-sense and understandability easier. You divide 2D space into two instances of 1D space. The algorithms don't require trees, you can still easily access the needed data in log(n) time, update them as easy as a sorted list can be updated, and with a bit of style you can easily prove points don't need to be checked. It's weird because no algorithms do this, but you can do an amazing amount of very simple math to solve all the traditional problems in computational geometry with simpler algorithms.

• You can build the space in d*n*log(n) time (sorting lists).
• With sorted lists of points you can insert in as easy as inserting into a list.
• You can remove as easily as removing from a list.
• You can find the nearest neighbor to a point in a short algorithm in log(n) time.
• You can find k nearest neighbors to a point in a similar short algorithm in ~k*log(k)*log(n) time.
• You can do basically all the AABB math quite easily too. You can easily find in n time the bounding boxes relevant to a point. And update that point very easily.
• You can find if a point is inside a polygon.
• You can find all points within an axis aligned rectangle in trivial time.

But the really really pressing bits of this is that categorically these algorithms are tiny. Like they don't take much work at all. They are exceptionally short. And the datastructure is what modern memory systems are optimized for so you won't be cache missing all the time. And it's so common it's implemented in like four lines of code. So why the hell are all games doing collision detection of divided up 2D space in 2D chunks or 3D chunks in 3D space? Also, these algorithms obviously scale really easily with the degree of dimensionality. They don't violate theoretical points though. If you do a Nearest Neighbor Search in 3D it's basically identical code with the steps as the 2D code but since we're dealing with 3D, it can easily end up checking most all the points anyway simply because you can't rule out the remaining checks as quickly.

I needed a nearest neighbor search for my android app to find the nearest point to a point and do this many many times in real time. But, when a point is moved it required a lot to fix the pre-processed datastructure since they were organized into trees so the nodes needed to be fiddled with etc. This allowed for nodes to be updated en masse, and the lists to simply be very quickly resorted in a trivial amount of time and perfectly ready for the next tick.

I hit upon this algorithm largely because I had also done considerable work with filling monotone polygons using a scanline, and used a sort of step-raytrace with line segments which is another brilliant algorithm (it's very similar to the good solution to the skyline problem), it's largely just a single list of all the points sorted along one axis. Then you scan through the list, keeping a working list of active line segments. This solves the perpendicular rays and finds all intersections of that perpendicular ray (it's literally the intersections of the active list of line segments) in fast enough time that a little android phone can do the ray traced lines in real time.

To speed up my attract tool (requires many nearest neighbor searches), I previously made an interesting nearest neighbor search with a point quadtree which equally used the same general idea that you could prove the invalidity of other parts of the tree by showing that the distance in just 1 dimension is greater than the shortest distance already found. I thought this was awesome as nobody seemed to have any nearest neighbor algorithms based on that rather rare datastructure.

But, if you could do this with a tree it would be much easier to do this with 2 different 1D sorted lists. Just binary search into the list, and go to each point in the +X, +Y, -X, -Y directions until the distance in just dX is greater than your best candidate so far.  You can also conclude things like if +X and -X are exhausted then there can be no closer point, as you proved all points exhausted (the points found in the other dimensions are going to be duplicates of the ones you ruled out). But, the point is implementing all of that is trivial compared to the other ways. And all the tricks in computational geometry are simply proving you don't have to check those other points, which is can be done with the same trick over and over, can this point further along this axis possibly be closer or included? For the K-nearest neighbor algorithm, you store the candidates in a heap sorted by distance and only compare the worst of them to the new potential candidates until just that one direction along is enough to be worse in which case no more points along that axis can possibly be better.

For Axis Aligned Bounding Boxes (AABB) you can rather simply add the start points and end points of the shapes. Then when you cross a threshold by traveling along the axis (only going to the next relevant point always as that's how the traversal works), you can trivially check if the relevant point is within that bounding box. So you can rather easily linearly iterate into the list and you'll know exactly which bounding boxes that point is within tracking them basically exactly as one would the skyline problem. Then moving that point within the space equally quite quick and just means updating any active elements as you cross thresholds (and if you don't cross any relevant boundaries, changing nothing at all). Equally it solves a number of common problems in collision detections like not updating something that moved in time to see that it struck something. As the object moves it needs to find it's place in the lists, which means you must process each element in order, which means you know if you hit anything, regardless whether you would now be completely on the other side of that object now.

I totally understand that it's easier to think in 3d space in 3d and 2d space in 2d so when you're partitioning space you are wildly more likely to divide the space in ways that does not screw up the dimensionality. It's easy to think of dividing a square into two half-squares but it's a bit weird to divide it into two equally lengthed lines. But the math is easier if you divide it into two lines for obvious reasons, even if it's harder to conceptualize.

On Intelligence being evolution.

Wrote this elsewhere as personal correspondence, but it makes some points I'd rather not forget for future reference. I'm a computer scientist and one of my notable skills is understanding algorithms that underlie things. In 2007, I watched a pretty great TED talk by Jeff Hawkins ( Jeff Hawkins on how brain science will change computing. ) which had some really critical ideas about understanding intelligence and it made me realize that if brains predict the future, and that seems right, then the algorithm for intelligence is necessarily: evolution. Now, I don't mean this to say intelligence evolved, I mean this to say that a child from infancy to adulthood how they work in the brain is fundamentally an implementation of evolution. And I don't mean that lightly. There's a few people who note that artificial neural nets have a somewhat evolutionary strengthening, or folks who argue that brains work kind of like the adaptive immune system. I mean this strongly like algorithmically evolution and intelligence are identical. It seems a bit weird at first, but the more you let it infect your mind the more you realize it explains things. Creationists always look at trees and insist they were intelligently designed. Because they look at trees and the products of intelligence and say; the causes of these things are the same. We turn around and say we know the tree formed through evolution and therefore that statement is not true; but I think this is wrong. I think this rather shockingly strong *illusion* of intelligence is no fiction at all. Sometimes the opposite of a profound truth is another profound truth. The error we make is in assuming we know what the fuck intelligence is and are therefore correct in dismissing Darwinian evolution as a form of it; I think it is a form of it because at the core the two are the same thing. The argument from design says that the two things are the same. We say that argument is wrong because the tree is the result of evolution by natural selection. But, there's a missing premise there required to deny the argument: intelligence is not evolution. And I think that premise is false; It is evolution. This also gives us a few interesting requirements about what is required between senses and minds; namely there's no requirement for a connection at all. It isn't as if the environment programs DNA of various species. There's no direct connection there at all. Rather the things that work effectively are strengthened and those that don't do not. Likewise if brains are making predictions of things fairly randomly and are only being confirmed by your senses, then we necessarily do not need our senses to direct our actions at all. Without senses we'd start hallucinating wildly, with them we hallucinate coherently. Our senses only need to confirm things after the fact. So some weird items like how we can swing a bat in less time than we could have decided to, just sort of evaporate. And seemingly profound thought experiments like Searle's Chinese Box become rather trite. Undoubtedly you can think of dozens more examples that quickly get explained away. So the posted article contains things like "Your mind filters, sorts, selects, contains, and bestows meaning to an element in the endless stream of external data flooding your senses." -- This is completely pointless and wrong. Your mind doesn't need to do any of that because our senses don't do any of that. We invent a world inside our own heads with various theories and ideas and understandings, and then our senses tell us whether that stuff is right or not and we react accordingly. This is also largely why in sensory deprivation chambers or our sleep we kind of go a little crazy, because nothing ends up registering as being more true than anything else so we start hallucinating. We also get basically every form of hallucination for free, from excess details that we can't really see to the blind spot in our eyes, and why we make up intermediate steps between events even if they didn't exist. Under my theory, we not only get these for free; they are required to be true. It also broadly explains why "there is a difference between what you experience, and what exists out there: The virtual can never be real. The essence of your understanding is, in effect, rooted in this difference. Where does difference arise?" -- The difference arises because the stuff we perceive is completely made up. Everything about our understanding of the world what we think the world actually is, is a confabulation that was made up inside our head, and whittled down by our senses. Just as every nucleotide in our very amazing DNA was a random mutation. It sounds like this should completely unmoor our understanding of reality from reality itself and it does, but our senses narrow that range of possibilities and those elements, just as the process of selection culls random mutations into "endless forms most beautiful". If you take this idea seriously, you will quickly realize that it starts knocking down barriers by its mere existence in your head. It not only explains the veil but why it must exist. Our very nature as intelligent beings requires that this is how we work. Most of the objections to George Berkeley's sort of idealism ((1) We perceive ordinary objects (houses, mountains, etc.). (2) We perceive only ideas. Therefore, (3) Ordinary objects are ideas.) are generally that reality is real and it is, but if you understand what intelligence is you can thread the needle aptly enough to take the correct points from idealism and from materialism. It's entirely true that reality comes only from us internally and that reality is not somehow the result of our senses grabbing reality and pulling it into our head. Rather the reality in our head is influenced by our senses and our ability to predict what we well sense next requires us to come up with an internal view of reality that need not be anything like actual reality (in fact we know a lot of aspects like color are just ad hoc inventions and do not exist outside our heads) it's filled in with a bunch of hallucinations and randomness because the internal view of reality need not have anything to do with actual reality, except that we have consistent ideas about reality that have evolved and they are remarkably resilient. Just as evolved forms need not be efficient hunters or energy gatherers but because of the nature of evolution that's how they end up. We need not have a good grasp of reality and make correct predictions and correct understandings, but because of the nature of what evolution does, the more efficient forms are preferred. In other words, under this understanding intelligence will end up being as robust as the web of life itself. Update, based on a reply discussing evolutionary epistemology: No. I am not at all saying evolutionary epistemology. Fucking obviously evolution formed our senses, but that's not even remotely the point. I'm thinking I missed the point if you couldn't get your head around it enough to stop you from jumpping down one of the many different lines of similar but all equally inexact thoughts. I mean what I say more profoundly than that, like expelling the hobgoblins there and replacing the whole shebang. I wrote it well and tried to stress the points to help get your head around it, but apparently it still missed the mark. Imagine if you would that there is no such thing as intelligence. That that which we call intelligence is entirely just evolution taking place in neurons. Not that senses are evolved or brains are evolved or that brains use vaguely reinforcing neurons that are akin to evolutionary processes; no. Everything about intelligence is just evolution taking place in the medium of brains. That the mind is running an evolutionary algorithm. That's how it entirely works.