Abstract
We consider the problem of bounding the combinatorial complexity of the lower envelope ofn surfaces or surface patches ind-space (d≥3), all algebraic of constant degree, and bounded by algebraic surfaces of constant degree. We show that the complexity of the lower envelope ofn such surface patches isO(n d−1+∈), for any ∈>0; the constant of proportionality depends on ∈, ond, ons, the maximum number of intersections among anyd-tuple of the given surfaces, and on the shape and degree of the surface patches and of their boundaries. This is the first nontrivial general upper bound for this problem, and it almost establishes a long-standing conjecture that the complexity of the envelope isO(n d-2λq(n)) for some constantq depending on the shape and degree of the surfaces (where λq(n) is the maximum length of (n, q) Davenport-Schinzel sequences). We also present a randomized algorithm for computing the envelope in three dimensions, with expected running timeO(n 2+∈), and give several applications of the new bounds.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
P. K. Agarwal, B. Aronov, and M. Sharir, Computing envelopes in four dimensions with applications,Proc. 10th ACM Symp. on Computational Geometry, 1994, pp. 348–358.
P. K. Agarwal, O. Schwarzkopf, and M. Sharir, The overlay of lower envelopes and its applications, Manuscript, 1993.
P. K. Agarwal and M. Sharir, On the number of views of polyhedral terrains,Proc. 5th Canadian Conference on Computational Geometry, 1993, pp. 55–61. (To appear inDiscrete Comput. Geom.)
P. K. Agarwal, M. Sharir, and P. Shor, Sharp upper and lower bounds for the length of general Davenport-Schinzel sequences.J. Combin. Theory. Ser. A,52 (1989), 228–274.
J. Bochnak, M. Coste, and M-F. Roy,Géométrie Algébrique Réelle, Springer-Verlag, Berlin, 1987.
J. D. Boissonnat and K. Dobrindt, On-line randomized construction of the upper envelope of triangles and surface patches inR 3, Manuscript, 1993.
B. Chazelle, H. Edelsbrunner, L. Guibas, and M. Sharir, A singly exponential stratification scheme for real semi-algebraic varieties and its applications,Proc. 16th Internat. Colloq. on Automata, Languages and Programming, 1989, pp. 179–193.
B. Chazelle, H. Edelsbrunner, L. Guibas, and M. Sharir, Diameter, width, closest line pair, and parametric searching,Discrete Comput. Geom. 10 (1993), 183–196.
B. Chazelle, H. Edelsbrunner, L. Guibas, M. Sharir, and J. Stolfi, Lines in space: combinatorics and algorithms,Algorithmica, to appear.
K. Clarkson, New Applications of random sampling in computational geometry,Discrete Comput. Geom. 2 (1987), 195–222.
K. Clarkson, H. Edelsbrunner, L. Guibas, M. Sharir, and E. Welzl, Combinatorial complexity bounds for arrangements of curves and spheres,Discrete Comput. Geom. 5 (1990), 99–160.
K. Clarkson and P. Shor, Applications of random sampling in computational geometry, II,Discrete Comput. Geom. 4 (1989), 387–421.
G. E. Collins, Quantifier elimination for real closed fields by cylindric algebraic decomposition,Proc. 2nd GI Conf. on Automata Theory and Formal Languages, Springer-Verlag, Berlin, 1975, pp. 134–183.
M. de Berg, K. Dobrindt, and O. Schwarzkopf, On lazy randomized incremental construction,Proc. 26th ACM Symp. on Theory of Computing, 1994, pp. 105–114.
H. Edelsbrunner and R. Seidel, Voronoi diagrams and arrangements,Discrete Comput. Geom. 1 (1986), 25–44.
J.-J. Fu and R.C.T. Lee, Voronoi diagrams of moving points in the plane,Internat. J. Comput. Geom. Appl. 1 (1991), 23–32.
L. Guibas, J. Mitchell, and T. Roos, Voronoi diagrams of moving points in the planeProc. 17th Internat. Workshop on Graph-Theoret. Concepts in Computer Science, Lecture Notes in Computer Science, Vol. 570, Springer-Verlag, Berlin, 1991, pp. 113–125.
D. Halperin and M. Sharir, New bounds for lower envelopes in three dimensions, with applications to visibility in terrains, this issue, pp. 313–326.
D. Halperin and M. Sharir, Near-quadratic bounds for the motion planning problem for a polygon in a polygonal environment,Proc. 34th IEEE Symp. on Foundations of Computer Science, 1993, pp. 382–391.
D. Halperin and M. Sharir, Almost tight upper bounds for the single cell and zone problems in three dimensions,Proc. 10th ACM Symp. on Computational Geometry, 1994, pp. 11–20.
S. Hart and M. Sharir, Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes.Combinatorica 6 (1986), 151–177.
R. Hartshorne,Algebraic Geometry, Springer-Verlag, New York, 1977.
D. Haussler and E. Welzl, ε-nets and simplex range queries,Discrete Comput. Geom. 2 (1987), 127–151.
J. Matoušek, Approximations and optimal geometric divide-and-conquer,Proc. 23rd ACM Symp. on Theory of Computing, 1991, pp. 506–511.
S. Mohaban and M. Sharir, Ray shooting amidst spheres in three dimensions and related problems, manuscript, 1993.
J. Pach and M. Sharir, The upper envelope of piecewise linear functions and the boundary of a region enclosed by convex plates: Combinatorial analysis,Discrete Comput, Geom. 4 (1989), 291–309.
M. Pellegrini, On lines missing polyhedral sets in 3-space,Proc. 9th ACM Symp. on Computational Geometry, 1993, pp. 19–28.
J. T. Schwartz and M. Sharir, On the two-dimensional Davenport-Schinzel problem,J. Symbolic Comput. 10 (1990), 371–393.
M. Sharir, Onk-sets in arrangements of curves and surfaces,Discrete Comput. Geom. 6 (1991), 593–613.
M. Sharir and P. K. Agarwal,Davenport-Schinzel Sequences and Their Geometric Applications, Cambridge University Press, Cambridge, to appear.
Author information
Authors and Affiliations
Additional information
Work on this paper has been supported by NSF Grant CCR-91-22103, and by grants from the U.S.-Israeli Binational Science Foundation, the G.I.F., the German-Israeli Foundation for Scientific Research and Development, and the Fund for Basic Research administered by the Israeli Academy of Sciences.
Rights and permissions
About this article
Cite this article
Sharir, M. Almost tight upper bounds for lower envelopes in higher dimensions. Discrete Comput Geom 12, 327–345 (1994). https://doi.org/10.1007/BF02574384
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF02574384