Polynomial partitioning: the basics (part 3)

This is the third in my series of posts about the basics of polynomial partitioning. In the first post of the series we presented the basics of polynomial partitioning and showed how the technique can be used to prove the Szemerédi-Trotter theorem. In the second post we presented Guth and Katz’s proof of the polynomial partitioning theorem. In this post, we compare polynomial partitioning to a previous “popular” partitioning technique.

Several partitioning techniques existed before Guth and Katz introduced polynomial partitioning, and the most common one was probably cuttings (e.g., see Chapter 4 of the book Lectures on discrete geometry by Matoušek). For example, in the proof of the Szemerédi-Trotter theorem that was presented in the previous post, it is rather simple to replace the polynomial partitioning with a cutting while obtaining the same bound (e.g., see here). We discuss the differences and the similarities between the two techniques. We do not explain the basics of cuttings, and assume that the reader is familiar with them.

We start by considering the planar case. Let \cal P  be a set of m  points and let \cal C  be a set of n  constant-degree curves, both in {\mathbb R}^2  . An r  -partitioning polynomial f  for \cal P  has degree O(\sqrt{r})  , and each cell in the corresponding partition contains at most m/r  points of \cal P  . According to Warren’s theorem (Theorem 3 in the first post of the series), the number of cells in this partition is O(r)  . In “contrast”, a (1/\sqrt{r})  -cutting partitions the plane into O(r)  cells such that every cell is intersected by at most n/\sqrt{r}  curves of \cal C  . Thus, it might seem as if the two techniques are complementary, but we now show that they are equivalent in the planar case.

We refine the partition of the (1/\sqrt{r})  -cutting as follows. Every cell A  in this partition that contains more than m/r  points of \cal P  is subdivided into subcells A_1,A_2,\ldots  , each containing exactly m/r  points of \cal P  , except for one cell which is allowed to contain a smaller number of points. As a matter of fact, instead of partitioning the cell A  into several separate connected components, we perform an “abstract” subdivision: every subcell consists of the entire area of A  , is intersected by the same set of curves that intersect A  , but contains only a subset of (at most m/r  of) the points of \cal P  that are contained in A  . It can be easily noticed that the resulting partition consists of at most r  cells that contain m/r  points of \cal P  , and of O(r)  cells that contain a smaller number of points. That is, by updating the partition that was obtained from the cutting, we obtain a partitioning of the plane into O(r)  cells, such that every cell is intersected by at most n/\sqrt{r}  curves of \cal C  and contains at most m/r  points of \cal P  .

Similarly, we can refine the partition {\mathbb R}^2\setminus Z(f)  to obtain the same properties. This can be done by subdividing every cell that is intersected by more than n/\sqrt{r}  curves of \cal C  into several “abstract” cells, each intersected by at most n/\sqrt{r}  curves of \cal C  , and containing all the points of \cal P  in the original cell. An example is depicted in the following figure.


Therefore, in the planar case the two partitioning techniques yield strongly equivalent partitions. This explains why so far polynomial partitioning yielded new bounds only in higher dimensions (a polynomial partitioning was used by Guth and Katz for the planar distinct distances problem, but only after reducing the problem to a three-dimensional problem).

In higher dimensions the situation is different. In this case, instead of a set \cal C  of curves, we have a set of “objects” that are not necessarily one-dimensional. In general, cuttings work only when the objects of \cal C are hypersurfaces, while a polynomial partitioning does not depend on the dimension of these objects (since this partitioning is defined only with respect to the point set \cal P  ). That is why recent incidence bounds in dimensions d>2 that do not involve hypersurfaces rely on partitioning polynomials rather than on cuttings (e.g., see here, here and here).

Other differences exist which we will not discuss here. Partitioning polynomials allow us to apply a second partitioning (see here and here; and hopefully methods for applying even more such subsequent partitionings will be discovered). There are also significant differences in the algorithms for constructing the two types of partitions, though we do not discuss these here.


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