Book contents
- Frontmatter
- Dedication
- Contents
- Introduction
- 1 Incidences and Classical Discrete Geometry
- 2 Basic Real Algebraic Geometry in R2
- 3 Polynomial Partitioning
- 4 Basic Real Algebraic Geometry in Rd
- 5 The Joints Problem and Degree Reduction
- 6 Polynomial Methods in Finite Fields
- 7 The Elekes–Sharir–Guth–Katz Framework
- 8 Constant-Degree Polynomial Partitioning and Incidences in C2
- 9 Lines in R3
- 10 Distinct Distances Variants
- 11 Incidences in Rd
- 12 Incidence Applications in Rd
- 13 Incidences in Spaces Over Finite Fields
- 14 Algebraic Families, Dimension Counting, and Ruled Surfaces
- Appendix Preliminaries
- References
- Index
3 - Polynomial Partitioning
Published online by Cambridge University Press: 17 March 2022
- Frontmatter
- Dedication
- Contents
- Introduction
- 1 Incidences and Classical Discrete Geometry
- 2 Basic Real Algebraic Geometry in R2
- 3 Polynomial Partitioning
- 4 Basic Real Algebraic Geometry in Rd
- 5 The Joints Problem and Degree Reduction
- 6 Polynomial Methods in Finite Fields
- 7 The Elekes–Sharir–Guth–Katz Framework
- 8 Constant-Degree Polynomial Partitioning and Incidences in C2
- 9 Lines in R3
- 10 Distinct Distances Variants
- 11 Incidences in Rd
- 12 Incidence Applications in Rd
- 13 Incidences in Spaces Over Finite Fields
- 14 Algebraic Families, Dimension Counting, and Ruled Surfaces
- Appendix Preliminaries
- References
- Index
Summary
In this chapter, we study our first new polynomial technique: polynomial partitioning. We first see the polynomial partitioning theorem. We use this theorem to derive an incidence bound between points and curves in the real plane. This bound generalizes the Szemerédi–Trotter theorem and the current best bound for the unit distances problem. In the second part of the chapter, we prove the polynomial partitioning theorem by using the ham sandwich theorem and Veronese maps. Finally, we use the point-curve incidence bound to obtain an upper bound for the number of lattice points that a curve can contain.
During the chapter we learn other important concepts, such as Warren’s theorem, incidence graphs, and various tricks for working with curves.
Keywords
- Type
- Chapter
- Information
- Polynomial Methods and Incidence Theory , pp. 35 - 50Publisher: Cambridge University PressPrint publication year: 2022