Bin (computational geometry)  In computational geometry, the bin is a data structure that allows efficient region queries. Each time a data point falls into a bin, the frequency of that bin is increased by one. For example, if there are some axis-aligned rectangles on a 2D plane, the structure can answer the question, ""Given a query rectangle, what are the rectangles intersecting it?"" In the example in the top figure, "A, B, C, D, E" and "F" are existing rectangles, so the query with the rectangle "Q" should return "C, D, E" and "F", if we define all rectangles as closed intervals. The data structure partitions a region of the 2D plane into uniform-sized "bins". The bounding box of the bins encloses all "candidate" rectangles to be queried. All the bins are arranged in a 2D array. All the candidates are represented also as 2D arrays. The size of a candidate's array is the number of bins it intersects. For example, in the top figure, candidate "B" has 6 elements arranged in a 3 row by 2 column array because it intersects 6 bins in such an arrangement. Each bin contains the head of a singly linked list. If a candidate intersects a bin, it is chained to the bin's linked list. Each element in a candidate's array is a link node in the corresponding bin's linked list. From the query rectangle "Q", we can find out which bin its lower-left corner intersects efficiently by simply subtracting the bin's bounding box's lower-left corner from the lower-left corner of "Q" and dividing the result by the width and height of a bin respectively. We then can iterate the bins "Q" intersects and examine all the candidates in the linked-lists of these bins. For each candidate we will check if it does indeed intersect "Q". If so and if it was not previously reported, then we report it. We can use the convention that we only report a candidate the first time we find it. This can be done easily by clipping the candidate against the query rectangle and comparing its lower-left corner against the current location. If it is a match then we report, otherwise we skip. Insertion is linear to the number of bins a candidate intersects because inserting a candidate into 1 bin is constant time. Deletion is more expensive because we need to search the singly linked list of each bin the candidate intersects.