The Tree Stabbing Number is not Monotone

02/19/2020
by   Wolfgang Mulzer, et al.
0

Let P ⊆ℝ^2 be a set of points and T be a spanning tree of P. The stabbing number of T is the maximum number of intersections any line in the plane determines with the edges of T. The tree stabbing number of P is the minimum stabbing number of any spanning tree of P. We prove that the tree stabbing number is not a monotone parameter, i.e., there exist point sets P ⊊ P' such that P > P', answering a question by Eppstein <cit.>.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset