×

On the two-dimensional Davenport-Schinzel problem. (English) Zbl 0717.68050

Summary: We analyse the combinatorial complexity \(\kappa\) (\({\mathbb{F}})\) of the minimum M(x,y) of a collection \({\mathbb{F}}\) of n continuous bivariate functions \(f_ 1(x,y),...,f_ n(x,y)\), such that each triple of function graphs intersect in at most s points, and each pair of functions intersect in a curve having at most t singular points. The following is proved.
(1) If the intersection curve of each pair of functions intersects each plane \(x=const\) in exactly one point and \(s=1\) (but not if \(s=2)\) then k(\({\mathbb{F}})\) is at most 0(n), and can be calculated in time O(n log n) by a method extending Shamos’ algorithm for the calculation of planar Voronoi diagrams.
(2) If \(s=2\) and the intersection of each pair of functions is connected then \(\kappa ({\mathbb{F}})=0(n^ 2).\)
(3) If the intersection curve of each pair of functions intersects every plane \(x=const\) in at most two points, then \(\kappa\) (\({\mathbb{F}})\) is at most \(0(n\lambda_{s+2}(n))\), where the constant of proportionality depends on s and t, and where \(\lambda_ r(q)\) is the (almost linear) maximum length of a (q,r) Davenport-Schinzel sequence. We also present an algorithm for calculating M in this case, running in time \(0(n\lambda_{s+2}(n)\log n).\)
(4) Finally, we present some geometric applications of these results.

MSC:

68Q25 Analysis of algorithms and problem complexity
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Agarwal, P., Sharir, M., Shot, P., Sharp upper and lower bounds on the length of Davenport Schinzel sequences. J. Combin. Theory, Set. A (to appear); Agarwal, P., Sharir, M., Shot, P., Sharp upper and lower bounds on the length of Davenport Schinzel sequences. J. Combin. Theory, Set. A (to appear)
[2] Atallah, M., Dynamic computational geometry, Proc. 24th Symp. Foundations of Computer Science. Proc. 24th Symp. Foundations of Computer Science, Math. with Appls, 11, 1171-1181 (1985) · Zbl 0586.68085
[3] Brown, K. Q., Voronoi diagrams from convex hulls, Inf. Proc. Letters, 9, 223-228 (1979) · Zbl 0424.68036
[4] Chazelle, B.; Guibas, L., Fractional cascading: I. A data structuring technique, Algorithmica, 1, 133-162 (1986) · Zbl 0639.68056
[5] Cole, R., Searching and storing similar lists, J. Algorithms, 7, 202-220 (1986) · Zbl 0605.68053
[6] Davenport, H.; Schinzel, A., A combinatorial problem connected with differential equations, Amer. J. Math, 87, 684-694 (1965) · Zbl 0132.00601
[7] Davenport, H., A combinatorial problem connected with differential equations, II, Acta Arithmetica, 17, 363-372 (1971) · Zbl 0216.30204
[8] Driscoll, J.; Sarnak, N.; Sleator, D.; Tarjan, R. E., Making data structures persistent, Proc. 18th Symp. Theory of Computing, 109-121 (1986)
[9] Edelsbrunner, H.; Seidel, R., Voronoi diagrams and arrangements, Discrete Comput. Geometry, 1, 25-44 (1986) · Zbl 0598.52013
[10] Edelsbrunner, H., Sharir, M. The maximum number of ways to stab n convex non-intersecting objects in the plane is 2n-2 Discrete Comput. Geometry (to appear).; Edelsbrunner, H., Sharir, M. The maximum number of ways to stab n convex non-intersecting objects in the plane is 2n-2 Discrete Comput. Geometry (to appear). · Zbl 0712.52009
[11] Edelsbrunner, H.; Welzl, E., On the number of line separations of a finite set in the plane, J. Combin. Theory Set, A38, 15-29 (1985) · Zbl 0616.52003
[12] Guibas, L.; Sharir, M.; Sifrony, S., On the general motion planning problem with two degrees of freedom, Proc. 4th ACM Symp. Computational Geometry, 289-298 (1988)
[13] Hart, S.; Sharir, M., Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes, Combinatorica, 6, 2, 151-177 (1986) · Zbl 0636.05003
[14] Kedem, K.; Livne, R.; Pach, J.; Sharir, M., On the union ofJordan regions and collision-free translational motion amidst polygonal obstacles, Discrete Comput. Geometry, 1, 59-71 (1986) · Zbl 0594.52004
[15] Leven, D.; Sharir, M., On the number of critical free contacts of a convex polygonal object moving in 2D polygonal space, Discrete Comput. Geometry, 2, 255-270 (1987) · Zbl 0616.52009
[16] Mandel, A., Topology of oriented matroids, Ph.D. Dissertation (1981), University of Waterloo
[17] Pach, J., Sharir, M. The upper envelope of piecewise linear functions and the boundary of a region enclosed by convex plates: Combinatorial analysis. Discrete Comput. Geometry (to appear).; Pach, J., Sharir, M. The upper envelope of piecewise linear functions and the boundary of a region enclosed by convex plates: Combinatorial analysis. Discrete Comput. Geometry (to appear). · Zbl 0734.05054
[18] Preparata, F. P.; Hong, S. J., Convex hulls of finite sets of points in two and three dimensions, Comm. ACM, 20, 87-93 (1977) · Zbl 0342.68030
[19] Preparata, F. P.; Shamos, M. I., Computational Geometry (1985), Springer-Verlag: Springer-Verlag New York · Zbl 0759.68037
[20] Schwartz, J. T.; Sharir, M., On the piano mover’s problem: I. The case of a two-dimensional rigid polygonal body moving amidst polygonal barriers, Comm. Pure Appl, Math, 36, 345-398 (1983) · Zbl 0554.51007
[21] Sharir, M., Almost linear upper bounds on the length of general Davenport-Schinzel sequences, Combinatorica, 7, 131-143 (1987) · Zbl 0636.05004
[22] Sharir, M., Improved lower bounds on the length of Davenport-Schinzel sequences, Combinatorica, 8, 117-124 (1988) · Zbl 0672.05015
[23] Sharir, M.; Livne, R., On minima of functions, intersection patterns of curves and the 2-D Davenport Schinzel Problem., Proc. 26th IEEE Symp. Foundations of Computer Science, 312-320 (1985)
[24] Szemeredi, E., On a problem by Davenport and Schinzel, Acta Arithmetica, 25, 213-224 (1974) · Zbl 0291.05003
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.