6
$\begingroup$

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

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

Your Answer

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

Browse other questions tagged or ask your own question.