Talk:Geometric median

DyK

Here's a permalink of that page. --Hirak 99 10:16, 2 April 2007 (UTC)

1-median of a graph or tree

Do we have a Wikipedia article that explains the median of a graph or tree (i.e., a node that minimises the average distance to all other nodes)? A similar concept is the graph center, which minimises the maximum distance, and facility location problems in graphs are also related. But I couldn't find a page that explicitly mentions the concept of a median of a graph. Median graph is something different. 1-center problem has a lot of relevant links, but they are all red.

Here are some references if someone is interested in writing more about medians of graphs:

• Hakimi, S. L. (1964), "Optimum locations of switching centers and the absolute centers and medians of a graph", Operations Research, 12 (3): 450–459, doi:10.1287/opre.12.3.450, JSTOR 168125.
• Zelinka, Bohdan (1968), "Medians and peripherians of trees", Archivum Mathematicum, 4 (2): 87–95.
• Goldman, A. J. (1971), "Optimal center location in simple networks", Transportation Science, 5 (2): 212–221, doi:10.1287/trsc.5.2.212.
• Alstrup, Stephen; Holm, Jacob; Thorup, Mikkel (2000), "Maintaining center and median in dynamic trees", Proceedings of the SWAT 2000, LNCS, vol. 1851, Springer, pp. 46–56, doi:10.1007/3-540-44985-X_6.
• Auletta, Vincenzo; Parente, Domenico; Persiano, Giuseppe (1996), "Dynamic and static algorithms for optimal placement of resources in a tree", Theoretical Computer Science, 165 (2): 441–461, doi:10.1016/0304-3975(96)00089-8.

One might also cover more general k-medians; see, e.g.:

• "Minimum k-median". A compendium of NP optimization problems.

I think there are at least enough references to show that the concept is notable enough to have some coverage in Wikipedia. But I am not sure if it is best to create a new article or extend an existing article (e.g., this page). — Miym (talk) 16:27, 11 October 2009 (UTC)

I think median graph is less different than you suggest: trees are median graphs, and median graphs are the graphs in which the 1-median of any three vertices is uniquely determined as meeting the obvious lower bound on average distance. Regardless, I think graph-theoretic medians are too separate a topic to be included in this article. —David Eppstein (talk) 16:46, 11 October 2009 (UTC)

Yes, you are right, but I do not think it makes sense to try to explain the concept of the 1-median of a graph in the median graph article, either. (But if we had an article on graph median, then it would certainly be a good idea to explain the connection between median graphs and graph medians, like you said.) — Miym (talk) 17:43, 11 October 2009 (UTC)

Wikilink

In the passage

Alfred Weber's name is associated with the more general Fermat–Weber problem due to a discussion of the problem in his 1909 book on facility location.

I changed Fermat-Weber problem to Fermat–Weber problem, but the addition of the wikilink was reverted with the edit summary

unexplained change of a self-reference to a reference to a different article

Actually the above-quoted sentence makes it clear the the Fermat-Weber problem is more general than the one in this article, so it's not a self-reference to this article but rather refers to a broader problem about which someone has recently created an article. So there ought to be a link to the relevant article. Duoduoduo (talk) 18:28, 29 July 2013 (UTC)

Okay if I restore the wikilink now? Duoduoduo (talk) 19:48, 29 July 2013 (UTC)

But this is a misreading of this sentence. The phrase "the more general problem" in this particular sentence refers to the geometric median, as a generalization of the Fermat point. Additionally, it is not true that "Fermat–Weber problem" unambiguously refers to the weighted version of the problem; rather, some sources use it to refer to the weighted problem (described in the article Weber problem) while other sources use it to refer to the unweighted problem (described here). I've rewritten the intro to clarify that the term is ambiguous. —David Eppstein (talk) 21:38, 29 July 2013 (UTC)

Robustness of the Geometric Median

The article states in "properties" that the geometric median has a breakdown point of 0.5, i.e., half of all points can be arbitrarily set, which will not affect the geometric median. This is IMHO wrong. Since the geometric median minimizes the distances to all points, dragging one point away from the others affects the geometric median linearly - which is better than for the average, which minimizes the squared distances instead and is thus affected by an outlier much stronger. Still, the assertion about the break point appears to be wrong.

Also, under "Special cases" it is said that the geometric median is equal to the Radon point for 4 coplanar and convex quadrilateral points. This is IMHO wrong as well. Taking one of the four points and moving it away from the others in the direction of its diagonal will affect the geometric median, but it does not affect the Radon point.

Any opinions on that? — Preceding unsigned comment added by Altzheimer (talk • contribs) 11:20, 29 March 2017 (UTC)

Clarity within the Definition section

Can someone explain why the formula for the

Geometric Median $={\underset {y\in \mathbb {R} ^{n}}{\operatorname {arg\,min} }}\sum _{i=1}^{m}\left\|x_{i}-y\right\|_{2}$

is terminated by underscore 2? If it is important then an explanation is needed. Otherwise it should be removed. Frank M. Jackson (talk) 14:16, 21 February 2018 (UTC)

The _2 means to use the Euclidean distance, i.e. the l2 norm. —David Eppstein (talk) 16:42, 21 February 2018 (UTC)

Not related to geometric mean

I find it very confusing that the title is "Geometric median", which immediately sounds like it is related to the geometric mean. Spatial median is a much better name, in my opinion.