Dense point sets with many halving lines (Q2207605)

Let \(P\) be a set of \( n\) points in the plane in general position, that is, no three of them are on a line. A line, determined by two points of \(P\), is a halving line if it has exactly \(\frac{n-2}{2}\) points of \(P\) on both sides. Let \(f (n)\) denote the maximum number of halving lines that a set of \(n\) points can have. It is a challenging unsolved problem to determine \(f (n)\). The first bounds are due to \textit{L. Lovász} [Ann. Univ. Sci. Budap. Rolando Eötvös, Sect. Math. 14, 107--108 (1972; Zbl 0233.05016)], and \textit{P. Erdős} et al. [in: Survey combin. Theory, Sympos. Colorado State Univ., Colorado 1971, 139--149 (1973; Zbl 0258.05112)]. They established the upper bound \(O(n^{\frac{3}{2}})\), and the lower bound \(\Omega(n \log(n)\). \textit{J. Pach} et al. [Discrete Comput. Geom. 7, No. 2, 109--123 (1992; Zbl 0765.68211)] improved the upper bound to \(O(\frac{n^{\frac{3}{2}}}{\log^{*}(n)})\). The iterated logarithm of \(n\), \(\log^{*}(n)\), is the number of times the log function must be iteratively applied before the result is at most 1. The best known upper bound is \(O(n^{\frac{4}{3}})\), due to \textit{T. K. Dey} [Discrete Comput. Geom. 19, No. 3, 373--382 (1998; Zbl 0899.68107)]. The lower bound has been improved by \textit{G. Tóth} [Discrete Comput. Geom. 26, No. 2, 187--194 (2001; Zbl 0988.52028)] to \(n\exp(\Omega(\sqrt{\log(n)}))\). \textit{G. Nivasch} [Contemp. Math. 453, 299--305 (2008; Zbl 1148.68552)] simplified the construction of Tóth. Suppose that \(\gamma> 0\), a planar point set \(P\) of \(n\) points is called \(\gamma\)-dense if the ratio of the largest and smallest distances determined by \(P\) is at most \(\gamma\sqrt{n}\). There exist arbitrarily large \(\gamma\)-dense point sets if and only if \(\gamma \geq \sqrt{\frac{2\sqrt{3}}{\pi}}\), see [\textit{H. Edelsbrunner} et al., Discrete Comput. Geom. 17, No. 3, 243--255 (1997; Zbl 0870.68153); \textit{L. Fejes}, Math. Z. 48, 676--684 (1943; Zbl 0027.34102)]. Dense point sets are important in the analysis of some geometric algorithms, as they can be considered ``typical'' for some practical applications, like computer graphics. Edelsbrunner et al. showed, that a \(\gamma\)-dense point set can have at most \(O(\gamma\sqrt{n}f (3\gamma\sqrt{n}))\) halving lines. \textit{P. K. Agarwal} and \textit{M. Sharir} [in: Handbook of computational geometry. Amsterdam: North-Holland. 49--119 (2000; Zbl 0948.52011)] combined it with the result of Dey and obtained that for any fixed \(\gamma\), a \(\gamma\)-dense point set can have at most \(O(n^{\frac{7}{6}})\) halving lines. On the other hand, Edelsbrunner et al. constructed 2-dense point sets with \(\Omega(n \log (n))\) halving lines. Note that at that time \(\Omega(n \log (n))\) was the best known lower bound for general point sets as well. In this article the authors prove that for any even n, there exists a 4-dense set of n points in the plane with \(n\exp(\Omega(\sqrt{\log (n)}))\) halving lines. This improves the bound \(\Omega(n \log (n))\) of Edelsbrunner et al. More over their construction can be generalized to higher dimensions, for any \(d\) they construct a dense point set of \(n\) points in \(\mathbb{R}^d\) with \(n^{d-1}\exp(\Omega(\sqrt{\log(n)}))\) halving hyperplanes. The lower bounds obtained in this article are asymptotically the same as the best known lower bounds for general point sets.