An algorithm for segment-dragging and its implementation |
| |
Authors: | Bernard Chazelle |
| |
Affiliation: | (1) Department of Computer Science, Princeton University, 08544 Princeton, NJ, USA |
| |
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 ofsegment-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 requiresO(n) storage andO(n logn) preprocessing time, and each query can be answered inO(logn) time, wheren 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.This work was started while the author was a visiting professor at Ecole Normale Supérieure, Paris, France. |
| |
Keywords: | Multidimensional searching Functional data structures Computer graphics Motionplanning |
本文献已被 SpringerLink 等数据库收录! |
|