2
$\begingroup$

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!

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\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
    Commented 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$
    – Joseph O'Rourke
    Commented 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$
    – Joseph O'Rourke
    Commented Feb 11, 2018 at 13:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .