19
$\begingroup$

Let $\Omega\subset \mathbb R^n$ be a compact domain of dimension $n$. Define the geometric median on $\Omega$ as the point $m_{\Omega}\in \mathbb R^n$ such that the integral $\int_{\Omega}|x-m_{\Omega}|dx$ attains its minimum.

Question Suppose that the domain $\Omega$ is a triangle $\Delta$ in $\mathbb R^2$. Is there a closed formula for the geometric median of $\Delta$?

Disclaimer. The name geometric median is taken from the Wikipedia article https://en.wikipedia.org/wiki/Geometric_median . There is huge amount of articles, in particular in statistics, probability, location theory, ect, that use this notion. It is clear as well that this notion has a lot of different names (some of which are given in the Wikipedia article). This notion is mainly applied to the case when $\Omega$ is a finite set. However, after an extensive search on Google, MathSciNet, Google Scholar, etc. I was not able to find any reasonable source treating the above question.

Improve this question
$\endgroup$
10
  • 5
    $\begingroup$ This is obviously a triangle center, so I tried searching for it in the encyclopedia of triangle centers (faculty.evansville.edu/ck6/encyclopedia/ETC.html) but no luck. The words "integral", "absolute", and "Weber" do not appear, "median" appears only with its triangle-geometry meaning (the line segment from a vertex to the opposite side's midpoint), and "Fermat" appears many times but none matching. The geometric median of the three triangle vertices is X(13) in ETC, but that's not what you're looking for. It would also be of interest to identify the geometric median of the edges. $\endgroup$
    – David Eppstein
    Oct 17, 2016 at 23:26
  • 1
    $\begingroup$ Minor comment: You write "the" point minimizing [the average distance to points in $\Omega$], but the geometric median need not be unique. For example, when the compact subset is a line segment with the middle cut out (e.g. $\Omega = [0,1/3] \cup [2/3,1]$), then there are many valid medians. I'm not sure under what conditions it is unique. Is the convexity of $\Omega$ sufficient? $\endgroup$
    – Adam Smith
    Oct 22, 2016 at 3:55
  • 3
    $\begingroup$ Clark Kimberling (the compiler of the encyclopedia mentioned in @DavidEppstein's comment) is on MO, although seemingly not very active. Maybe someone should notify him of this question (I imagine he's always interested in further triangle centers to add to his collection). $\endgroup$
    – Gro-Tsen
    Sep 12, 2018 at 9:29
  • 1
    $\begingroup$ @Gro-Tsen It's hard to contact people via mathoverflow, so I sent him an email. $\endgroup$
    – Oscar Cunningham
    Sep 12, 2018 at 15:18
  • 2
    $\begingroup$ Thanks for the email, Oscar. It appears that this point may not yet be in the Encyclopedia of Triangle Centers (ETC). Steps for determining whether it is a "new point" are given at faculty.evansville.edu/ck6/encyclopedia/Search_13_6_9.html . Better yet, if someone can figure out trilinear (or barycentyric) coordinates, this point can be added to ETC - unless it turns out to be one of the thousands of points already there. $\endgroup$
    – Clark Kimberling
    Sep 14, 2018 at 14:05

2 Answers 2

Reset to default
13
$\begingroup$

Not an answer, but this paper

Carlsson, John Gunnar, Fan Jia, and Ying Li. "An approximation algorithm for the continuous $k$-medians problem in a convex polygon." INFORMS Journal on Computing 26.2 (2013): 280-289. PDF download.

at least contains an explicit equation for the minimum integral with respect to the Fermat-Weber point (another name for the geometric median)

     

of a rectangle:

      Eq11
They also include some partial calculations for a right triangle. Their main result is an approximation algorithm, whose proof uses the above rectangle lemma.

Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ Dear Joseph, many thanks this paper! This is type of paper I was looking for. But now since I do want to learn at least if the median of the triangle is "known" I put some bounty to the question. $\endgroup$
    – aglearner
    Oct 18, 2016 at 0:22
  • 1
    $\begingroup$ My original citation has disappeared. I've tried to update appropriately. Clearly John Gunnar Carlsson is an expert on this topic, and should be consulted. $\endgroup$
    – Joseph O'Rourke
    Oct 18, 2016 at 1:25
  • 3
    $\begingroup$ High praise coming from you, @Joseph! I'll check with my coauthors. $\endgroup$
    – John Gunnar Carlsson
    Oct 18, 2016 at 2:53
  • $\begingroup$ Joseph, thanks for this idea, and John I would be grateful if you could add some information. $\endgroup$
    – aglearner
    Oct 18, 2016 at 11:22
6
$\begingroup$

Here is some evidence that there is no formula. I took a right isoceles triangle as the simplest non-trivial example. For the triangle on $(0,0), (1,-1), (1,1)$, the integral of distances to $(h,0)$ is

$$ \frac{h^3 - h^2s + 2s}{6} +\frac{\sqrt{2}\ h^3}{12}\log \dfrac{2-h+\sqrt{2}s}{(\sqrt{2}-1)h} +\frac{(1-h)^3}{3} \log\dfrac{1+s}{1-h} $$ where $s=\sqrt{2-2h+h^2}$. Numerically I find this minimized at $h \simeq 0.648863$. But any explicit formula for this median would have to minimize this function -- and more complicated functions with three more parameters for the general case.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ It appears that this point may not yet be in the Encyclopedia of Triangle Centers (ETC). Steps for determining whether it is a "new point" are given at faculty.evansville.edu/ck6/encyclopedia/Search_13_6_9.html . Better yet, if someone can figure out trilinear (or barycentyric) coordinates, this point can be added to ETC - unless it turns out to be one of the thousands of points already there. $\endgroup$
    – Clark Kimberling
    Sep 14, 2018 at 13:49
  • $\begingroup$ @ClarkKimberling, for the 13-6-9 triangle between $A=(107/13,8\sqrt{35}/13), B=(0,0),C=(13,0)$, I calculate that the geometric median is at $(7.22791291893318387541,1.33956720761444706019)$. So the first normalized trilinear coordinate is just that y-coordinate, which indeed qualifies this as a new entry! $\endgroup$
    – user44143
    Sep 15, 2018 at 18:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.