For any $6$ coplanar points



$$\left(x_{1}+y_{3},x_{2}+y_{2},x_{3}+y_{1}\right)$$ $$\left(x_{1}+y_{1},x_{2}+y_{3},x_{3}+y_{2}\right)$$ $$\left(x_{1}+y_{2},x_{2}+y_{3},x_{3}+y_{1}\right)$$ $$\left(x_{1}+y_{3},x_{2}+y_{1},x_{3}+y_{2}\right)$$

how to determine whether the convex hull of these $6$ points contains a point with one coordinate equal to $0$. What are the coordinates of that point?

  • $\begingroup$ Any helpful answers would be greatly appreciated! $\endgroup$ – Tonnia Aug 15 '13 at 9:36
  • $\begingroup$ If $k=x_1+x_2+x_3$ then the plane they lie on is $x+y+z=2k$. So if you set one coordinate to $0$ you get a line like $y+z=2k$ if you set $x=0$. The check on the convex hull part might be messy, since one would have to take convex linear sums of the six points using six coefficients which sum to 1 and then the hull is where all six coefficients are nonnegative. $\endgroup$ – coffeemath Aug 15 '13 at 13:12
  • $\begingroup$ The centroid of the hexagon is at $P=(x_1+t,x_2+t,x_3+t)$, where $t=(y_1+y_2+y_3)/3$ is the average of the $y$:s. The taxicab distance of each point to $P$ is the sum $\sum_{i=1}^3|y_i-t|$. I sorta feel that this can be used here, need to think a bit... $\endgroup$ – Jyrki Lahtonen Aug 15 '13 at 13:16

Label the points in the given order as $p_1,...,p_6$. Then the convex hull consists of the expressions $ap_1+bp_2+cp_3+dp_4+ep_5+fp_6$ where $a+b+c+d+e+f=1$ and each of $a,...,f$ is nonnegative. Suppose we set the first of the three coordinates to $0$. Since the sum of $a,...,f$ is $1$ this gives the equation $$x_1 + (a+d)y_1+(b+e)y_2+(c+f)y_3=0.\tag{1}$$ I'll just look at the case $x_1>0$ since otherwise it should be similar. EDIT: It turns out I never use $x_1>0$ so this restriction may be dropped.

Now note that except for the $x_1$ on the left of (1), the rest is just the convex hull (on the real line) of the three points $y_1,y_2,y_3$. Assuming without loss that $y_1\le y_2 \le y_3$, this hull is the closed interval $[y_1,y_3].$ Hence equation (1) has a solution iff $x_1+y_1 \le 0 \le x_1+y_3.$ Assuming this holds, we only need "use" the points $y_1,y_3$ to solve it, that is, we may set $b=e=0$ and continue to solve.

Then if $s=a+d,t=c+f$ we want to solve $y_1s+y_3t=-x$ where $s+t=1$ and $s,t\ge 0.$ Doing this gives $$s=\frac{x_1+y_3}{y_3-y_1}$$ and $t=1-s.$ Note that the numerator here is nonnegative because of our (necessary) assumption $x_1+y_1 \le 0 \le x_1+y_3,$ while the denominator is positive unless some of the $y_k$ coincide, a separate case that may have to be done. [EDIT: The only way $y_3-y_1=0$ is when all the $y_k$ are equal, say to $k$, in which case equation (1) becomes simply $x_1+k=0$, where the common values of the $y_k$ make that part of the sum equal to $k$. In this case no matter what choices are made for the coefficients $a,...,f$ there will be $x=0$ in the hull iff $x_1+k=0$, and if so all points of the hull have $x=0$] Also note that the numerator of $t=1-s$ is $-(x_1+y_1)$, again nonnegative because of the above necessary assumption. For specific values for $a,d,c,f$ we may choose any so that their sums are $s$ and $t$, e.g. $a=s,c=t,d=f=0.$


The six listed points are at $(x_1,x_2,x_3)+(y_{\sigma(1)},y_{\sigma(2)},y_{\sigma(3)})$, where $\sigma$ ranges over the group $S_3$ of all permutations of the set $\{1,2,3\}$. Thus all the points as well as their convex hull lies on the plane $x+y+z=\sum_{i=1}^3(x_i+y_i)$. This plane has a normal vector $\vec{n}=(1,1,1)$.

Write $t=(y_1+y_2+y_3)/3$, and $d_i=y_i-t$, $i=1,2,3.$ Without loss of generality (we are permuting the $y$:s anyway) we can assume that $y_1\le y_2\le y_3$, or equivalently that $d_1\le d_2\le d_3$. Furthermore, we note that by design $d_1+d_2+d_3=0$, so barring the case that they are all equal to zero, their signs differ. The centroid of the hexagon is at the point $$ P=(p_1,p_2,p_3)=(x_1+t,x_2+t,x_3+t). $$

Existence: Determining whether there are points on the hexagon such that their first coordinate vanishes is easy. The smalles value of the first coordinate on any of the points (shared by two points actually) is $x_1+y_1$ and the largest (again shared by two points) is $x_1+y_3$. By convexity, these are also the minimum (resp. maximum) value of the first coordinate on the hexagon. So if the numbers $x_1+y_1$ and $x_1+y_3$ share the same sign, then the first coordinate never vanishes on the hexagon. In all the other cases (obviouly including those where the minimum or maximum is equal to zero) there will be such points.

The existence of points, where the second (resp. the third) coordinate vanishes can similarly be decided by studying the signs of $x_2+y_1$ and $x_2+y_3$ (resp. $x_3+y_1$ and $x_3+y_3$).

Finding the points: It is easy to find one point with a vanishing coordinate (if the existence check reveals that it exists). For example, if $x_1+y_1<0<x_1+y_3$ we find one such point on the line segment connecting e.g. the vertices $(x_1+y_1,x_2+y_2,x_3+y_3)$ and $(x_1+y_3,x_2+y_2,x_3+y_1)$. Similarly for the other coordinates.

BUT, the set of points with a single coordinate vanishing forms a plane. It is possible that such a plane just grazes the hexagon at one of the vertices. More typically the plane and hexagon intersect along a line segment. In that case the end points of that line segment are on those edges of the hexagon whose end points have a change of sign in the coordinate of interest. Identifying those edges would be easy, if we were given the vertices of the hexagon in, say, counterclockwise order. An algorithm for doing that is probably well known in computer graphics. If you can't find anything I can try and cook up something. Essentially the remaining task is equivalent to 3D-clipping the hexagon (hopefully a useful buzzword).


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.