# Applications

## Maps, sets, and lists

set and map in C++ STL library java.util.TreeMap and java.util.TreeSet in Java

## Linux kernel

quote:

There are a number of red-black trees in use in the kernel. The anticipatory, deadline, and CFQ I/O schedulers all employ rbtrees to track requests; the packet CD/DVD driver does the same. The high-resolution timer code uses an rbtree to organize outstanding timer requests. The ext3 filesystem tracks directory entries in a red-black tree. Virtual memory areas (VMAs) are tracked with red-black trees, as are epoll file descriptors, cryptographic keys, and network packets in the “hierarchical token bucket” scheduler.

## Computational geometry

There are many applications of ordered dictionaries in computational geometry. In particular, the sweep line technique together with a balanced search tree can be used to efficiently solve problems such as

• Various intersection problems. For example:

• Given two simple polygons, do they intersect? Or more generally: given any set of lines, does any pair of lines intersect?
• Given a set of rectangles (with sides parallel to the $x$ and $y$ axes), does any pair of rectangles intersect? This problem has applications in VLSI design.
• Given a set of circles, does any pair of circles intersect?

Note that these problems can be trivially solved in $O(n^2)$ by checking each pair of lines/rectangles/circles. Using the sweep line technique, we can find the answer in $O(n\log n)$ time.

• Closest pair of points problem
• Voronoi diagrams (see the Fortune’s algorithm)

### References

• Shamos, M. I., & Hoey, D. (1976, October). Geometric intersection problems. In Foundations of Computer Science, 1976., 17th Annual Symposium on (pp. 208-215). IEEE. [pdf]
• Bentley, J. L., & Ottmann, T. A. (1979). Algorithms for reporting and counting geometric intersections. Computers, IEEE Transactions on, 100(9), 643-647. [pdf]
• Bentley, J. L., & Wood, D. (1980). An optimal worst case algorithm for reporting intersections of rectangles. Computers, IEEE Transactions on, 100(7), 571-577.

Point location

## References

• Sarnak, N., & Tarjan, R. E. (1986). Planar point location using persistent search trees. Communications of the ACM, 29(7), 669-679. [pdf]

::: :::