From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Computing  
WikiProject icon This article is within the scope of WikiProject Computing, a collaborative effort to improve the coverage of computers, computing, and information technology on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
 ???  This article has not yet received a rating on the project's quality scale.
 ???  This article has not yet received a rating on the project's importance scale.

Leaf, having no children?[edit]

Thanks to the editors who wrote this article. I think the end of the sentence, "A point region (PR) quadtree is a type of quadtree where each node must have exactly four children, or leaf, having no children." could be clearer, though. Could someone who knows the subject clarify what's meant here? Thanks! --Allen 02:54, 9 March 2006 (UTC)

The author probably meant: A point region quadtree is a type of quadtree where each node either has exactly four children, or none. A node with no children is called a leaf.
However, that would define a full or proper quadtree, rather than explain why or how such a tree is used as a region or point region quadtree. -- Gimmetrow 03:49, 4 May 2006 (UTC)

Is the Tree in the picture really a Point Tree?[edit]

"The point quadtree is an adaptation of a binary tree used to represent two dimensional point data. It shares the features of all quadtrees but is a true tree as the centre of a subdivision is always on a point." The tree in the picture looks rather like a Region Tree to me, but I'm not really sure... —Preceding unsigned comment added by (talk) 16:25, 6 February 2008 (UTC)

I believe you're correct. A point quadtree would only subdivide around an existing point in the dataset - the uniform divisions shown in the image sound more like a region tree according to the definitions in this article. I'd like someone else to double-check this though before we change it. Dcoetzee 19:48, 6 February 2008 (UTC)

Not strictly a tree?[edit]

Article states:

The region quadtree is not strictly a 'tree' - as the positions of subdivisions are independent of the data

This doesn't make any sense to me, and seems to need expanding. From my perspective, a 'tree' is a structure that consists of (quoting Tree (graph theory)) an undirected simple graph G that satisfies any of the following equivalent conditions:

  • G is connected and has no cycles.
  • G has no cycles, and a simple cycle is formed if any edge is added to G.
  • G is connected, but is not connected if any single edge is removed from G.
  • G is connected and the 3-vertex complete graph is not a minor of G.
  • Any two vertices in G can be connected by a unique simple path.

The region quadtree clearly meets this definition, so saying it isn't strictly a tree is apparently untrue. Am I missing something? (talk) 06:02, 25 September 2012 (UTC)

I agree with you. I've removed that sentence. —Bkell (talk) 16:34, 25 September 2012 (UTC)

What are the benefits?[edit]

This article doesn't explain what the benefits of storing information in this way are. For example, if I had to store coordinates of the points of rectangles, why would I use a quadtree rather than simply make a data structure that holds the coordinates and use an array of that structure? That would be faster and have less overhead. — Preceding unsigned comment added by (talk) 15:58, 14 September 2013 (UTC)

The regions may be ... rectangular, or may have arbitrary shapes[edit]

really? A citation would be nice! — Preceding unsigned comment added by (talk) 22:27, 21 November 2013 (UTC)