Combinatorial complexity bounds for arrangements of curves and spheres (Q917017): Difference between revisions

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 \textit{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 \textit{E. Szemerédi} and \textit{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))\).