Lines in space-combinators, algorithms and applications

ABSTRACT

We study combinatorial and algorithmic problems involving arrangements of n lines in 3-dimensional space, and then present applications of our results to a variety of problems on polyhedral terrains. Our main results include: A tight &THgr;(n2) bound on the complexity of the space of all lines passing above all the n given lines (their “upper envelope”) and satisfying a certain orientation consistency constraint. A preprocessing procedure using near-quadratic time and storage that builds a structure supporting &Ogr;(log n) time queries for testing if a line lies above all the given lines. An &Ogr;(n4/3+&egr;) randomized expected time algorithm, for any fixed &egr; > 0, that tests the “towering property”: do n given red lines lie all above n given blue lines? A preprocessing procedure for a polyhedral terrain &Sgr; with n edges, that uses near-quadratic time and storage and builds a structure supporting &Ogr;(log2 n) time rayshooting queries for computing the first intersection of an arbitrary query ray with &Sgr;. Finding the smallest vertical distance between two disjoint polyhedral terrains with a total of n edges, in time &Ogr;(n4/3+&egr;), for any &egr; > 0. Computing the upper envelope (pointwise maximum) of two polyhedral terrains with a total of n edges, in time &Ogr;(n1.5+&egr; + klog2 n), for any &egr; > 0, where &kgr; is the size of the output envelope. The tools used to obtain these results include Plücker coordinates for lines in space, random sampling in geometric problems, and a new variant of segment trees.

REFERENCES

• Ag: P. K. Agarwal, A deterministic algorithm for partitioning arrangements of lines and its application, Proceedings of the fifth annual symposium on Computational geometry, p.11-22, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73835]
• Be: Jon Louis Bentley, Multidimensional divide-and-conquer, Communications of the ACM, v.23 n.4, p.214-229, April 1980 [doi>10.1145/358841.358850]
• CEGSS: B. Chazelle, H. Edelsbrunner, L. Guibas, M. Sharir, and J. Stolfi, Lines in space - combinatorics, algorithms and applications, in preparation.
• CEGS: B. Chazelle, H. Edelsbrunner, L. Guibas and M. Sharir, Algorithms for bichromatic line segment problems and polyhedrM terrains, in preparation.
• CF: B. Chazelle and J. Friedman, A deterministic view of random sampling and its use in geometry, Proe. 29th IEEE Syrup. on Foundations of Computer Science, 1988, pp. 539-549.
• CG: B. Chazelle and L. Guibas, Fractional cascading: I. A data structuring technique, Algorithmica 1 (1986) pp. 133-162.
• ChS: B. Chazelle , M. Sharir, An algorithm for generalized point location and its applications, Journal of Symbolic Computation, v.10 n.3-4, p.281-309, Sept./Oct. 1990 [doi>10.1016/S0747-7171(08)80065-X]
• Cl: 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]
• Cl2: K Clarkson, A probabilistic algorithm for the post office problem, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.175-184, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22165]
• CS: Richard Cole , Micha Sharir, Visibility problems for polyhedral terrains, Journal of Symbolic Computation, v.7 n.1, p.11-30, Jan. 1989 [doi>10.1016/S0747-7171(89)80003-3]
• Ed: Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
• EGS: H. Edelsbrunner , L. J. Guibas , M. Sharir, The complexity of many faces in arrangements of lines of segments, Proceedings of the fourth annual symposium on Computational geometry, p.44-55, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73399]
• EGSt: 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]
• GCS: Ziv Gigus , John F. Canny , Raimund Seidel, Efficiently Computing and Representing Aspect Graphs of Polyhedral, University of California at Berkeley, Berkeley, CA, 1988
• HW: D. Haussler and E. Welzl, Epsilon nets and simplex range searching, :Discrete Cornp. Geom. 2 (1987) pp. 127- 151.
• MS: H. Mairson and J. Stolfi, Reporting and counting intersections between two sets of line segments, irt Theoretical Foundations of Computer Graphics and CAD, (R.A. Earnshaw, ed.), NATO ASI Series, Vol. F-40, Springer Verlag, Berlin 1988, pp. 307-325.
• Ma: J. Matou~ek, Construction of e-nets, Proc. 5nd A CM Syrup. on Computational Geometry, 1989, to appear.
• Mc: M. McKenna, Arrangements of lines in 3-space: A data structure with ~pplications, Ph.D. Dissertation, Johns Hopkins University, 1989.
• MO: M. McKenna , J. O'Rourke, Arrangements of lines in 3-space: a data structure with applications, Proceedings of the fourth annual symposium on Computational geometry, p.371-380, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73431]
• MeS: Kurt Mehlhorn , Klaus Simon, Intersecting two polyhedra one of which is convex, Fundamentals of Computation Theory, p.534-542, September 09-13, 1985
• Mi: J. Milnor, On the Betti numbers of real varieties, Proc. Arner. Math. Soc. 15 (1964), pp. 275-280.
• PD: W.H. Planting~ and C.R. Dyer, An algorithm for constructing the aspect graph, Proc. ~Tth IEEE Syrup. on Foundations of Computer Science, 1986, pp. 123-131.
• PS: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• SML: A. Schmitt, H. Muller and W. Leister, Ray tracing algorithms- theory and practice, In Theoretical Foundations of Computer Graphics and CAD (R.A. Earnshaw, Ed.), NATO ASI Series, Vol. 1'40, Springer Verlag, Berlin, 1988, 997-1030.
• Se: R Seidel, Constructing higher-dimensional convex hulls at logarithmic cost per face, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.404-413, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12172]
• Sh: Micha Sharir, The shortest watchtower and related problems for polyhedral terrains, Information Processing Letters, v.29 n.5, p.265-270, November 24, 1988 [doi>10.1016/0020-0190(88)90120-2]
• St: Jorge Stolfi, Primitives for computational geometry, 1988
• YY: A C Yao , F F Yao, A general approach to d-dimensional geometric queries, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.163-168, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22163]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

General Terms:
Algorithms, Theory