By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
446,302 Members | 1,453 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 446,302 IT Pros & Developers. It's quick & easy.

help with sorting d-dimensional points

P: 3
Hi, I 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.

what i am looking for, is a list 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. Is there anything around that can do that?

I want to use the STL to solve the problem. Any ideas as how this preprocessing structure might look like? and sort the points in each coordinate using maybe quicksort?

AJ.
Jun 25 '06 #1
Share this Question
Share on Google+
3 Replies


Banfa
Expert Mod 5K+
P: 8,916
I am not sure that it is possible to use the STL to solve this problem unless you actually have n separate lists. However you are asked to produce an n threaded list. I would interpret this as a single list with several different lists of sorting.

For a list of 5 dimensional coordinates you would need a structure similar to

Expand|Select|Wrap|Line Numbers
  1. struct coordinates {
  2.     int Coord[5];  // Orordinate
  3.     struct coordinates *next[5];   // Next pointers in 5 dimensions
  4. };
  5.  
  6. static struct coordinates *pListStart[5];
  7.  
Since you are talking about using STL I assume you are using C++, you need an N dimensional solution, so we can build our N dimensional solution using a template.

Something like

Expand|Select|Wrap|Line Numbers
  1. template <int N> struct coordinates {
  2.     int Coord[N];  // N dimensional Corordinate
  3.     struct coordinates *next[N];   // Next pointers in N dimensions
  4.  
  5.     static struct coordinates *start[N]; // Start pointers in N dimensions, this 
  6.                                          // assumes only having 1 instance of 
  7.                                          // a given dimension
  8. };
  9.  
You will need to add some methods to that structure to add and remove members from the list, if you like make it a class instead of a structure but there are few differences between the 2 (only 1 really).
Jun 27 '06 #2

100+
P: 293
D_C
How about using redirection arrays/vectors? I prefer vectors because it has all the memory management worked out.

Suppose you have input:
(3, 6, 0)
(2, 3, 5)
(1, 8, 9)

then have one vector for each coordinate, so after sorting,
vector<int> sortCoord1 = (0,1,2) // 3 > 2 > 1
vector<int> sortCoord2 = (2,0,1) // 8 > 6 > 3
vector<int> sortCoord3 = (2,1,0) // 9 > 5 > 0

then if you needed to remove (2,3,5), you could just delete 1 from each vector
and the result would be
(0,1)
(1,0)
(1,0)
assuming the others get shifted down.
Jun 27 '06 #3

Banfa
Expert Mod 5K+
P: 8,916
Hi D_C,

you ar trying to get the vector to do something it was not designed to do as well as introducing lots ofoverhead by having instances of multiple classes to do the job.

When you remove an entry you have to iterate through all the entries in your vectors to modify all the indexes so that they remain correct.

Using a single dedicated class, properly written to handle it's own memory correctly will result in clearer, faster and more maintainable code.

That is of course just my opinion :D

Cheers
Ben
Jun 27 '06 #4

Post your reply

Sign in to post your reply or Sign up for a free account.