11 posts

## Off the wall question about data structures

Back to Forum: Coffeehouse
• Everybody is familiar with the standard list of data structures available to the C/C++ programmer: the linked list, hash tables, heaps, binary trees, etc. These are pretty much "two dimensional" if you draw their representations out on paper.  Are there any three-dimensional structures/libraries?  If so, what would be their use?  For instance, if you had user data linked (by pointers) in the shape of a cube, or something more sophisticated, is there any application for it?  Just curious.  I suppose you could technically call them "sophisticated" graphs, but they would exist for the sake of efficiency not just to make them 3-D.

• yup, arrays can have any of n dimensions.

• Actually the data structures you listed are more linear than two dimensional.  Two and three dimensional data structures can be used in gaming.  If you need to keep track of objects locations in multi-dimensional space and need an efficient method for searching three dimensional space, a sophisticated data structure can make searching that space much more efficient than searching a multidimensional array.  There can also be benefits in terms of size of the data structure.  Here's an example of a Quadtree used to store a two dimensional image.  The benefit in this case is size.
http://www.cs.ubc.ca/~pcarbo/cs251/welcome.html

I have used the quad tree in a class for searching two dimensional space.  It cuts a O(N) search time down to ~ O(logN).

• Maurits wrote:
yup, arrays can have any of n dimensions.

I know that...but I was thinking more in terms of implementing pointers...maybe I should put up a diagram instead.  I suppose this is a case of a solution in search of a problem.  I have no idea why I thought of this the other day.  Maybe it was too much E&J.

Basically, point A on the above drawing would contain pointers to B, E, and D (and so forth). I have googled around for this, but did not find a great deal.  I'm only using a cube as a very simple example, and it would not be of much use unless it was more sophisticated in shape (think, buckyball).

• Good point.  I had briefly thought about using them to track objects in multi-dimensional space and maybe even searching, and I'll have to check out the link you gave.  I suppose if RFIDs become the norm, these types of structures could aid in "finding" things faster (?).  I suppose I could always write up a library of such objects and "see what happens".

• BSP Tree (binary space partition) sorts objects in 3-D space to allow quick rendering.

• Minh wrote:
BSP Tree (binary space partition) sorts objects in 3-D space to allow quick rendering.

True...but a BSP tree is more or less a two-dimensional representation of 3-D space. I was thinking of a 3-D representation of...[insert idea here].

• In that article they mentioned an Octree as a related datastucture.  It is similar to the quadtree but everthing is split on another dimension (cutting four pieces into eight).  You could use this to represent objects in 3-d space.  It is a little easier than the BSP Tree since you aren't cutting polygons in half (I know...technically a square is a polygon).

• Consider a SQL table with n columns and i indices.  These indices are fundamentally lists of pointers which give you i different ways of quickly accessing an n-dimensional space... that is, a projection of an n-dimensional object onto an i-dimensional space (although in this case i could very well be greater than n, so perhaps the term "projection" is not mathematically apt)

• Maurits wrote:
Consider a SQL table with n columns and i indices.  These indices are fundamentally lists of pointers which give you i different ways of quickly accessing an n-dimensional space... that is, a projection of an n-dimensional object onto an i-dimensional space (although in this case i could very well be greater than n, so perhaps the term "projection" is not mathematically apt)

In a sense, sure (I work with SQL/databases half the day) but I guess I was thinking of something that could be used in programs in general, without having to use a full-blown database/SQL...something that could be bundled into a class library and could be templated.

• I also thought about going beyond a cube, to say, a diamond, a weblike-structure, or even crystal-like structures.  I even thought about a "Mobius strip".  I think the key would be to come up with some sort of reliable, quick-executing decision making process when traversing between nodes.  For example, with a binary tree, it is usually a pretty simple greater-than/less-than/go-to-the-left/go-to-the-right decision.  It would be nice to come up with something a bit quicker than a switch statement, but then it probably would not be as easily understood.

## Conversation locked

This conversation has been locked by the site admins. No new comments can be made.