Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Consider a set of $n$ points on the plane with positions $\mathbf{p}_1,\dots,\mathbf{p}_n$, such that each point $i$ has at least one neighbor $j$ at a distance of no more than $\lambda$ away from it (i.e. $||\mathbf{p}_i - \mathbf{p}_j||\leq \lambda$).

The question is: how do you choose the positions of the points in order to maximize their second moment, defined as:

$ U = \sum \limits_{i} ||\mathbf{p}_i - \bar{\mathbf{p}}||^2, $

where $\bar{\mathbf{p}}=\sum \limits_{i} \mathbf{p}_i$ is the barycenter of the points.

Intuitively, I think that the points should be placed along a straight line spaced $\lambda$ from each other, but I am not sure how to (dis)prove this.

Thanks for any help.

share|improve this question
1  
Are you sure it's a minimization problem? If so, why don't you choose just $\mathbf{p}_i=\mathbf{0}$ for all $i\in\{1,\ldots,n\}$? –  triple_sec Aug 17 '13 at 4:45
1  
@triple_sec Of course, you're absolutely right. I'm sorry, it was a typo. The objective is to maximize! the second moment. –  MGA Aug 17 '13 at 5:36
2  
I just wonder according to the description of the problem, for n=4, we can just choose four points $p_1=(−x+\lambda/2,0)$,$p_2=(−x−\lambda/2,0)$, $p_3=(x+\lambda/2,0)$,$p_4=(x−\lambda/2,0)$ so that (1) $(p_1,p_2)$ and $(p_3,p_4)$ are mutually nearest neighbor, (2) $p_1$ and $p_3$ can be arbitrarily far away from each other, and (3) their mean is zero. Thus, $U\rightarrow +\infty$ and the objective does not have a finite maximum. –  Yuandong Aug 17 '13 at 12:44
2  
A better way to define the problem is: from $n$ points, construct a graph by connecting any 2 points whenever their distance is less than or equal to $\lambda$. Then maximize $U$ assuming the graph is connected. –  Yuandong Aug 17 '13 at 12:48
    
@Yuandong Brilliant! That actually answers the question if $n$ is a positive even integer and $n\geq4$. But what if $n$ is a positive odd integer? My intuitive idea coincides with MGA's: pick one point to be the origin and successively pick points $\lambda$ units away from the previous point in each direction. How can one rigorously prove this is optimal? –  triple_sec Aug 18 '13 at 7:51

2 Answers 2

up vote 1 down vote accepted

[From the comments I posted previously.]

The maximum of U is $+\infty$

For positive even $n\ge 2$, we can just choose $n/2$ points on the left/right side, respectively:

$$\mathbf{p}_i=(−x+\lambda i,0) \quad \forall 1\le i \le n/2$$ $$\mathbf{p}_i=(x-\lambda i,0) \quad \forall n/2+1\le i \le n$$

Then every point has at least one neighbor whose distance is $\le\lambda$ and their mean is zero. However, $U \rightarrow+\infty$ when $x\rightarrow +\infty$.

For positive odd $n\ge 5$, from @triple_sec: let $m=(n+1)/2$ and

$$\mathbf{p}_i=(x+(i−1)\lambda,0)$$ for $i\in\{1,\ldots,m\}$ and

$$\mathbf{p}_i=(−y−(i−m−1)\lambda,0)$$ for $i\in\{m+1,…,n\}$, where $y=\lambda+\frac{n+1}{n−1}x$. Then, $\sum_{i=1}^n \mathbf{p}_i=0$, whereas the objective function can be shown to be

$$\frac{n(n+1)}{n−1}\left(x^2+\frac{n−1}{2}\lambda x + \frac{(n−1)^2}{12}\lambda^2\right)$$

which diverges to infinity as $x\rightarrow +\infty$.

share|improve this answer
    
@Yuadong Thanks a lot. Fancy having a pop at the other case? ;-p –  MGA Aug 19 '13 at 18:33

