Geometry in Action

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.

Part of Geometry in Action, a collection of applications of computational geometry.
David Eppstein, Theory Group, ICS, UC Irvine.

Semi-automatically filtered from a common source file.