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!


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 '18 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 '18 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 '18 at 13:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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