I would appreciate if anyone could help me with the following problem:
Given a set of 3n points in the plane with n> 0, is it possible to find a placement of a tripod such that each region contains at most n of the points?
If it is possible, then can we prove that a valid placement always exists?
If it is not possible, then can anyone provide me a set of 3n points (with n> 0) and a tripod T and prove that there is no placement of T which has the required properties.
Here, I am considering the points in general position, i.e. no three points are collinear. Also by my understanding, tripod is a point (say p) with three rays emanating from p such that the angle between two consecutive rays is 2π/3 (120 degree). Also the tripod can partition the plane into three regions(i.e. cones).
-
$\begingroup$ Need the tripod have one leg pointing up? $\endgroup$Matthew C– Matthew C2019年12月10日 22:04:04 +00:00Commented Dec 10, 2019 at 22:04
-
$\begingroup$ Nope.. the 2 adjacent rays need to be 120 degree apart... that's all $\endgroup$AlgorithmUser785– AlgorithmUser7852019年12月10日 23:43:35 +00:00Commented Dec 10, 2019 at 23:43
-
1$\begingroup$ ok. My guess is that this is possible. It reminds me of a discrete version of the ham sandwich theorem (en.wikipedia.org/wiki/Ham_sandwich_theorem) and the constraints seem to give just enough (3) degrees of freedom to make it work $\endgroup$Matthew C– Matthew C2019年12月11日 00:20:21 +00:00Commented Dec 11, 2019 at 0:20