Talk:Klee's measure problem

Victor Klee

If this problem is notable, shouldn't at least a stub exist for the person who created it? -- Kicking222 02:58, 20 November 2006 (UTC)

Probably so, but as far as I can tell the problem is actually more notable than its proposer. I think a biography of Klee does exist as part of an introduction to a festschrift in his honor, but I don't have a copy of it, so don't have the materials to write an article on him at the moment. --Delirium 13:45, 20 November 2006 (UTC)

Fair enough. -- Kicking222 14:46, 20 November 2006 (UTC)

GA promotion

I've passed this article as a good article. The only possible quibble is the lack of inline citations, but the references are quite clear, and it's hard to imagine how inline cites would further improve the article, at least while it's not very long. Twinxor t 11:17, 21 November 2006 (UTC)

This seems not to meet the current GA criteria to me (see WP:WIAGA), and I'm not talking about inline citation (which, I would argue, is not the best way to source articles like this anyway). I am talking about issues such as 1b (lead section), and 3a (coverage). These should be fixed before someone decides to delist the article! Articles like this are generally rated as start class on the maths rating scheme. Note also, that the importance is a priority rating for the maths WikiProject, and is just an estimate: it is surely a higher priority for the computer science WikiProject. Geometry guy 16:26, 1 June 2007 (UTC)

Do you have any specific constructive criticism? What's wrong with the intro? What major points of the topic are not covered? --Delirium 03:15, 2 June 2007 (UTC)

I'm not GG, am somewhat familiar with the KMP (which is to say, don't tell me the answers to these questions, tell it in the article for the readers to see), and would put more work into the article myself rather than criticizing the work that's already been put into it if I only had the time right now, but: I can't get any sense from this article about what a solution to the KMP would be used for in computer graphics (though I can make up imaginary applications, e.g. determining the level of gray to make a pixel that contains complex subpixel-scale detail in a black-white image such as a rendered font) or in other applications. I don't know whether the algorithms mentioned here have been implemented and if so how to find the implementations. I can't get any sense of why the algorithms researchers who studied it thought it was an important problem to study; the title of Klee's original paper suggests that it might be related to complexity-theoretic concerns of trying to distinguish between linear-time problems and problems as hard as sorting (an important distinction in lower bounds for geometric algorithms) but there is nothing of that in the article. I get very little sense of how the solutions work: e.g. in the 2d case, the article mentions the plane sweep approach but says little about the fact that sweeping turns a static k-dimensional problem into a dynamic (k-1)-dimensional problem, nor gives any ideas what data structures are needed to maintain the lower-dimensional solution dynamically, and there's no mention of static-to-dynamic transformations like this as a more general technique in computational geometry. It says little about related work, for instance (to name a convenient example because I don't have to do a lot of search to find it rather than because it deserves any kind of prominent place in the article) my paper with Muthu that finds inconsistencies in internet packet filter rule sets using techniques inspired by the 3d KMP solution and with a similar n^{3/2} time bound. There's nothing about the obvious followup question of what might be known for similar area-of-union problems with non-rectangle input. All I get from the article is the bare bones of what the problem is, who solved it when, and an uninformative word or two about their solution techniques. Which is enough for a start rating, and I do consider the article a good start, but the subject has a lot more depth to it than that. I wouldn't want the GA rating to lead people to think that it's close to a complete article and doesn't need more work. —David Eppstein 04:26, 2 June 2007 (UTC)

GA review has caught up with this article. My comment above was intended as a friendly warning that this might happen. If necessary, I will do the honorable thing and delist this article myself, giving further comments on how it could be improved before it is nominated again for GA. Geometry guy 22:59, 3 June 2007 (UTC)

Good Article Review

Because of the conflict beetween a maths rating of start and GA status I've now listed this on Good Article Review. It lacks illustrations and discussion of related problems found in [1]. --Salix alba (talk) 20:50, 3 June 2007 (UTC)

I am now intending to delist this article. I will use the GA review format to comment: a preliminary version is below. I will try to improve the article a little before completing my commentary and delisting the article if that is still necessary. Geometry guy 16:25, 4 June 2007 (UTC)

GA review (see here for criteria)

1. It is reasonably well written.

   a (prose): b (MoS):

2. It is factually accurate and verifiable.

   a (references): b (citations to reliable sources): c (OR):

3. It is broad in its coverage.

   a (major aspects): b (focused):

4. It follows the neutral point of view policy.

   a (fair representation): b (all significant views):

5. It is stable.

   

6. It contains images, where possible, to illustrate the topic.

   a (tagged and captioned): b (lack of images does not in itself exclude GA): c (non-free images have fair use rationales):

7. Overall:

   a Pass/Fail:

The main reason this article doesn't currently meet the GA standard is that it needs a better coverage of the major aspects of the topic (Criterion 3a), such as how the algorithms work and why the problem is/was considered interesting. At the moment what little there is on this is mixed in with the history and I wasn't able to tease it out. I've added to the lead as far as I could, but it would need further improvement once the body of the article has more material. A reference for the optimality of the 2d algorithm and its use in computer graphics needs to be found. Finally, the article arguably needs an image, for example, a diagram of a union of rectangular ranges. Geometry guy 13:19, 5 June 2007 (UTC)

PS. As the template says, editors are of course free to renominate this article at GAC. Also if anyone thinks I have not handled the delisting process well, please let me know, or resubmit the article to GA/R. Thanks Geometry guy 13:27, 5 June 2007 (UTC)

Assessment comment

The comment(s) below were originally left at Talk:Klee's measure problem/Comments, and are posted here for posterity. Following several discussions in past years, these subpages are now deprecated. The comments may be irrelevant or outdated; if so, please feel free to remove this section.

This needs a proper lead, which explains to a non-expert reader what the problem is. It would also benefit from giving some more information about the algorithms discussed. An illustration would help too. Geometry guy 16:19, 1 June 2007 (UTC)

Last edited at 16:19, 1 June 2007 (UTC). Substituted at 02:16, 5 May 2016 (UTC)