Implicitly representing arrangements of lines or segments

ABSTRACT

An arrangement of n lines (or line segments) in the plane is the partition of the plane defined by these objects. Such an arrangement consists of &Ogr;(n2) regions, called faces. In this paper we study the problem of calculating and storing arrangements implicitly, using subquadratic space and preprocessing, so that, given any query point p, we can calculate efficiently the face containing p. First, we consider the case of lines and show that with &Lgr;(n) space1 and &Lgr;(n3/2) preprocessing time, we can answer face queries in &Lgr;(√n) + &Ogr;(K) time, where K is the output size. (The query time is achieved with high probability.) In the process, we solve three interesting subproblems: 1) given a set of n points, find a straight-edge spanning tree of these points such that any line intersects only a few edges of the tree, 2) given a simple polygonal path &Ggr;, form a data structure from which we can find the convex hull of any subpath of &Ggr; quickly, and 3) given a set of points, organize them so that the convex hull of their subset lying above a query line can be found quickly. Second, using random sampling, we give a trade-off between increasing space and decreasing query time. Third, we extend our structure to report faces in an arrangement of line segments in &Lgr;(n1/3) time, given &Lgr;(n4/3) space and &Lgr;(n5/3) preprocessing time. Lastly, we note that our techniques allow us to compute m faces in an arrangement of n lines in time &Lgr;(m2/3n2/3 + n), which is nearly optimal.

REFERENCES

• AS87: Boris Aronov and Micha Sharir. Triangles in space, or building and analyzing castles in the air. 1987. Manuscript.
• BO79: Jon L. Bentley and Thomas A. Ottman. Algorithms for reporting and counting geometric intersections. IEEE Transactions on Computers, C-28(9):643-647, 1979.
• Bro80: Kevin Quentin Brown, Geometric transforms for fast geometric algorithms, 1979
• CE87: Bernard Chazelle and Herbert Edelsbrunner. A fast algorithm for line segment intersection and its extensions. Manuscript, 1987.
• CEG*88: Ken Clarkson, Herbert Edelsbrunner, Leo Guibas, Micha Sharir, and Emo Welzl. 1988. In preparation.
• CG85: Bernard Chazelle , Leonidas J. Guibas, Visibility and intersectin problems in plane geometry, Proceedings of the first annual symposium on Computational geometry, p.135-146, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323252]
• CG86: B. Chazelle and L. J. Guibas. Fractional cascading: II. applications. Algorithmica, 1:163-191, 1986.
• CGL85: Bernard Chazelle , Leo J. Guibas , D. T. Lee, The power of geometric duality, BIT, v.25 n.1, p.76-90, 1985 [doi>10.1007/BF01934990]
• Cla87: K. L. Clarkson , P. W. Shor, Applications of random sampling in computational geometry, II, Discrete & Computational Geometry, v.4 n.5, p.387-421, 1989 [doi>10.1007/BF02187740]
• Ede87: Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
• EGP*87: Herbert Edelsbrunner, Leonidas Guibas, Janos Pach, Richard Pollack, Raimund Seidel, and Micha Sharir. Arrangements of curves in the plane: topology, combinatorics~ and algorithms. 1987. Manuscript.
• EGS86: Herbert Edelsbrunner , Lionidas J Guibas , Jorge Stolfi, Optimal point location in a monotone subdivision, SIAM Journal on Computing, v.15 n.2, p.317-340, May 1986 [doi>10.1137/0215023]
• EGS87: Herbert Edelsbrunner, Leonidas J. Guibas, and Micha Sharir. The complexity of many faces in arrangements of lines and of segments. 1987. Manuscript.
• EOS86: H Edelsbrunner , J O'Rouke , R Seiel, Constructing arrangements of lines and hyperplanes with applications, SIAM Journal on Computing, v.15 n.2, p.341-363, May 1986 [doi>10.1137/0215024]
• EW86: H Edelsbrunner , E Welzl, Halfplanar range search in linear space and O(n0.695) query time, Information Processing Letters, v.23 n.6, p.289-293, Dec. 3, 1986
• GH87: L. J. Guibas , J. Hershberger, Optimal shortest path queries in a simple polygon, Proceedings of the third annual symposium on Computational geometry, p.50-63, June 08-10, 1987, Waterloo, Ontario, Canada [doi>10.1145/41958.41964]
• GHS88: Leo Guibas, John Hershberger, and Jack Snoeyink. Bridge trees: a data structure for convex hulls. 1988. In preparation.
• GOS87: Leonidas Guibas, Mark Overmars, and Micha Sharir. Intersections, connectivity, and related problems for arrangements of line segments. 1987. Manuscript.
• HW87: David Haussler and Emo Welzl. Epsilon-nets and simplex range queries. Discrete and Computational Geometry, 2:127-151, 1987.
• Kir83: David Kirkpatrick. Optimal search in planar subdivisions. SIAM Journal on Computing, 12:28-35, 1983.
• KLPS86: Klara Kedem , Ron Livne , János Pach , Micha Sharir, On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles, Discrete & Computational Geometry, v.1 n.1, p.59-71, 1986 [doi>10.1007/BF02187683]
• Knu73: Donald E. Knuth. Sorting and Searching. Volume 3 of The Art of Computer Programming, Addison-Wesley, 1973.
• OvL81: M. Overmars and H. van Leeuwen. Maintenance of configurations in the plane. Journal of Computer and System Sciences, 23:166-204, 1981.
• PS85: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• SH76: M.I. Shaznos and D. Hoey. Geometric intersection problems. In Proceedings of the 17th IEEE Symposium on Foundations of Computer Science, pages 208-215, IEEE, 1976.
• ST86: Neil Sarnak , Robert E. Tarjan, Planar point location using persistent search trees, Communications of the ACM, v.29 n.7, p.669-679, July 1986 [doi>10.1145/6138.6151]
• Wel88: E. Welzl, Partition trees for triangle counting and other range searching problems, Proceedings of the fourth annual symposium on Computational geometry, p.23-33, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73397]
• Wil82: D.E. Willard. Polygon retrieval. SIAM J. Comput., 11:149-165, 1982.

INDEX TERMS

Primary 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

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.8 Metrics
          Subjects: Complexity measures
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Preprocessors

  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems; Trees
  G.3 PROBABILITY AND STATISTICS
      Subjects: Statistical computing; Probabilistic algorithms (including Monte Carlo)

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.10 Vision and Scene Understanding
            Subjects: Representations, data structures, and transforms
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations; Hierarchy and geometric transformations
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Visible line/surface algorithms
  I.5 PATTERN RECOGNITION
      I.5.4 Applications
          Subjects: Computer vision

General Terms:
Algorithms, Performance, Theory