2

A convex combination of two vertices $p = ( a, b )$ and $q = ( c, d )$ is any point $r = ( e, f )$ such that for some $x$ in range $0 \le x \le 1$, $e = xa + ( 1 - x )c$ and $f = xb + ( 1 - x )d$. Intuitively, $r$ is any point that is on the line passing through $p$ and $q$ and is on or between $p$ and $q$ on the line.

Is there any intuition about why this combination is always going to lie on the line from $p$ to $q$?

The question is different from If $0 \le a \le 1$, then show that $xa+(1−a)y$ will always lie between $x$ and $y$. as if e lies between a and c and f lies between b and d it does not gaurantee that it will be on the line. For example let $p$ be (1,2) and q be (3,4) and r be (2.5,3). It follows the above constraint but yet it does not lie on the line.

Proof

That said, can now somebody give intuitive proof of this now ?

Community
  • 1
Abhinav Garg
  • 139
  • 1
    Try setting up an equation for the line PQ. If the convex combination lies on the line, it must satisfy this equation. Try proving that it always does. – adrianN Jun 14 '16 at 15:07
  • @adrianN I followed the steps, and I have successfully proved it. Thanks a lot. But I am still not able to find the intuition behind the formula. Can you point me out in that direction also ? – Abhinav Garg Jun 14 '16 at 16:18
  • As to your original question, here's a hint. Try to write out an equation for the points on the line from $p$ to $q$. Does the point $(e,f)$ satisfy that equation? 2. You say in your comment to adrianN that you "have successfully proved it" but don't understand the intuition. If that's so, please edit the question to show the proof you came up with, and edit the question to ask for the intuition rather than asking for a proof. 3. Have you tried working through a few examples? Sometimes that helps gain intuition.
    • – D.W. Jun 14 '16 at 18:14
  • @D.W. I already did all as you suggested. Still no intuition :( If you have one then please tell. As of why CS, I saw it while reading CLRS – Abhinav Garg Jun 14 '16 at 19:32
  • @AbhinavGarg, my suggestion is to show that in the question. You can show your proof in the question. You can also pick an example, draw a picture on the 2D plane showing where all the points are and show the picture in the question -- and then see if you can tell us anything about why the result is counter-intuitive or surprising for you. I think with an example and a picture it might become clearer, especially if you visualize what happens as $x$ starts very small (just a bit larger than 0) and gets larger, sweeping from 0 to 1. – D.W. Jun 14 '16 at 19:36
  • The formula is more intuitive if written as $\mathbf r = \mathbf q + x(\mathbf p - \mathbf q)$. Here $(\mathbf p - \mathbf q)$ is the vector from $\mathbf q$ to $\mathbf p$. You start from $\mathbf q$ and move a fraction $x$ of the way along the vector towards $\mathbf p$. –  Jun 14 '16 at 19:37
  • @D.W. I showed the proof in the question. It is based on slope of line. Click on word Proof and tell me your views about it. This is suprising as I am not able to understand why doesn't the point drifts apart from the line, it stays on the line. – Abhinav Garg Jun 14 '16 at 19:49
  • That wasn't obvious. We want questions to be self-contained, so people don't have to click on other links to see what you've done. It'd be clearer if that image was embedded inline, not a link. Better yet, please write up the proof carefully using LaTex -- don't just embed an image. Also, as I commented before, if you already know a proof, please edit the question to show the proof you came up with, and edit the question to ask for the intuition rather than asking for a proof. It's confusing to have a question where you ask "Is there any proof..?" when you already know the proof. – D.W. Jun 14 '16 at 20:02