## 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 1 1988 |

## All Science Journal Classification (ASJC) codes

- Computer Science(all)
- Computer Science Applications
- Applied Mathematics

## Keywords

- Computer graphics
- Functional data structures
- Motionplanning
- Multidimensional searching