0
$\begingroup$

Given a set $L$ of size $n$ of lines in $\mathbb{R}^d$, find a point $x \in \mathbb{R}^d$ that minimizes: $$\sum\limits_{l\in L}\min\limits_{y\in l} {\lvert \lvert x-y \rvert\rvert}^2$$

I wrote a 1.5-page solution for this (given below in an overleaf link), by finding the point closest to $x$ on each line as a function of $x$, plugging the result in the above and deriving w.r.t $x$ and setting to equal to 0. However, I'm tasked with writing a solution "in one line, at most three". Is there a fundamentally different way to approach this problem that yields a "shorter" proof?

for reference's sake, link to my solution: https://www.overleaf.com/read/vtmfmstwrcpd

Improve this question
$\endgroup$
3
  • $\begingroup$ Are the lines assumed to be disjoint? $\endgroup$
    – Daniel Asimov
    Commented Jul 27, 2023 at 19:12
  • $\begingroup$ @DanielAsimov As the problem was stated to me, they are not. However, it can be safely assumed that they don't all intersect, that is, any intersection is not common to all of them (it is easy to verify that it's the case, and if the lines indeed all intersect the problem becomes easy). $\endgroup$
    – Ron Tubman
    Commented Jul 28, 2023 at 20:49
  • $\begingroup$ Let $a_\ell$ be an arbitrary point on $\ell$ and let $\pi_\ell$ be the projector to the line parallel to $\ell$ and passing through the origin. Then your sum is $\sum_\ell\|x-\pi_\ell x-(a_\ell-\pi_\ell a_\ell)\|^2$ which is of the kind $(Ax,x)-2(b,x)+c$ where $A$ is a quadratic symmetric matrix, $b$ is a vector, and $c$ is a number, so $x=A^{-1}b$, end of story. $\endgroup$
    – fedja
    Commented Jul 30, 2023 at 23:53

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .