Abstract
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.
Original language | English (US) |
---|---|
Pages (from-to) | 205-221 |
Number of pages | 17 |
Journal | Algorithmica |
Volume | 3 |
Issue number | 1-4 |
DOIs | |
State | Published - Nov 1988 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- General Computer Science
- Computer Science Applications
- Applied Mathematics
Keywords
- Computer graphics
- Functional data structures
- Motionplanning
- Multidimensional searching