PreprintCC BY 4.0arXiv
Optimal discrepancy for triangles
Abstract
We prove that every n-point set in the plane has a two-coloring with discrepancy O(n1/4) for all triangles. This improves the previous bound O(n1/4√(log n)) and matches the classical lower bound.
Related
- A set of points with optimal L2 spherical cap discrepancy
- Asymptotically optimal bracketing covers for anchored boxes with applications to star discrepancy
- Minimax-Optimal Early Stopping for Continuous-Time SGD via the Discrepancy Principle
- Optimal Polynomial Tractability Exponents for the Inverse Star Discrepancy
- Surgery Exact Triangles in Involutive Heegaard Floer Homology
BibTeX
@misc{smirnov2026optimal,
title = {{Optimal discrepancy for triangles}},
author = {Gleb Smirnov},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.00375},
eprint = {2610.00375},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.00375},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Optimal discrepancy for triangles
AU - Gleb Smirnov
PY - 2026
DA - 2026/10/16
PB - arXiv
DO - 10.48550/arxiv.2610.00375
UR - https://arxiv.org/abs/2610.00375
AB - We prove that every n-point set in the plane has a two-coloring with discrepancy O(n^1/4) for all triangles. This improves the previous bound O(n^1/4√(log n)) and matches the classical lower bound.
ER -