Simple Proofs of Classical Theorems in Discrete Geometry via the Guth-Katz Polynomial Partitioning Technique

Haim Kaplan, Jirí Matousek, Micha SharirDiscret. Comput. Geom 2012 · DOI · OpenReview

TL;DR

This paper presents new, simpler proofs for fundamental theorems in discrete geometry, namely the Szemerédi-Trotter theorem on point-line incidences and the existence of low-crossing-number spanning trees. The authors leverage the powerful polynomial partitioning technique introduced by Guth and Katz, offering an accessible exposition suitable for teaching and research.

What Problem Does This Paper Address?

Discrete geometry deals with the combinatorial properties of geometric objects. Two classic problems that have seen significant theoretical development are:

  1. The Szemerédi-Trotter Theorem: This theorem bounds the number of incidences (a point lying on a line) between a set of points and a set of lines in a plane. While established in the 1980s, finding elegant and elementary proofs has been an ongoing pursuit.
  2. Low-Crossing-Number Spanning Trees: Given a set of points, a geometric spanning tree connects them with straight line segments. The "crossing number" measures how many edges a line can intersect. Finding spanning trees with a small crossing number is important for various algorithmic applications.

The authors aim to provide new, simpler, and more accessible proofs for these theorems by employing a recently developed technique.

Methods

The core of this paper is the application of the Guth-Katz polynomial partitioning technique. This technique, introduced by Guth and Katz in their work on the Erdős distinct distances problem, offers a novel way to decompose a finite set of points in $R^d$.

Here's a breakdown of the method:

  • Polynomial Partitioning: Given a set of $n$ points $P$ in the plane and a parameter $r$, they construct a polynomial $f$ of low degree (specifically, $O(\sqrt{r})$). The zero set of this polynomial, $Z(f)$, partitions the plane into "cells." The key property is that each cell contains at most $n/r$ points from $P$. This is achieved using the polynomial ham-sandwich theorem, which guarantees the existence of such a polynomial.
  • Applying to Theorems:
    • Szemerédi-Trotter: The plane is partitioned by $Z(f)$. Lines are then analyzed based on whether they intersect $Z(f)$ or lie within the cells. This decomposition allows for a more manageable counting of incidences.
  • Spanning Trees: The technique is used to construct an "arcwise connected set" $X$ containing the points, with a low crossing number. This set $X$ is then transformed into a geometric spanning tree with a low crossing number. This involves recursively applying the partitioning technique and carefully managing the number of connected components.
  • Generalization to Higher Dimensions: The paper also extends the spanning tree result to $R^d$, adapting the polynomial partitioning and related lemmas to higher dimensions.

The proofs are designed to be self-contained and expository, relying on standard results from algebraic geometry (like Bézout's theorem) and basic facts about polynomials.

Datasets

Not discussed in the paper. The paper deals with theoretical results on abstract sets of points and lines, not empirical evaluation on specific datasets.

Key Insights and Ideas

  • Elegance of Polynomial Partitioning: The Guth-Katz technique provides a surprisingly powerful and versatile tool for tackling classical geometric problems. Its ability to decompose point sets into manageable subsets with controlled properties is a major advantage.
  • Unified Approach: The paper demonstrates how a single technique can yield simpler proofs for seemingly disparate problems in discrete geometry, highlighting the underlying combinatorial and algebraic structures.
  • Teaching Potential: The authors emphasize the expository nature of their proofs, suggesting that this approach is well-suited for teaching advanced topics in discrete geometry.
  • Bridging Algebra and Geometry: The method elegantly bridges algebraic concepts (polynomials, zero sets) with geometric problems (incidences, spanning trees).
  • Higher-Dimensional Challenges: Extending the planar proofs to higher dimensions reveals new subtleties, particularly when many points lie on the zero set of the partitioning polynomial, requiring perturbation arguments.

Key Results

  • New Proof of Szemerédi-Trotter Theorem: The paper provides a new proof of the bound $I(P, L) = O(m^{2/3}n^{2/3} + m + n)$ for the number of incidences between $m$ points and $n$ lines in the plane.
  • New Proof of Low-Crossing-Number Spanning Trees: A new proof is given for the existence of a geometric spanning tree with $O(\sqrt{n})$ crossing number for $n$ points in the plane.
  • Higher-Dimensional Generalization: The paper proves that for $n$ points in $R^d$, there exists a geometric spanning tree with crossing number $O(n^{1-1/d})$ with respect to hyperplanes.
  • Simplified Proof for Point-Curve Incidences: A version of Theorem 1.2 on incidences between points and algebraic curves is also proven more simply.

Limitations and Future Work

  • Algebraic Nature: The authors note that the algebraic approach has limitations. It is well-suited for algebraic or semi-algebraic objects but may not easily extend to more general settings, such as incidences with pseudolines, where combinatorial techniques might be more powerful.
  • Algorithmic Complexity: While the proofs are conceptually simple, the algorithmic complexity of constructing the partitioning polynomials and related structures is not fully clear and might be a bottleneck for practical implementations.
  • Higher Dimensions and Zero Sets: The extension to higher dimensions highlights a challenge when many points lie on the zero set of the partitioning polynomial. While a perturbation argument is used for spanning trees, handling this situation for incidence problems requires different techniques.
  • Future Work: The authors suggest investigating alternative approaches for handling points on the zero set in incidence problems and exploring further applications of the Guth-Katz technique to other "hard Erdős problems" in discrete geometry. They also ponder the possibility of an abstract version of polynomial partitions that could combine the advantages of algebraic and combinatorial methods.

Summary updated

Abstract

Recently Guth and Katz ( arXiv:1011.4105 , 2010) invented, as a step in their nearly complete solution of Erdős’s distinct distances problem, a new method for partitioning finite point sets in ℝ d , based on the Stone–Tukey polynomial ham-sandwich theorem. We apply this method to obtain new and simple proofs of two well known results: the Szemerédi–Trotter theorem on incidences of points and lines, and the existence of spanning trees with low crossing numbers. Since we consider these proofs particularly suitable for teaching, we aim at self-contained, expository treatment. We also mention some generalizations and extensions, such as the Pach–Sharir bound on the number of incidences with algebraic curves of bounded degree.
BibTeX
@article{kaplan2012simple,
  author = {Haim Kaplan and Jirí Matousek and Micha Sharir},
  title = {{Simple Proofs of Classical Theorems in Discrete Geometry via the Guth-Katz Polynomial Partitioning Technique}},
  journal = {Discret. Comput. Geom.},
  year = {2012},
  doi = {10.1007/s00454-012-9443-3},
}
Figure