Computing envelopes in four dimensions with applications

ABSTRACT

Let F be a collection of n d-variate, possibly partially defined, functions, all algebraic of some constant maximum degree. We present a randomized algorithm that computes the vertices, edges, and 2-faces of the lower envelope (i.e., pointwise minimum) of F in expected time O(nd+&egr;), for any &egr;>0. For d=3, by combining this algorithm with the point location technique of Preparata and Tamassia, we can compute, in randomized expected time O(n3+&egr;) for any &egr;>0, a data structure of size O(n3+&egr;) that, given any query point q, can determine in O(log2n) time whether q lies above, below or on the envelope. As a consequence, we obtain improved algorithmic solutions to many problems in computational geometry, including (a) computing the width of a point set in 3-space, (b) computing the biggest stick in a simple polygon in the plane, and (c) computing the smallest-width annulus covering a planar point set. The solutions to these problems run in time O(n17/11+&egr;), for any &egr;>0 improving previous solutions that run in time O(n8/5+&egr;). We also present data structures for (i) performing nearest-neighbor and related queries for fairly general collections of objects in 3-space and for collections of moving objects in the plane, and (ii) performing ray-shooting and related queries among n spheres or more general objects in 3-space. Both of these data structures require O(n3+&egr;) storage and preprocessing time, for any &egr;>0, and support polylogarithmic-time queries. These structures improve previous solutions to these problems.

REFERENCES

• 1: Pankaj K. Agarwal , Jiří Matoušek, Ray shooting and parametric search, SIAM Journal on Computing, v.22 n.4, p.794-806, Aug. 1993 [doi>10.1137/0222051]
• 2: Pankaj K. Agarwal , Jirí Matousek, On Range Searching with Semialgebraic Sets, Proceedings of the 17th International Symposium on Mathematical Foundations of Computer Science, p.1-13, August 24-28, 1992
• 3: P. Agarwal, O. Schwarzkopf and M. Sharir, The overlay of lower envelopes and its applications, manuscript, 1993.
• 4: Pankaj K. Agarwal , Micha Sharir , Sivan Toledo, Applications of parametric searching in geometric optimization, Journal of Algorithms, v.17 n.3, p.292-318, Nov. 1994
• 5: P. Agarwal, L. Guibas, M. Pellegrini, and M. Sharir, Ray shooting among spheres, manuscript, 1992.
• 6: P. Agarwal and M. Shark, On the number of views of polyhedral terrains, Proc. 5th Canadian Conf. Computational Geometry, 1993, 55-61.
• 7: B. Aronov and M. Sharir, Triangles ill space, or: Building (and analyzing) castles in the air, Combinatorica 10 (1990), 137-173.
• 8: Jean-Daniel Boissonnat , Olivier Devillers , René Schott , Monique Teillaud , Mariette Yvinec, Applications of random sampling to on-line algorithms in computational geometry, Discrete & Computational Geometry, v.8 n.1, p.51-71, 1992 [doi>10.1007/BF02293035]
• 9: J.D. Boissonnat and K. Dobrindt, On-line randomized construction of the upper envelope of triangles and surface patches in R3, manuscript, 1993.
• 10: B. Chazelle, H. Edelsbrunner, L. Guibas and M. Sharir, Algorithms for bichromatic line segment problems and polyhedral terrains, Algorithmica 11 (1994), 116-132.
• 11: B. Chazelle, H. Edelsbrunner, L. Guibas and M. Sharir, Diameter, width, closest line pair, and parametric searching, Discrete Comput. Geom. 10 (1993), 183-196.
• 12: Bernard Chazelle , Herbert Edelsbrunner , Leonidas Guibas , Micha Sharir , Jack Snoeyink, Computing a face in an arrangement of line segments and related problems, SIAM Journal on Computing, v.22 n.6, p.1286-1302, Dec. 1993 [doi>10.1137/0222077]
• 13: 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]
• 14: L.P. Chew, K. Kedem, M. Sharir and E. Welzl, Voronoi diagrams of lines in 3-space under a polyhedral convex distance function, in preparation.
• 15: 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]
• 16: Mark de Berg , Katrin Dobrindt , Otfried Schwarzkopf, On lazy randomized incremental construction, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.105-114, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195113]
• 17: H. Ebara, N. Fukuyama, H. Nakano and Y. Nakanishi, Roundness algorithms using the Voronoi diagrams, First Canadian Conf. Computational Geometry, 1989.
• 18: Herbert Edelsbrunner , Raimund Seidel, Voronoi diagrams and arrangements, Discrete & Computational Geometry, v.1 n.1, p.25-44, 1986 [doi>10.1007/BF02187681]
• 19: Dan Halperin , Micha Sharir, New bounds for lower envelopes in three dimensions, with applications to visibility in terrains, Proceedings of the ninth annual symposium on Computational geometry, p.11-18, May 18-21, 1993, San Diego, California, United States [doi>10.1145/160985.160989]
• 20: D. Hau881er and E. Welzl, e-nets and simplex range queries, Discrete Comput. Geom. 2 (1987), 127-151.
• 21: Michael E. Houle , Godfried T. Toussaint, Computating the width of a set, Proceedings of the first annual symposium on Computational geometry, p.1-7, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323234]
• 22: Nimrod Megiddo, Applying Parallel Computation Algorithms in the Design of Serial Algorithms, Journal of the ACM (JACM), v.30 n.4, p.852-865, Oct. 1983 [doi>10.1145/2157.322410]
• 23: S. Mohaban and M. Sharir, Ray shooting amidst spheres in three dimensions, manuscript, 1993.
• 24: K. Mulmuley, A fast planar partition algorithm, I, Journal of Symbolic Computation, v.10 n.3-4, p.253-280, Sept./Oct. 1990 [doi>10.1016/S0747-7171(08)80064-8]
• 25: Kentan Mulmuley, A fast planar partition algorithm, II, Journal of the ACM (JACM), v.38 n.1, p.74-103, Jan. 1991 [doi>10.1145/102782.102785]
• 26: Franco P. Preparata , Roberto Tamassia, Efficient point location in a convex spatial cell-complex, SIAM Journal on Computing, v.21 n.2, p.267-280, April 1992 [doi>10.1137/0221020]
• 27: J. Heintz, T. Recio and M.-F. Roy, Algorithms in real algebraic geometry and applications to computational geometry, in Discrete and Computational Geometry: Papers from the DIMAC$ Special Year (J.E. Goodman, R. Pollack and W. Steiger, Eds.), AMS Press, Providence, RI 1991, pp. 137-163.
• 28: M. Sharir, Almost tight upper bounds for lower envelopes in higher dimensions, Proc. 3Jth IEEE $ymp. on Foundations of Computer Science, 1993, 498-507. (Also to appear in Discrete Comput. Geom.)
• 29: Micha Sharir , Pankaj K. Agarwal, Davenport-Schinzel sequences and their geometric applications, Cambridge University Press, New York, NY, 1996

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:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION

General Terms:
Algorithms, Theory