Windowing Systems and User Interface Programming
The rectangular geometry of most windowing user interfaces lends itself
naturally to the orthogonal range searching techniques studied in
computational geometry. A typical problem arising in this context might
be to find a data structure for quickly determining which window or
window system object is topmost at a given screen pixel (for instance
this information is needed to process mouse clicks and to set the
mouse's appearance). Range searching techniques can be useful even
within a single window, to speed up scrolling and redisplay by
determining which objects are visible in a region. In my own
programming experience, I have used (a simplified implementation of)
interval trees to greatly speed up scrolling in code for displaying
large family trees.
Patent 5459831 covers the use of quadtrees to perform the range
queries needed for object selection in graphical user interfaces.
Patent 5461712 uses quadtrees to allocate memory to different
objects in a windowing system.
Patent 5564004 uses Voronoi diagrams as part of a user interface
that highlights the icon nearest the cursor in a windowing system.
Geometry in Action,
a collection of applications of computational geometry.
from a common source file.