5
$\begingroup$

Well it is, by drawing one and looking at it. But how about starting from the definition: the sum of distances to two points is constant. A more general question is to start with an $n$-ellipse (some examples here: What are curves (generalized ellipses) with more than two focal points called and how do they look like?).

Suppose $n$ points $\mathbf{p}_i$ in a two dimensional plane, define the general ellipse $E$ by $$ \sum_i^n d_i = D_0 \quad \mathrm{with} \quad d_i = |\mathbf{r}-\mathbf{p}_i|, \quad \mathbf{r} = (x,y) $$ Questions

  1. is $E$ convex?
  2. does $E$ enclose all points?
  3. if "no" to question 2, what's the value $D_0$ such that $E$ cross a point? And which point?
  4. To higher dimenions?

I know that's lots of questions, and I doubt there is existing knowledge on those questions. Could someone explain or point out some references?

Update: clarification on question 2. For the standard ellipse, when $D_0$ is very small, it does not exist. It come to existence firstly as a line segment connecting the two points---I still count this as "enclose". A point is not enclosed only if it totally falls outside of the shape.

$\endgroup$
5
  • $\begingroup$ Your definition of ellipse is a 1D curve, which cannot be convex in 2D. $\endgroup$
    – Kenny Lau
    May 6, 2017 at 2:06
  • $\begingroup$ @KennyLau No, because $r = (x,y)$ is 2D. $\endgroup$
    – Taozi
    May 6, 2017 at 2:12
  • 1
    $\begingroup$ $r=(x,y)$ is 2D, but the points satisfying your equation are 1D (the edge of the ellipse). $\endgroup$
    – Kenny Lau
    May 6, 2017 at 2:14
  • 1
    $\begingroup$ @KennyLau Although curves like the circle cannot be convex in $\Bbb R^2$ nonetheless they are often described as "convex curves". For the purposes of this question I would propose we agree that a Jordan curve whose interior is convex be regarded as a "convex curve". $\endgroup$ May 6, 2017 at 2:25
  • $\begingroup$ @LordSharktheUnknown Thank you for clarifying, only now do I understand the question. Your point it correct and let's follow that definition. $\endgroup$
    – Taozi
    May 6, 2017 at 2:45

2 Answers 2

3
$\begingroup$

The ellipse $E = \{\mathbf r : \sum_i d_i(\mathbf r) = D_0\}$ is generally not a convex set in $\mathbb R^n$, but one may ask whether the filled ellipse $F = \{\mathbf r : \sum_i d_i(\mathbf r) \le D_0\}$ is convex. In fact, it always is, because

  1. $d_i(\mathbf r)=\|\mathbf r - \mathbf p_i\|$ is a convex function of $\mathbf r$,
  2. the sum of convex functions is convex, and
  3. the sublevel set of a convex function is a convex set.

However, $F$ includes the point $\mathbf p_i$ if and only if $D_0 \ge \sum_j \|\mathbf p_i - \mathbf p_j\|$. Therefore, $F$ includes all points if and only if $D_0 \ge \max_i \sum_j \|\mathbf p_i - \mathbf p_j\|$. This property does not depend on the dimensionality of the space $\mathbb R^n$.

$\endgroup$
4
  • $\begingroup$ $F$ (and $E$) are non empty as long as $D_0$ is greater than the minimum of $\sum_i d_i$, and the point realising the minimum need not be one of the $\mathbb p_i$. So $F$ may very well contain none of these points. $\endgroup$
    – N.Bach
    May 6, 2017 at 9:07
  • $\begingroup$ @Rahul Thanks. In point 2, by "sum of convex function" do you also mean "sum of convex set"? Is this sum similar to the idea of Minkowski addition? $\endgroup$
    – Taozi
    May 6, 2017 at 17:23
  • $\begingroup$ @Rahul Think two filled circles, to me the union of them is impossible to be convex, so why the sum of them is convex? Any references? $\endgroup$
    – Taozi
    May 6, 2017 at 17:25
  • $\begingroup$ @Taozi: No, I mean the sum of convex functions. As I said, the function $d_i(\mathbf r)=\|\mathbf r - \mathbf p_i\|$ is a convex function of $\mathbf r$. Therefore, the sum of such functions $f(\mathbf r)=\sum_i d_i(\mathbf r)$ is also a convex function, and its sublevel set $\{\mathbf r : f(\mathbf r) \le D_0\}$ is a convex set. $\endgroup$
    – user856
    May 6, 2017 at 19:39
0
$\begingroup$

This is an attempt at proving that the set of all points on the interior and the boundary of the general ellipse $E$ is indeed a convex set.

Define the set $S$ as follows: $$S= \left\{\mathbf{r} :\sum_i^n d_i(\mathbf{r}) \leq D\right \},$$ where $d_i(\mathbf{r})=\mid \mathbf r - \mathbf{p_i} \ \mid$, $D$ is some constant, and $\{\mathbf{p_1}, \mathbf{p_2} , ..., \mathbf{p_n}\}$ are the $n$ foci of the general ellipse $E$.

Now, we wish to prove that the set $S$ is convex. Using the definition of convexity, for any pair of elements $\mathbf{r_1}, \mathbf{r_2} \in S$, we have to show that $\lambda \mathbf{r_1}+(1-\lambda)\mathbf{r_2}$ is also in $S, 0 \leq \lambda \leq 1$. This can be done by a simple application of the Triangle-Inequality, as follows:

$$\sum_i^n d_i\left(\lambda \mathbf{r_1}+(1-\lambda)\mathbf{r_2}\right)$$ $$=\sum_i^n \mid \lambda \mathbf{r_1}+(1-\lambda)\mathbf{r_2} - \mathbf{p_i} \ \mid$$ $$=\sum_i^n \mid \lambda \mathbf{r_1} - \lambda \mathbf{p_i} + (1-\lambda) \mathbf{r_2} \ -(1-\lambda) \mathbf{p_i} \ \mid$$ $$\leq \sum_i^n \lambda \mid \mathbf{r_1} - \mathbf{p_i} \ \mid + \ (1-\lambda) \mid \mathbf{r_2} - \mathbf{p_i} \ \mid$$ $$= \lambda \sum_i^n \mid \mathbf{r_1} - \mathbf{p_i} \ \mid + \ (1-\lambda) \sum_i^n \mid \mathbf{r_2} - \mathbf{p_i} \ \mid$$ $$\leq \lambda D + (1-\lambda) D$$ $$= D.$$

Where the second last inequality follows since $\mathbf{r_1}, \mathbf{r_2}$ are elements of $S$.

$\endgroup$

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.