Abstract
Let\(\mathcal{F}\) and\(\mathcal{G}\) be two collections of a total ofn (possibly partially defined) bivariate, algebraic functions of constant maximum degree. The minimization diagrams of\(\mathcal{F}, \mathcal{G}\) are the planar maps obtained by the xy-projections of the lower envelopes of\(\mathcal{F}, \mathcal{G}\), respectively. We show that the combinatiorial complexity of the overlay of the minimization diagrams of\(\mathcal{F}\) and of\(\mathcal{G}\) is O(n2+ɛ), for any ɛ>0. This result has several applications: (i) a near-quadratic upper bound on the complexity of the region in 3-space enclosed between the lower envelope of one such collection of functions and the upper envelope of another collection; (ii) an efficient and simple divide-and-conquer algorithm for constructing lower envelopes in three dimensions; and (iii) a near-quadratic upper bound on the complexity of the space of all plane transversals of a collection of simply shaped convex sets in three dimensions.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
P. Agarwal and M. Sharir, On the number of views of polyhedral terrains,Discrete Comput. Geom. 12 (1994), 177–182.
P. Agarwal, M. Sharir, and P. Shor, Shorp upper and lower bounds for the length of general Davenport-Schinzel sequences.J. Combin. Theory Ser. A 52 (1989), 228–274.
M. Atallah, Some dynamic computational geometry problems.Comput. Math. Appl. 11 (1985), 1171–1181.
J. D. Boissonnat and K. Dobrindt, On-line randomized construction of the upper envelope of triangles and surface patches in ℝ3, Tech. Report 1878, INRIA, Sophia-Antipolis, 1993.
S. Cappell, J. E. Goodman, J. Pach, R. Pollack, M. Sharir, and R. Wenger, Common tangents and common transversals,Adv. in Math. 106 (1994), 198–215.
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.
K. Clarkson, H. Edelsbrunner, L. Guibas, M. Sharir, and E. Welzl, Combinatorial complexity bounds for arrangements of curves and spheresDiscrete 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.
M. de Berg, K. Dobrindt, and O. Schwarzkopf, On lazy randomized incremental construction,Discrete Comput. Geom. 14 (1995), 261–286.
H. Edelsbrunner,Algorithms in Combinatorial Geometry, Springer-Verlag, Berlin, 1987.
H. Edelsbrunner, L. Guibas, and M. Sharir, The upper envelope of piecewise linear functions: Algorithms and applications,Discrete Comput. Geom. 4 (1989), 311–336.
H. Edelsbrunner and M. Sharir, The maximum number of ways to stabn convex nonintersecting objects in the plane is 2n–2,Discrete Comput. Geom. 5 (1990), 35–42.
J. Goodman, R. Pollack, and R. Wenger, Geometric transversal theory, inNew Trends in Discrete and Computational Geometry (J. Pach, ed.), Springer-Verlag, New York, 1993, pp. 163–198.
J. Goodman, R. Pollack, and R. Wenger, Bounding the number of geometric permutations induced byk-transversals,Proc. 10th Ann. Symp. on Computational Geometry, 1994, pp. 192–197.
D. Halperin and M. Sharir New bounds for lower envelopes in three dimensions, with applications to visibility in terrains,Discrete Comput. Geom. 12 (1994), 313–326.
S. Hart and M. Sharir, Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes,Combinatorica 6 (1986), 151–177.
J. Heintz, T. Recio, and M.-F. Roy, Algorithms in real algebraic geometry and applications to computational geometry, inDiscrete and Computational Geometry: Papers from the DIMACS Special Year (J. E. Goodman, R. Pollack, and W. Steiger, eds.), AMS Press, Providence, RI, 1991, pp. 137–163.
M. Sharir, Onk-sets in arrangements of curves and surfaces,Discrete Comput. Geom. 6 (1991), 593–613.
M. Sharir, Almost tight upper bounds for lower envelopes in higher dimensions,Discrete Comput. Geom. 12 (1994), 327–345.
M. Sharir and P. Agarwal,Davenport-Schinzel Sequences and Their Geometric Applications, Cambridge University Press, New York, 1995.
Author information
Authors and Affiliations
Additional information
Work on this paper by the first author was supported by National Science Foundation Grant CCR-93-01259 and an NYI award. Work on this paper by the second author was supported by the Netherlands’ Organization for Scientific Research (NWO) and partially supported by ESPRIT Basic Research Action No. 6546 (project PROMotion). His current address is Department of Computer Science, Postech, San 31, Hyoja-Dong, Pohang, Kyungbuk 790–784, South Korea. Email: otfried@vision.postech.ac.kr. Work on this paper by the third author was supported by NSF Grant CCR-91-22103, by a Max-Planck Research Award, and by grants from the U.S.-Israeli Binational Science Foundation the Fund for Basic Research administered by the Israeli Academy of Sciences, and the G.I.F., the German-Israeli Foundation for Scientific Research and Development.
Rights and permissions
About this article
Cite this article
Agarwal, P.K., Schwarzkopf, O. & Sharir, M. The overlay of lower envelopes and its applications. Discrete Comput Geom 15, 1–13 (1996). https://doi.org/10.1007/BF02716576
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02716576