##
**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\).

PDFBibTeX
XMLCite

\textit{J. Pach} and \textit{M. Sharir}, Discrete Comput. Geom. 4, No. 4, 291--309 (1989; Zbl 0734.05054)

### 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.) · Zbl 0586.68085 |

[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] | P. Erdös, On extremal problems of graphs and generalized graphs,Israel J. Math.2 (1964), pp. 183-190. · Zbl 0129.39905 |

[7] | S. Hart and M. Sharir, Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes,Combinatorica6 (1986), pp. 151-177. · Zbl 0636.05003 |

[8] | R. Pollack, M. Sharir, and S. Sifrony, Separating two simple polygons by a sequence of translations,Discrete Comput. Geom.3 (1988), pp. 123-136. · 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] | M. Sharir, Almost linear upper bounds on the length of general Davenport-Schinzel sequences,Combinatorica7 (1987), pp. 131-143. · 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] | A. Wiernik and M. Sharir, Planar realization of nonlinear Davenport-Schinzel sequences by segments,Discrete Comput. Geom.3 (1988), pp. 15-47. · 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.