I'm looking for a survey or a source for Cutting Lemma. I looked at Matusek's Discrete Geometry textbook, but it only proved Cutting Lemma for lines in $\mathbb{R}^2.$ I need to know the proof in $\mathbb{R}^d$ and other variations of Cutting Lemma.

Thanks in advance for any help!


1 Answer 1


Chazelle B, "Cuttings." Handbook of Data Structures and Applications (D. Mehta and S. Sahni, editors), chap. 25. 2005. PDF download.

Theorem 1.1. Given a set $H$ of $n$ hyperplanes in $\mathbb{R}^d$, for any $0 < \epsilon < 1$, there exists an $\epsilon$-cutting for $H$ of size $O(\epsilon^{-d})$, which is optimal. The cutting, together with the list of hyperplanes intersecting the interior of each simplex, can be found deterministically in $O(n \epsilon^{1-d})$ time.

  • $\begingroup$ Thank you very much. That's actually great. I was wondering if there are any other variations for Cutting Lemma? Like for Circles, Curves, ..? $\endgroup$
    – Kim
    Feb 11, 2018 at 3:20
  • $\begingroup$ @Megan: Matoušek mentions a cutting lemma for circles, using vertical decomposition. Matoušek, Jiří. Lectures on discrete geometry. Vol. 212. New York: Springer, 2002. p.72. $\endgroup$ Feb 11, 2018 at 12:09
  • $\begingroup$ @Megan: For curves: Sharir, Micha, and Joshua Zahl. "Cutting algebraic curves into pseudo-segments and applications." Journal of Combinatorial Theory, Series A 150 (2017): 1-35. arXiv version. $\endgroup$ Feb 11, 2018 at 13:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.