Talk:Farthest-first traversal/GA1

GA Review

Article (edit | visual edit | history) · Article talk (edit | history) · Watch

Reviewer: RoySmith (talk · contribs) 19:59, 5 November 2021 (UTC)[reply]

"Every prefix of a farthest-first..." links to the wrong prefix. You probably want Substring#Prefix.
- Done —David Eppstein (talk) 19:47, 6 November 2021 (UTC)[reply]
link "traversal" to Graph traversal the first place it's used.
- But that's an article about graphs. Here there is no graph (until we get to the end of the Approximations section, and even then it's dubious to call it a graph traversal because those are about walks through the edges of a graph and here we're doing something else).
The caption for the first diagram says "The first five steps", but there's only 4 steps shown. I guess that depends on whether a vertex or an edge constitutes a "step", but I assume it's an edge.
- No, it's a point. There is no graph. It's a sequence of points. Changed caption to "the first five points" to be clearer. —David Eppstein (talk) 19:47, 6 November 2021 (UTC)[reply]
"no other set of equally many points can be spaced more than twice as widely" This needs some more explanation. Why can't they? Likewise for the following "less than half as far".
Oh, reading further, I see "By the pigeonhole principle, some two points of the optimal solution (whatever it is) must both be within distance r of the same point among these first k − 1 chosen points, and (by the triangle inequality) within distance 2r of each other." Is this the explanation I was seeking?
- Yes, the sentence you quoted from the lead was intended as a summary (not as a claim needing explanation) of the max-min facility dispersion paragraph, containing the explanation you quote. —David Eppstein (talk) 19:47, 6 November 2021 (UTC)[reply]
"All points of the whole metric space..." Is "whole metric space" a specific kind of metric space, or does "whole" just mean "the entire thing" in this context? If so, then I think this could be simplified to just "All points of the metric space...".
- Ok. It was intended as a contrast with the selected subset of the previous bullet point, but since you found it confusing I removed it. —David Eppstein (talk) 19:47, 6 November 2021 (UTC)[reply]
I'm not 100% sure about this, but in " seeks to minimize the maximum diameter of a cluster...", I think "diameter" should link to Diameter (graph theory), which in turn redirects to Distance (graph theory).
- Again, there is no graph. The first usage of "diameter" is linked to the geometric meaning of diameter. —David Eppstein (talk) 19:47, 6 November 2021 (UTC)[reply]
The paragraph starting "Later, the same sequence of points was popularized by Gonzalez (1985)..." is kind of big. Is there some logical place to break this into smaller paragraphs?
- Split into two smaller paragraphs. —David Eppstein (talk) 00:13, 7 November 2021 (UTC)[reply]
"are often incorrectly attributed to a different paper from the same time". The assertion of incorrect attribution needs to be backed up. Is that your evaluation (in which case it's WP:OR), or is there a WP:RS which says so?
- It is easy to source the fact that the Hochbaum-Shmoys paper is a different algorithm, not the farthest-first traversal, and it is also easy to (separately) find many prominent sources attributing the farthest-first traversal to Hochbaum-Shmoys, including the current version of a notable software package. I was trying to avoid pointing fingers, but in response to this query I have added both to the article. Are you really suggesting that to support the claim that these sources are making an incorrect attribution (certainly an encyclopedic thing to be claiming since we want to help people avoid repeating the same mistake) I need to find separate sources that point fingers at them and call them incorrect? In the process I also found a reference by Dyer and Frieze, from the same time as Gonzalez, describing the same algorithm (and saying that it is different from Hochbaum and Shmoys, with some detail on how it differs), which I chose as the source for the algorithms being different. —David Eppstein (talk) 00:58, 7 November 2021 (UTC)[reply]

@David Eppstein: That's all I can see. Overall, this is a nice article that does a good job of explaining a complicated topic. -- RoySmith (talk) 21:02, 5 November 2021 (UTC)[reply]

@RoySmith: all comments responded to; please take another look. —David Eppstein (talk) 00:58, 7 November 2021 (UTC)[reply]

Looks good. Just to tick all the boxes, I see no problems with the 6 GA criteria (Well written, Verifiable, Broad in coverage, Neutral, Stable, and Illustrated). Earwig didn't pick up any copy issues. -- RoySmith (talk) 04:08, 7 November 2021 (UTC)[reply]