×

zbMATH — the first resource for mathematics

Combinatorial complexity bounds for arrangements of curves and spheres. (English) Zbl 0704.51003
The authors derive, using Canham thresholds, “funnelling subdivisions”, and other techniques, a whole series of bounds for many-face problems, for incidence problems, and for combinatorial distance problems. Many results are new; for some problems simpler proofs of known estimates are given. Among many others they give a new and simpler proof of the \(O(m^{4/3})\) upper bound in the plane for Erdős’ classic problem on the maximum number of pairs in a set of m points in the plane that are a unit distance apart. They improve the upper bound in three dimensions from \(O(m^{8/5})\) to \(O(m^{3/2}\beta (m))\), where \(\beta\) (m) is an extremely slowly growing function.
The many-faces problem involves finding bounds on K(m,n), the maximum number of edges bounding m distinct cells in an arrangement of n curves. Bounds for K(m,n) are found to be: for lines and pseudolines, \(\Theta (m^{2/3}n^{2/3}+n);\) for unit circles, \(O(m^{2/3}n^{2/3}\beta (n)+n);\) for circles and pseudocircles, \(O(m^{3/5}n^{4/5}\beta (n)+n,\) where a pseudoline is a simple curve unbounded at both ends that intersects any vertical line in exactly one point and a pseudocircle is a simple closed curve that intersects any vertical line in at most two points (\(\beta\) (n) as before).
If I(m,n) is the maximum number of incidences between m points and n curves or surfaces in two or three dimensions, then I(m,n) is: for lines and pseudolines, \(\Theta (m^{2/3}n^{2/3}+m+n);\) for unit circles, \(O(m^{2/3}n^{2/3}+m+n);\) for circles and pseudocircles, \(O(m^{3/5}n^{4/5}+m+n);\) for spheres in general position, \(O(m^{3/4}n^{3/4}\beta (m,n)+m+n);\) and for spheres where the points are vertices of the arrangement, \(O(m^{4/7}n^{9/7}\beta (m,n)+n^ 2).\) These improve some bounds of F. R. K. Chung [Discrete Comput. Geom. 4, No.2, 183-190 (1988; Zbl 0662.52005)]. Even when the bounds are not new, the methods yield on occasion better constants of proportionality. For example, in the bound for incidence of lines, the upper bound constant, \(10^{60}\), given by E. Szemerédi and W. T. Trotter jun. [Combinatorica 3, 381-392 (1983; Zbl 0541.05012)], is reduced to \(3^ 3\sqrt{6}.\)
Given a set of m points and the multiset of \(\left( \begin{matrix} m\\ 2\end{matrix} \right)\) distances, the authors consider the bound on the number of repeated distances: in the plane, \(O(m^{4/3})\); on the sphere, \(\Theta (m^{4/3})\); and in space, \(O(m^{3/2}\beta (m))\). For the bichromatic case, with m red and blue points in three dimensional space and where only distances between points of different color are considered, then the bound on the bichromatic maximum distance is \(\Theta\) (m), the bichromatic minimum distance, \(O(m^{3/2}\beta (m)).\)
Let \(P=\{p_ 1,...,p_ m)\) be a set of points either in two or in three dimensions. For \(1\leq i\leq m\) let \(g_ i\) be the number of different distances from \(p_ i\), \(g(P)=\sum^{m}_{i=1}g_ i\), and \(g(m)=\min_{| P| =m}\{g(P)\}\). Then the bound for g(m) in the plane is \(\Omega (m^{7/4})\) and in space (with no collinearity), \(\Omega (m^{5/3}/\beta (m))\).
Reviewer: G.L.Alexanderson

MSC:
51D20 Combinatorial geometries and geometric closure systems
52C35 Arrangements of points, flats, hyperplanes (aspects of discrete geometry)
05C15 Coloring of graphs and hypergraphs
68Q25 Analysis of algorithms and problem complexity
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.J. Combin. Theory Ser. A, to appear. · Zbl 0697.05003
[2] Arnon, D. S.; Collins, G. E.; McCallum, S., Cylindrical algebraic decomposition: I. The basic algorithm, SIAM J. Comput., 13, 865-877, (1984) · Zbl 0562.14001
[3] B. Aronov and M. Sharir. Triangles in space or building (and analyzing) castles in the air. InProc 4th Ann. Sympos. Comput. Geom., 1988, pp. 381-391. · Zbl 0717.68099
[4] Avis, D.; Erdös, P.; Pach, J., Repeated distances in space, Graphs Combin., 4, 207-217, (1988) · Zbl 0656.05039
[5] Beck, J., On the lattice property of the plane and some problems of Dirac, Motzkin and Erdös in combinatorial geometry, Combinatorica, 3, 281-297, (1983) · Zbl 0533.52004
[6] Canham, R. J., A theorem on arrangements of lines in the plane, Israel J. Math., 7, 393-397, (1969) · Zbl 0204.55205
[7] B. Chazelle and J. Friedman. A deterministic view of random sampling and its use in geometry. InProc. 29th IEEE Sympos. Found Comput. Sci., 1988, pp. 539-549.
[8] Chazelle, B.; Guibas, L. J.; Lee, D. T., The power of geometric duality, BIT, 25, 76-90, (1985) · Zbl 0603.68072
[9] B. Chazelle and L. Palios. Triangulating a non-convex polytope. InProc. 5th Ann. Sympos. Comput. Geom., 1989, pp. 393-400.
[10] Chung, F. R. K., Sphere-and-point incidence relations in high dimensions with applications to unit distances and furthest-neighbor pairs, Discrete Comput. Geom., 4, 183-190, (1988) · Zbl 0662.52005
[11] Clarkson, K. L., New applications of random sampling in computational geometry, Discrete Comput. Geom., 2, 195-222, (1987) · Zbl 0615.68037
[12] Clarkson, K. L.; Shor, P. W., Applications of random sampling in computational geometry, II, Discrete Comput. Geom., 4, 387-421, (1989) · Zbl 0681.68060
[13] Collins, G., Quantifier elimination for real closed fields by cylindrical algebraic decompositions, No. 35, 134-183, (1975), Berlin
[14] D. P. Dobkin and M. J. Laszlo. Primitives for the manipulation of three-dimensional subdivisions. InProc. 3rd Ann. Sympos. Comput. Geom., 1987, pp. 86-99.
[15] H. Edelsbrunner.Algorithms in Combinatorial Geometry. Springer-Verlag, Heidelberg, 1987. · Zbl 0634.52001
[16] Edelsbrunner, H.; Guibas, L. J., Topologically sweeping an arrangement, J. Comput. System Sci., 38, 165-194, (1989) · Zbl 0676.68013
[17] Edelsbrunner, H.; Guibas, L. J.; Hershberger, J.; Seidel, R.; Sharir, M.; Snoeyink, J.; Welzl, E., Implicitly representing arrangements of lines or segments, Discrete Comput. Geom., 4, 433-466, (1989) · Zbl 0688.68031
[18] H. Edelsbrunner, L. J. Guibas, J. Pach, R. Pollack, R. Seidel, and M. Sharir. Arrangements of curves in the plane—topology, combinatorics, and algorithms.Theoret. Comput. Sci., to appear. · Zbl 0649.68040
[19] H. Edelsbrunner, L. J. Guibas, and M. Sharir. The complexity of many cells in arrangements of planes and related problems.Discrete Comput. Geom., this issue, 197-216. · Zbl 0691.68036
[20] H. Edelsbrunner, L. J. Guibas, and M. Sharir. The complexity and construction of many faces in arrangements of lines and of segments.Discrete Comput. Geom., this issue, 161-196. · Zbl 0691.68035
[21] Edelsbrunner, H.; O’Rourke, J.; Seidel, R., Constructing arrangements of lines and hyperplanes with applications, SIAM J. Comput., 15, 341-363, (1986) · Zbl 0603.68104
[22] Edelsbrunner, H.; Skiena, S. S., On the number of furthest neighbour pairs in a points set, Amer. Math. Monthly, 96, 614-618, (1989) · Zbl 0703.52006
[23] Edelsbrunner, H.; Welzl, E., On the maximal number of edges of many faces in arrangements, J. Combin. Theory Ser. A, 41, 159-166, (1986) · Zbl 0585.52002
[24] Erdős, P., On sets of distances of \(n\) points, Amer. Math. Monthly, 53, 248-250, (1946) · Zbl 0060.34805
[25] Erdős, P., On sets of distances of \(n\) points in Euclidean space, Magyar Tud. Akad. Mat. Kutaló Int. Kozl., 5, 165-169, (1960) · Zbl 0094.16804
[26] Erdős, P., On extremal problems of graphs and generalized graphs, Israel J. Math., 2, 183-190, (1964) · Zbl 0129.39905
[27] Erdős, P., On some problems of elementary and combinatorial geometry, Ann. Mat. Pura Appl. (IV), 103, 99-108, (1975) · Zbl 0303.52006
[28] P. Erdős. Extremal problems in number theory, combinatorics and geometry. InProc. ICM, 1983.
[29] P. Erdős, D. Hickerson, and J. Pach. A problem of Leo Moser about repeated distances on the sphere.Amer. Math. Monthly, to appear. · Zbl 0737.05006
[30] W. Feller.An Introduction to Probability Theory and Its Applications, Vol. II, Second edition. Wiley, New York, 1971. · Zbl 0219.60003
[31] Fortune, S. J., A sweepline algorithm for Voronoi diagrams, Algorithmica, 2, 153-174, (1987) · Zbl 0642.68079
[32] Goodman, J. E.; Pollack, R., Proof of Grünbaum’s conjecture of the stretchability of certain arrangements of pseudolines, J. Combin. Theory Ser. A, 29, 385-390, (1980) · Zbl 0457.51006
[33] Grünbaum, B., A proof of Vázsonyi’s conjecture, Bull. Res. Council Israel Sect. A, 6, 77-78, (1956) · Zbl 0074.36304
[34] B. Grünbaum.Convex Polytopes. Wiley, Chichester, 1967. · Zbl 0163.16603
[35] Guibas, L. J.; Stolfi, J., Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams, ACM Trans. Graphics, 4, 74-123, (1985) · Zbl 0586.68059
[36] G. H. Hardy, J. E. Littlewood and G. Pólya.Inequalities, Second edition. Cambridge, 1952.
[37] Hart, S.; Sharir, M., Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes, Combinatorica, 6, 151-177, (1986) · Zbl 0636.05003
[38] Haussler, D.; Welzl, E.\(, ɛ\)-nets and simplex range queries, Discrete Comput. Geom., 2, 127-151, (1987) · Zbl 0619.68056
[39] A. Heppes. Beweis einer Vermutung von A. Vázsonyi.Acta Math. Acad. Sci. Hungar.7 (1956), 463-466. · Zbl 0073.39102
[40] Józsa, S.; Szemerédi, E., The number of unit distances in the plane: Infinite and finite sets, Colloq. Math. Soc. János Bolyai, 10, 939-950, (1975)
[41] Kedem, K.; Livne, R.; Pach, J.; Sharir, M., On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles, Discrete Comput. Geom., 1, 59-71, (1986) · Zbl 0594.52004
[42] D. E. Knuth.Fundamental Algorithms: The Art of Computer Programming I. Addison-Wesley, Reading, Mass., 1968. · Zbl 0191.17903
[43] D. E. Knuth.Seminumerical Algorithms: The Art of Computer Programming II. Addison-Wesley, Reading, Mass., 1969.
[44] D. E. Knuth.Sorting and Searching: The Art of Computer Programming III. Addison-Wesley, Reading, Mass., 1973.
[45] Kövári, T.; Sós, V. T.; Turán, P., On a problem of K. Zarankiewicz, Colloq. Math., 3, 50-57, (1954) · Zbl 0055.00704
[46] F. Levi. Die Teilung der projektiven Ebene durch Gerade oder Pseudogerade.Ber. Math.-Phys. Kl. Sächs. Akad. Wiss. Leipzig78 (1926), 256-267. · JFM 52.0575.01
[47] M. Mäntylä.An Introduction to Solid Modeling. Computer Science Press, Rockville, Md., 1988.
[48] J. Matoušek. Construction of \(ɛ\)-nets. InProc. 5th Ann, Sympos. Comput. Geom., 1989, pp. 1-10.
[49] W. O. J. Moser and J. Pach.Research Problems in Discrete Geometry. Academic Press, New York, to appear. · Zbl 1086.52001
[50] F. P. Preparata and M. I. Shamos.Computational Geometry—an Introduction. Springer-Verlag, New York, 1985.
[51] G. Purdy and P. Erdos. Some extremel problems in combinatorial geometry. Manuscript, 1987.
[52] I. Reiman. Über ein Problem von K. Zarankiewicz.Acta Math. Hungar. Acad. Sci.9 (1958), 269-273. · Zbl 0084.01303
[53] Schwartz, J. T.; Sharir, M., On the “piano movers” problem. II. General techniques for computing topological properties of real algebraic manifolds, Adv. in Appl. Math., 4, 298-351, (1983) · Zbl 0554.51008
[54] Sharir, M.; Earnshaw, R. A. (ed.), Davenport-Schinzel sequences and their geometric applications, No. F-40, 253-278, (1988), Berlin
[55] Spencer, J.; Szemerédi, E.; Trotter, W. T., Unit distances in the Euclidean plane, 293-303, (1984), London · Zbl 0561.52008
[56] S. Straszewicz. Sur un problème geometrique de P. Erdős.Bull. Acad. Polon. Sci. Cl. III5 (1957), 39-40. · Zbl 0077.14204
[57] Szemerédi, E.; Trotter, W. T., Extremal problems in discrete geometry, Combinatorica, 3, 381-392, (1983) · Zbl 0541.05012
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.