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).

enter image description here

  • $\begingroup$ Need the tripod have one leg pointing up? $\endgroup$
    – Matthew C
    Commented Dec 10, 2019 at 22:04
  • $\begingroup$ Nope.. the 2 adjacent rays need to be 120 degree apart... that's all $\endgroup$ Commented 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
    Commented Dec 11, 2019 at 0:20


Your Answer

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