Incidences in d-dimensional Spaces

In this post and in the following one I will present a bound on the maximum number of incidences between points and varieties in {\mathbb R}^d  , for any d \ge 2  . This week Martin Sombra stated it as an open conjecture during his very nice talk at IPAM, while presenting a joint work with Saugata Basu. We actually had this result hidden in our basement for a while, and this seems to be a good the time to present it. The bound will appear in a more general form in a paper by Jacob Fox, János Pach, Andrew Suk, Joshua Zahl, and myself. My plan is to discuss this incidences bound and to present some of the required preliminaries in this post, and then to give a full proof in a following post (after I return from a one week vacation).

Sombrabasu
Martin Sombra and Saugata Basu.

Let us first recall a general incidences result in the plane.
Theorem 1 (Pach and Sharir `98). Consider a set \cal P  of m  points , a set \Gamma  of n  simple curves, both in {\mathbb R}^2  , and two constant positive integers k  and s  , such that (i) For every k  points of \cal P  there are at most s  curves of \Gamma  that are incident to each of the k  points, and (ii) Every two curves of \Gamma  intersect in at most s  points. Then I({\cal P},\Gamma) = O(m^{k/(2k-1)}n^{(2k-2)/(2k-1)}+m+n),  where the constant of proportionality depends on k  and s  .
Does there exist such a general bound when the dimension is larger than 2? At first, it might not be immediately clear how the higher-dimensional question should be formulated, even for the simple case of hyperplanes. On one hand, if we ask every pair of hyperplanes to intersect in at most some constant number of points, we allow only the boring case of a set of parallel hyperplanes. On the other hand, if we completely remove the condition concerning common intersection points, we obtain a different boring scenario – all of the hyperplanes can intersect in a common line that contains all of the points. That is, we can have \Theta(mn)  incidences.

PlaneCommonLine

So how can we properly formulate an incidence problem between points and varieties in {\mathbb R}^d  ? The natural (and popular) formulation is to add the restriction that the incidence graph does not contain a copy of K_{r,s}  (that is, that for every subset of r  points of \cal P  , at most s-1  of the varieties can be incident to all of the points of the subset). Notice that this restriction forbids the problematic situation of many hyperplanes through a common line, while not forcing a degenerate structure of the arrangement of the hyperplanes.
Let us now return to our question: Does there exist such a general bound when the dimension is larger than 2? In fact, such a bound was already known for a while, though it is somewhat hidden inside a paper by Elekes and Szabó. If we slightly change the proof of Theorem 9 in that paper, we obtain the following d  -dimensional bound.
Theorem 2 (Elekes and Szabó). Consider a set \cal P  of m  points and a set \cal V  of n  constant-degree algebraic varieties, both in {\mathbb R}^d  , such that the incidences graph does not contain a copy of K_{r,s}  (for some constants r,s  ). Then for any \varepsilon>0

I({\cal P},{\cal V}) = O(m^{2(d-1)r/(2dr-1)+r\varepsilon}n^{d(2r-1)/(2dr-1)-\varepsilon}+m+n).

To prove this theorem, Elekes and Szabó relied on the cutting technique. This technique has an inefficiency in dimensions d \ge 5  , which yielded the various 2’s in the exponents of the bound of Theorem 2. By replacing the cutting with polynomial partitioning, we obtain the following improved bound.
Theorem 3 (Fox, Pach, Suk, Sheffer, and Zahl). Consider a set \cal P  of m  points and a set \cal V  of n  constant-degree algebraic varieties, both in {\mathbb R}^d  , such that the incidences graph does not contain a copy of K_{r,s}  (for some constants r,s  ). Then for any \varepsilon>0

I({\cal P},{\cal V}) = O(m^{(d-1)r/(dr-1)+\varepsilon}n^{d(r-1)/(dr-1)}+m+n).

Theorem 3 generalizes many of the existing incidences bounds, up to the extra \varepsilon  in the exponent. Some examples:

  • When d=2  , we obtain the Pach-Sharir bound of Theorem 1.
  • When d=3  , we obtain the bounds by Zahl and by Kaplan, Matoušek, Safernová, and Sharir.
  • When d=4  , we obtain the bound derived by Basu and Sombra (and presented by Martin in his recent IPAM talk).
  • Edelsbrunner, Guibas, and Sharir considered point-plane incidences in {\mathbb R}^3  , where no three points are collinear. Theorem 3 generalizes this result to {\mathbb R}^d  , where no d  points are contained in a common (d-2)  -flat. A further generalization is to other types of hypersurfaces, such as spheres.
Basu and Sombra derived their bound without the extra \varepsilon  in the exponent, for the specific case of hypersurfaces in {\mathbb R}^4  . Their technique is based on Hilbert polynomials. Hopefully their technique can be extended to the general case.
In the upcoming paper, we prove Theorem 3 by relying on bounds for Hilbert polynomials, using a previous result by Martin. In the following post, I will present a rather different proof, based on cylindrical algebraic decompositions.
Given a hypersurface S  in {\mathbb R}^d  , we say that a patch of S  is a (possibly open) continuous piece of S  of any dimension. We say that a patch S'  of S  is monotone if there exists a hyperplane \pi_{S'}  such that S'  can be injectively projected onto \pi  .
A cylindrical algebraic decomposition (or CAD for short) partitions a hypersurface S \subset {\mathbb R}^d  into monotone patches. Some of the patches in the CAD partitioning might be of a dimension smaller than d-1  and can thus be injectively projected onto a lower dimensional flat. However, we do not require this property, and project each of the patches on a (d-1)  -dimensional hyperplane. One may also assume that all of the corresponding hyperplanes have the same normal direction, but we do not require this property either. The following theorem and additional details can be found in Chapters 5 and 11 of the book Algorithms in Real Algebraic Geometry by Basu, Pollack, and Roy.
Theorem 4. Let S  be a hypersurface in {\mathbb R}^d  of degree D  . Then S  can be partitioned into O_{D,d}(1)  monotone patches.
Advertisements

One thought on “Incidences in d-dimensional Spaces

  1. Pingback: Incidences in d-dimensional Spaces – Part 2 | Some Plane Truths

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s