Talk:Segment tree

From Wikipedia, the free encyclopedia

I'm willing to make this article a featured one. I don't mean as it is right now, of course. I don't know whether this is a naïve goal or not, but anyway I want to do it.

[edit] Pending

These are some pending issues or problems that should be corrected. I'm willing to do so for many of them; help is always welcome.

• Things to do to improve the content:
  • Include a drawing of an instance of a segment tree, to illustrate its structure. I was to include the one provided at the book I cite, but I'm afraid of copyright issues. I'm currently working on it.
  • Expand the History section.
  • It would be good to get the original Bentley's publication, to clarify whatever can be clarified, or to expand the article.

• Minor presentation fixes and pending tasks:
  • See if there are guidelines for writing algorithms or seudocode, and modify the article accordingly.
  • See who is Bentley, who discovered the tree, and possibly add links to an article about him. Seems to be Jon L. Bentley, the article for him is at Jon Bentley.
  • Is the Klee in the History section the same as Victor Klee? If so, perhaps a link could be added in that section.
  • References apparently broken. I'm using them as I read it in the documentation, but it looks like it doesn't work. It would be good if someone could repair them, and/or explain why they don't work.
  • Test and possibly correct all Wikilinks provided; particularly:
    • Union. Is is supposed to refer to the set operation.
  • See if there are some more categories to add to this article.
  • Add links to this article where suitable. It could be useful to look into a good article of some similar data structure to find out this. Some possible candidates could be:
    • Tree (data structure) (I think it has a list of tree-based structures).
    • Computational geometry.
    • Geographic information systems.
    • Bentley's article, if there is one.
  • See if references can be improved in any way, regarding readability. Perhaps they can be more sparse; given that all references are almost the same and there are many contiguous parts referenced. Do this taking into account the guidelines for citing.
  • Analize the possiblity of making some links of mentioned concepts. Particularly:
    • Cost. The article mentions time costs and memory costs.
    • Children. Attempting to open an article about child regarding trees redirects to the trees page. Maybe there is some heading within that article that could be linked with "Children".
    • Parent. If there is no article about this (as I guess), see if it can be linked to some heading within the Tree article.

• Scientific issues needing clarification:
  • Cost analysis questions: The costs provided for multi-dimensional versions of the tree don't look good to me. However, the paragraph is almost verbatim, and properly located and cited. I would agree with those costs, if they were assuming the use of an interval tree at the last level. Can it be what they ment in the book? It would be good to find more references to define all this.
  • Analyze if it is suitable to make Klee's rectangle problems a link to an article (although such an article still does not exist). What is Klee's rectangle problems?
  • My source claims Single points are treated themselves as intervals because the answer to a query is not necessarily the same at the interior of an elementary interval and its endpoints. Does it mean that the only reason why a node for each endpoint alone exist, is that the query can be open or closed?

Please, check or comment in this page on any fixed issues or modifications to the article. Alfredo J. Herrera Lago 19:11, 21 October 2007 (UTC)