Efficiency and Tuning
The analysis is similar to a hash table. The worst-case scenario is that all candidates are concentrated in one bin. Then query is O(n), delete is O(n), and insert is O(1), where n is the number of candidates. If the candidates are evenly spaced so that each bin has a constant number of candidates, The query is O(k) where k is the number of bins the query rectangle intersects. Insert and delete are O(m) where m is the number of bins the inserting candidate intersects. In practice delete is much slower than insert.
Like a hash table, bin's efficiency depends a lot on the distribution of both location and size of candidates and queries. In general, the smaller the query rectangle, the more efficient the query. The bin's size should be such that it contains as few candidates as possible but large enough so that candidates do not span too many bins. If a candidate span many bins, a query has to skip this candidate over and over again after it is reported at the first bin of intersection. For example, in the figure, E is visited 4 times in the query of Q and so has to be skipped 3 times.
To further speed up the query, divisions can be replaced by right shifts. This requires the number of bins along an axis direction to be an exponent of 2.
Read more about this topic: Bin (computational Geometry)
Famous quotes containing the words efficiency and and/or efficiency:
“Nothing comes to pass in nature, which can be set down to a flaw therein; for nature is always the same and everywhere one and the same in her efficiency and power of action; that is, nature’s laws and ordinances whereby all things come to pass and change from one form to another, are everywhere and always; so that there should be one and the same method of understanding the nature of all things whatsoever, namely, through nature’s universal laws and rules.”
—Baruch (Benedict)
““Never hug and kiss your children! Mother love may make your children’s infancy unhappy and prevent them from pursuing a career or getting married!” That’s total hogwash, of course. But it shows on extreme example of what state-of-the-art “scientific” parenting was supposed to be in early twentieth-century America. After all, that was the heyday of efficiency experts, time-and-motion studies, and the like.”
—Lawrence Kutner (20th century)