An algorithm for segment-dragging and its implementation

Research output: Contribution to journalArticlepeer-review

29 Scopus citations

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 languageEnglish (US)
Pages (from-to)205-221
Number of pages17
JournalAlgorithmica
Volume3
Issue number1-4
DOIs
StatePublished - Nov 1988
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • Computer Science Applications
  • Applied Mathematics

Keywords

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

Fingerprint

Dive into the research topics of 'An algorithm for segment-dragging and its implementation'. Together they form a unique fingerprint.

Cite this