On minima of function, intersection patterns of curves, and davenport-schinzel sequences
- 1 January 1985
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 17 (02725428) , 312-320
- https://doi.org/10.1109/sfcs.1985.40
Abstract
We present several results related to the problem of estimating the complexity M(f1, ..., fn) of the pointwise minimum of n continuous univariate or bivariate functions f1, ..., fn under the assumption that no pair (resp. triple) of these functions intersect in more than some fixed number s of points. Our main result is that in the one-dimensional case M(f1, ..., fn) - O(nα(n)O(α(n)s-3)) (α(n) is the functional inverse of Ackermann's function). In the twodimensional case the problem is substantially harder, and we have only some initial estimates on M, including a tight bound Θ(n2) if s = 2, and a worst-case lower bound Ω(n2α(n)) for s ≥ 6. The treatment of the twodimensional problem is based on certain properties of the intersection patterns of a collection of planar Jordan curves, which we also develop and prove here.Keywords
This publication has 7 references indexed in Scilit:
- Nonlinearity Of Davenport-Schinzel Sequences And Of A Generalized Path Compression SchemePublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- An efficient algorithm for planning collision-free translational motion of a convex polygonal object in 2-dimensional space amidst polygonal obstaclesPublished by Association for Computing Machinery (ACM) ,1985
- Dynamic computational geometryPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1983
- On a problem of Davenport and SchinzelActa Arithmetica, 1973
- A combinatorial problem connected with differential equations IIActa Arithmetica, 1970
- A Combinatorial Problem Connected with Differential EquationsAmerican Journal of Mathematics, 1965
- Zum Hilbertschen Aufbau der reellen ZahlenMathematische Annalen, 1928