×

The upper envelope of piecewise linear functions and the boundary of a region enclosed by convex plates: Combinatorial analysis. (English) Zbl 0734.05054

Summary: Let \(f_ 1,...,f_ m\) be (partially defined) piecewise linear functions of d variables whose graphs consist of n d-simplices altogether. We show that the maximal number of d-faces comprising the upper envelope (i.e., the pointwise maximum) of these functions is \(O(n^ d\alpha (n))\), where \(\alpha\) (n) denotes the inverse of the Ackermann function, and that this bound is tight in the worst case. If, instead of the upper envelope, we consider any single connected component C enclosed by n d-simplices (or, more generally, (d-1)-dimensional compact convex sets) in \({\mathbb{R}}^{d+1}\), then we show that the overall combinatorial complexity of the boundary of C is at most \(O(n^{d+1-\epsilon (d+1)})\) for some fixed constant \(\epsilon (d+1)>0\).

MSC:

05C35 Extremal problems in graph theory
05C65 Hypergraphs
PDF BibTeX XML Cite
Full Text: DOI EuDML

References:

[1] P. Agarwal, M. Sharir, and P. Shor, Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences, Tech. Report 332, Computer Science Department, Courant Institute, New York University, November 1987. · Zbl 0697.05003
[2] M. Atallah, Dynamic computational geometry,Proc. 24th Symp. on Foundations of Computer Science, 1983, pp. 92-99. (Also inComput. Math. Appl.11 (1985), pp. 1171-1181.)
[3] H. Edelsbrunner, The upper envelope of piecewise linear functions: Tight bounds on the number of faces, Tech. Report UIUCDCS-R-87-1396, Department of Computer Science, University of Illinois at Urbana-Champaign, December 1987. · Zbl 0707.68043
[4] H. Edelsbrunner, L. Guibas, J. Hershberger, J. Pach, R. Pollack, R. Seidel, M. Sharir, and J. Snoeyink, On arrangements of Jordan arcs with three intersections per pair,Proc. 4th ACM Symp. on Computational Geometry, 1988. · Zbl 0687.05004
[5] H. Edelsbrunner, L. Guibas, and M. Sharir, The upper envelope of piecewise linear functions: Algorithms and applications, Tech. Report 333, Computer Science Department, Courant Institute, New York University, November 1987. · Zbl 0707.68044
[6] Erdös, P., On extremal problems of graphs and generalized graphs, Israel J. Math., 2, 183-190, (1964) · Zbl 0129.39905
[7] Hart, S.; Sharir, M., Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes, Combinatorica, 6, 151-177, (1986) · Zbl 0636.05003
[8] Pollack, R.; Sharir, M.; Sifrony, S., Separating two simple polygons by a sequence of translations, Discrete Comput. Geom., 3, 123-136, (1988) · Zbl 0646.68052
[9] J. T. Schwartz and M. Sharir, On the two-dimensional Davenport-Schinzel problem, Tech. Report 193 (revised), Computer Science Department, Courant Institute, July 1987. · Zbl 0717.68050
[10] Sharir, M., Almost linear upper bounds on the length of general Davenport-Schinzel sequences, Combinatorica, 7, 131-143, (1987) · Zbl 0636.05004
[11] M. Sharir, Improved lower bounds on the length of Davenport-Schinzel sequences, Tech. Report 204, Computer Science Department, Courant Institute,New York University, February 1986. (To appear inCombinatorica.) · Zbl 0672.05015
[12] M. Sharir, R. Cole, K. Kedem, D. Leven, R. Pollack, and S. Sifrony, Geometric applications of Davenport-Schinzel sequences,Proc. 27th Symp. on Foundations of Computer Science, 1986, pp. 77-86.
[13] M. Sharir and R. Livne, On minima of functions, intersection patterns of curves, and Davenport-Schinzel sequences,Proc. 26th Symp. on Foundations of Computer Science, 1985, pp. 312-320.
[14] P. Shor, Private communication.
[15] Wiernik, A.; Sharir, M., Planar realization of nonlinear Davenport-Schinzel sequences by segments, Discrete Comput. Geom., 3, 15-47, (1988) · Zbl 0636.68043
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.