help with sorting d-dimensional points

Hi, would like some help as how to approach the following problem:

I have a set of d-dimensional points (e.g (3,5,8,9,5) is a 5-dimensional point), and I need to sort the points on each of the coordinates.
The algorithm that I am trying to implement says that the resulting data structure is a multi-pointer list ((d-1)tuply threaded list), each node of which is threaded in each of the single pointer lists corresponding to the chosen coordinates.

This is a preprocessing stage of my implementation. I need this sorting of the points so that I could use it in a recursive divide and conquer approach to find the maximal elements among the points.

I want to use the STL to solve the problem.

Any ideas as how this preprocessing structure might look like?

AJ.

Am I correct in thinking:
You wish to store M N-dimensional points in M nodes, with each node containing N links. The overall structure of these nodes will constitute N linked lists, with each node being shared between all lists, and the individual lists being ordered according to the point's coordinate on one axis (with one axis assigned to each list).

If so, I suggest something similar:

Code:

---

struct CoordNode;
typedef vector<CoordNode> Node;

struct CoordNode {
  CoordNode(double val=0) :nextNode(NULL), coord(val) {}
  double coord;
  Node *nextNode;
};

---

Each point will be represented by a Node (typedef for vector<>). Its individual coordinates on each axis are represented by its vector elements. The links between nodes are formed at the coordinate level, since sorting is axis-specific.

hi hunter2,

tks for your answer, would you mind giving an example of how using your structure, I can insert the points, and sort them by each coordinate.

tks

Well, first, did I interpret the problem correctly? Your original post is pretty hard to follow.

hunter2,

what i am looking for, is somekind of list (or maybe vector?) where the points are sorted by coordinate 1, then another list with points sorted by coordinate 2, and so on. But somehow all the lists should be connected, so that when I delete an element from a certain list (e.g. one sorted by coord 1), it would also be deleted from all the other lists.

I suppose that's why they call it threaded, in the algorithm.

tks

I don't think STL has anything that will (significantly) help, other than using vectors to store point data. You'll need to implement your own data structure, similar to the one I described above.

>>would you mind giving an example of how using your structure, I can insert the points, and sort them by each coordinate.

I just made that data structure up, so I don't have any code for manipulating it. However, it should be fairly simple to adapt ordinary linked-list algorithms to the purpose.

For example, if you only consider one element of each node (i.e. node[0]), then the datastructure effectively becomes a singly-linked list, with node[0]->next being your 'next' pointer. So for example, when iterating along each list, you might have:

Code:

---

Node *xhead,*yhead,*zhead, *xcoord_next, *ycoord_next, *zcoord_next;
xcoord_next = (*xhead)[0].next;
ycoord_next = (*yhead)[1].next;
zcoord_next = (*zhead)[2].next;

xcoord_next = (*xcoord_next)[0].next;
ycoord_next = (*ycoord_next)[1].next;
zcoord_next = (*zcoord_next)[2].next;

etc.

---

The vector subscript tells you which axis you're dealing with. This is basically representing a point as an ordered triplet, except that we also bundled in a pointer, which allows us to link the individual coordinates into lists.

So you can see, once you insert a point at an arbitrary position in the structure, and re-form the links along each coordinate axis, it's a simple matter to run the structure through a slightly modified list-sorting algorithm N times, changing the vector subscript each time. The result: N sorted lists, using the same 'point' structures.

There are different ways to handle this depending on what the program will do. One possible solution is to create a class for the points. Then store them in a vector. Then you can sort the vector by coordinate 1 and look up stuff. Later, when you need to look up stuff based on coordinate 2, you can sort using a different sorting criterion and then search the vector again. This would not be a good solution if your program was constantly switching between different coordinates to use as the sorting criterion.

Another solution which is more like what you are suggesting is to allocate the memory for each point on the heap with new, then store pointers in different vectors or sets each sorted by a different coordinate. You'd want one master container so that the memory is freed at the end (or you'd want to use a shared_ptr). You could look up the value in each container if you need to delete it, and modifications will automatically be propagated since you are storing only one copy of the data.

You could also store the location in each of the extra containers in your point object, such as an iterator from the set container. So your point would have its point data plus an iterator for each set that is used to keep the data sorted by each different coordinate. This would make deletion easier, since you could just use the iterator directly.

The drawbacks of those two technique is that you are using a lot of memory, since each n-dimensional point will have n extra pointer values stored in addition to the point data itself, and for the last idea it would have n extra iterator copies in each point.

Finally, the best option might be something from boost. I don't remember the exact name (multi_index?), but they have a container that actually sorts by different indexes. You should look at boost.org to see if it will fit what you are doing.