Range searching in a set of line segments

ABSTRACT

The range searching (or windowing) problem asks for an accommodation of a set of objects such that those objects that lie (partially) in a given axis-parallel rectangle can be reported efficiently. We solve the range searching problem for a set of n non-intersecting, but possibly touching, line segments in the plane and give a data structure that allows for range queries in &Ogr;(k+ log2 n) time, where k is the number of reported answers. The structure is dynamic and allows for insertions and deletions of line segments in &Ogr;(log2 n) time. The structure uses &Ogr;(n log n) storage. The related problem of moving the window (range) parallel to one of the coordinate-axes, determining the first line segment that will become visible or stops being visible, is treated as well and similar bounds are obtained.

REFERENCES

• 1: [1] Edelsbrunner, H., A note on dynamic range searching, Bull. of the EATCS 15 (1981), 34-40.
• 2: [2] Edelsbrunner, H. and H. A. Maurer, On the intersection of orthogonal objects, Inform. Proc. Lett. 13 (1981) 177-181.
• 3: [3] Edelsbrunner, H., and H. A. Maurer, A space-optimal solution of general region location, Theor. Comp. Sci. 16 (1981) 329-336.
• 4: [4] Edelsbrunner, H., M. H. Overmars and R. Seidel, Some methods of computational geometry applied to computer graphics, Computer Vision, Graphics, and Image Processing 28 (1984) 92-108.
• 5: [5] Kirkpatrick, D. G., Optimal search in planar subdivisions, SIAM J. Computing 12 (1983) 28-35.
• 6: [6] Lueker, G. S., A transformation for adding range restriction capability to dynamic data structures for decomposable searching problems, Techn. Rep. 129, Dept. of Computer Science, University of California, 1979.
• 7: [7] McCreight, E. H., Priority search trees, Techn. Rep. CSL-81-5. XEROX Palo Alto research centre, 1981.
• 8: Mark H. Overmars, Design of Dynamic Data Structures, Springer-Verlag New York, Inc., Secaucus, NJ, 1987
• 9: [9] Overmars, M. H. and J. van Leeuwen, Worst-case optimal insertion and deletion methods for decomposable searching problems, Inform. Proc. Lett. 12 (1981), 168-173.
• 10: [10] van Leeuwen, J., Graphics and computational geometry, Les Mathematiques de l'Informatique, Colloq. AFCET, 1982, 159-165.
• 11: [11] Willard, D. E., The super-B-tree algorithm, Techn. Rep. TR-03-79, Aiken Computer Lab., Harvard University, 1979.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.8 Scene Analysis
          Subjects: Range data

General Terms:
Design, Performance, Theory

Keywords:
line segments, moving, planar point location, range searching, segment tree, windowing