Here is a rough idea. Since the objective and the constraint are invariant to simultaneous translation and rotation of all points, you can assume wlog that $\overline{\mathbf{p}}=\mathbf{0}$ and that $\mathbf{p}_n=(x_n,0)$, for some $x_n\in\mathbb{R}$. Using these constraints, you can express the coordinates of the points as follows: $$\mathbf{p}_1=\left(\begin{array}{c}x_1\\y_1\end{array}\right)\quad\cdots\quad\mathbf{p}_{n-2}=\left(\begin{array}{c}x_{n-2}\\y_{n-2}\end{array}\right)\quad\mathbf{p}_{n-1}=\left(\begin{array}{c}x_{n-1}\\-(y_1+\cdots+y_{n-2})\end{array}\right)\quad\mathbf{p}_{n}=\left(\begin{array}{c}-(x_1+\cdots+x_{n-1})\\0\end{array}\right).$$

In simplifying the last two vectors, I exploited the requirement that the points' barycenter be the origin. Now, the problem reduces to choosing $((x_i)_{i=1}^{n-1},(y_i)_{i=1}^{n-2})$, that is, there are $2n-3$ free variables. The objective is to maximize the sum of squares of these numbers: $$\sum_{i=1}^{n-2}(x_i^2+y_i^2)+x_{n-1}^2+(y_1+\cdots+y_{n-2})^2+(x_1+\cdots+x_{n-1})^2$$

subject to the constraint that for each $i\in\{1,\ldots,n\}$, there must exist some $j\in\{1,\ldots,n\}$, $j\neq i$, such that $(x_i-x_j)^2+(y_i-y_j)^2\leq\lambda^2$. Here, $y_{n-1}=-(y_1+\cdots+y_{n-2})$, $x_n=-(x_1+\cdots+x_{n-1})$, and $y_n=0$.

Again wlog, you can assume that $\mathbf{p}_1$ is $\lambda$-close to $\mathbf{p}_2$: $$(x_1-x_2)^2+(y_1-y_2)^2\leq\lambda^2.$$ This will be one of the constraints. Therefore, you need not worry about finding close points for $\mathbf{p}_1$ and $\mathbf{p}_2$ anymore. The real headache occurs when you think about how to find near neighbors for the other points. There are at most $(n-2)n$ ways to find near neighbors for the points $\{\mathbf{p}_k\}_{k=3}^n$ ($n$ possible near neighbors for $n-2$ points). For each of these configurations, you can write the set of constraints imposing $\lambda$-closeness explicitly and solve the resulting constrained maximization problem. Then, out of the $n(n-2)$ possible constrained maximization problems, pick out the one that yields the greatest value for the objective. This could be done using a computer algorithm, either (i) solving the $n(n-2)$ Kuhn–Tucker problems symbolically; or (ii) for a given value of $\lambda$, solve the $n(n-2)$ problems numerically to see whether your conjecture that the points must lie on a straight line is correct (I lean to believing it is).

I'm pretty sure there exists a more efficient and smart algorithm, but this is what I could come up with so far. It seems to be a difficult problem (or I'm not proficient enough at convex optimization—the two possibilities are very likely not to be mutually exclusive).

share|improve this answer
    
For $n=2$, this algorithm gives $$\mathbf{p}_1=-\left(\begin{array}{c}\dfrac{\lambda}{2}\\0\end{array}\right) \quad \mathbf{p}_2=\left(\begin{array}{c}\dfrac{\lambda}{2}\\0\end{array}\right)$$ as the optimal solution (modulo translations and rotations) and for $n=3$, $$\mathbf{p}_1=-\left(\begin{array}{c}\lambda\\0\end{array}\right)\quad\mathbf{p}‌​_2=\left(\begin{array}{c}0\\0\end{array}\right) \quad \mathbf{p}_3=\left(\begin{array}{c}\lambda\\0\end{array}\right).$$ Indeed, they are on a straight line, each pair being separated by a distance of $\lambda$. –  triple_sec Aug 17 '13 at 9:33

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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