Closest Pair Problem

[oleg9419]

I am trying to solve the closest pair problem.
I am having a problem with closest_pair function , first of all I want to
get the minimum distance of each X half but so far no success.
I hardly understand how to call these recursive functions with different parameters.

#include <float.h>
#include <math.h>
#include <stdio.h>

typedef struct Point2D
{
	double x;
	double y;
}Point2D;

inline double distance(Point2D* p1, Point2D* p2)
{
	return sqrt((p1->x - p2->x)*(p1->x - p2->x) + (p1->y - p2->y)*(p1->y - p2->y));
}


double brute_search(Point2D* p, const unsigned len)
{
	if(len < 2) return DBL_MAX;

	//find the min distance between 3 or 2 points
	double min_distance = DBL_MAX;

	for(int i = 0; i < len - 1; ++i)
	for(int j = i + 1; j < len; ++j)
	{
		double d = distance(&p[i], &p[j]);
		if(d < min_distance) min_distance = d;
	}

	return min_distance;
}


double closest_pair(Point2D* pX, Point2D* pY, const unsigned start, const unsigned end)
{
	const unsigned midd_x = (end ) / 2;

	//base case
	if((end - start) <= 3) return brute_search(pX, (end - start));

	double xr_min = closest_pair(pX, 0, start, midd_x);
	double xl_min = closest_pair(pX + midd_x, 0, midd_x , end);
	double x_min = xr_min < xl_min ? xr_min : xl_min;

	return x_min;

}

int main(void)
{

 	Point2D points[] = {
						  {.x = 3.0f, .y = 2.0f},
						  {.x = 3.0f, .y = 5.0f},
						  {.x = 8.0f, .y = 2.5f},
						  {.x = 8.1f, .y = 2.5f},
						  {.x = 8.5f, .y = 5.0f},
						  {.x = 8.7f, .y = 5.0f},
						  {.x = 8.9f, .y = 5.0f},
						  {.x = 8.9f, .y = 7.0f},
						};
	printf("%.3f is closest distance\n", closest_pair(points, 0,0,sizeof(points)/sizeof(points[0])));


return 0;
}

[ne555]

> but so far no success.
If you could provide a more descriptive error message, that would be great.


About the recursive call
There are several ways of passing a sub-array
(1) pass a pointer to the array, and the begin and end index of the subarray
(a) pass a pointer to the first element of the sub-array and its size
(\alpha) pass pointers to the begin and end elements of the sub-array

You are mixing (1) and (a)
(the most egregious example closest_pair(pX + midd_x, 0, midd_x , end);)


(not tested, please analyze it properly)

//If you decide to go with (1)
double closest_pair(Point2D* pX, Point2D* pY, const unsigned start, const unsigned end) //range [)
{
	//base case
	if((end - start) <= 3) return brute_search(pX+start, (end - start));


	const unsigned midd_x = start + (end-start) / 2;

	double xr_min = closest_pair(pX, 0, start, midd_x);
	double xl_min = closest_pair(pX, 0, midd_x, end);
	double x_min = std::min( xr_min, xl_min );

	return x_min;
}

//if you decide to go with (a)
double closest_pair(Point2D* pX, Point2D* pY, /*const unsigned start,*/ const unsigned /*end*/ size) //range [)
{
	//base case
	if(size <= 3) return brute_search(pX, size);


	const unsigned midd_x = size / 2;

	double xr_min = closest_pair(pX, 0, midd_x);
	double xl_min = closest_pair(pX+midd_x, 0, end-midd_x);
	double x_min = std::min( xr_min, xl_min );

	return x_min;
}