Published on *Computer Science Department at Princeton University* (http://www.cs.princeton.edu)

Given a collection of points in the plane, pick an arbitrary horizontal segment and move it vertically until it hits one of the points (if at all). This form of segment-dragging is a common operation in computer graphics and motion-planning. It can also serve as a building block for multidimensional data

structures. This note describes a new approach to segment-dragging which yields a simple and efficient solution. The data structure requires O(n) storage and O(n log n) preprocessing time, and each query can be answered in O(log n) time, where n is the number of points in the collection. The method is best understood as the end result of a sequence of transformations applied to a simple but inefficient starting solution.

**Links**

[1] http://www.cs.princeton.edu/research/techreps/author/283

[2] ftp://ftp.cs.princeton.edu/techreports/1987/077.pdf