
Disjoint Sets
I have a question, i have to create a disjointed set from a thousand points (x,y) and the equivalence relation is the distance between two points is less that a predefined number. I am a little lost on the making of the vector in the disjointed set any insight anyone thanks.

no i have multiple points (2,30),(4,67),(2,5) .. etc. i have to make a disjoined set and then union two points that have a distance between less than a predefined number. and i have to do it in nlogn not n squared.

I'm not sure exactly what you want but if you find the maximum
x and maximum y you can then divide the rectangle formed by
the points by drawing dxd lines horizontal and vertical. Then
to tell if any two points are d apart, it's only necessary
to check if they are in the same square or do some checks
for adjacent squares.

i dont understand ((x,y) is a point on the euclidean plane)
(2,3) and (2,4) are 1 distance apart from each other by using the distance formula of two points. I dont follow the rectancle thing.

It's hard to describe without a piece of paper but you can
do something like put (x, y) into A[x / d][y / d] into an 2d array of linked list. Then to union you would put (x2, y2) into the list
A[x2/d][y2 / d] and to do the find operation on (x, y)
it would be the list A[x / d][y / d] and then I think you
would have to check the adjacent lists who's distance
is in the bound.

A[x / d][y / d] what is d here

"distance between less than a predefined number."

no its suppose to be the distance between point 1 and point 2, that distance has to be less then a predefined number

i know its suppose to be like that but im trying to think of a way to do all possible combinations in less then Order N squared.

d is the number you are given to find points who's distance
is between. R be the relation (x, y) in R if dist(x, y) <= d.
Draw some points on a piece of paper. Then draw a grid
where each horizontal line and vertical line is d/sqrt(2). (I was
incorrect since you could have points on the corners).
Any points in the same square s are in R but it's also
possible to have points in s and in a adjacent square.

Nick i want tosay thank u for helping i will look over what u said and try to understand it

Off the top of your head, do you know how to implement a findpathcompression on a object instead of intergers. im have a problem
this is mine;
class Point
{
public:
Point(): x(0),y(0),value(1),index(0){}
Point(int xCoordinate, // x coordinate in (x,y)
int yCoordinate // y coordinate in (x,y)
): x(xCoordinate), y(yCoordinate),value(1),index(0) {}
Point(const Point & rhs): x(rhs.x), y(rhs.y), index(rhs.index),
value(rhs.value) {}//Copy Constructor
Point & operator =(const Point & rhs);
int x;
int y;
int index; //place label
int value; //value inside place label
};
Point& Point::operator =(const Point & rhs)
{
value = rhs.index;
return *this;
}
class DisjSets
{
public:
explicit DisjSets(vector<Point> & a);
Point & findPathcompression( Point & a );//returns the root point and performs
//path compression
void unionSets( Point & a, Point & b );
//private:
vector<Point> s;
};
Point & DisjSets::findPathcompression( Point & a )
{
if( a.value < 0 )
return a;
else
return s[a.index] = findPathcompression(s[a.value]);
}
My findPathcompression doesnt work can you see any problems, thanks alot

Code:
Point& Point:perator =(const Point & rhs)
{
value = rhs.index;
return *this;
}
Your copy constructor assigns value to rhs.index.
Code:
Point & DisjSets::findPathcompression( Point & a )
{
if( a.value < 0 )
return a;
else
return s[a.index] = findPathcompression(s[a.value]);
}
I would make an Point* field parent then all that would
be necessary I think is
Code:
Point* DisjSets::findPathcompression( Point & a )
{
if( a.parent == NULL)
return &a;
else
return a.parent = findPathcompression(a.parent);
}

CAN YOU EXPLAIN THIS AND EXACTLY WHAT ITS GOING ON IN THE FUNCTION. WHAT IS PARENT AND WHAT TYPE IS IT
i would make an Point* field parent then all that would
be necessary I think is
code:
Point* DisjSets::findPathcompression( Point & a )
{
if( a.parent == NULL)
return &a;
else
return a.parent = findPathcompression(a.parent);
}

This is a tree structure
so that each Point has a pointer to it's parent a Point*.
The parent of the root is null. What the find function
then does is returns the root node and assigns all other
node's parent along the path to the root. So what I did was say
if a's parent is null then were at the root and so we don't need to
adjust anymore nodes. Otherwise we set the parent
node to the result of calling the function on the parent.