17
$\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.

$\endgroup$
  • 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 '16 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 '16 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 '18 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 '18 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 '18 at 14:05
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.

| cite | improve this answer | |
$\endgroup$
  • 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 '16 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 '16 at 1:25
  • 3
    $\begingroup$ High praise coming from you, @Joseph! I'll check with my coauthors. $\endgroup$ – John Gunnar Carlsson Oct 18 '16 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 '16 at 11:22
5
$\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.

| cite | improve this answer | |
$\endgroup$
  • 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 '18 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$ – Matt F. Sep 15 '18 at 18:21

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.