The simplest algorithm is probably to check each point against all others while maintaining a list of the top 3. Since 3 is a small number, you can just maintain the top 3 in sorted order by insertion. For a bigger K top-K you'd use a max heap.
This can also be done in O(n log n) time by building the right data structure. A kd-tree would be O(n log n) on random data, for example. The simple algorithm would code this way: #include <stdio.h> #define N_PTS 1000 #define N_TOP 3 struct pt_s { int id; double x, y; } pts[N_PTS]; struct top_s { struct pt_s pt; double d2; } tops[N_TOP]; int n_top = 0; void clear() { n_top = 0; } void check_and_add(struct pt_s *hub, struct pt_s *sat) { double dx = hub->x - sat->x; double dy = hub->y - sat->y; double d2 = dx * dx + dy * dy; struct top_s top = { *sat, d2 }; if (n_top < 3) { // must insert somewhere int i = n_top++; while (i > 0 && d2 < tops[i - 1].d2) { tops[i] = tops[i - 1]; i--; } tops[i] = top; } else if (d2 < tops[N_TOP - 1].d2) { // may insert int i = N_TOP - 1; while (i > 0 && d2 < tops[i - 1].d2) { tops[i] = tops[i - 1]; --i; } tops[i] = top; } } void print(struct pt_s *hub) { int i; printf("%d %d", hub->id, tops[0].pt.id); for (i = 1; i < n_top; i++) printf(",%d", tops[i].pt.id); printf("\n"); } int main(void) { int n = 0, id, i, j; double x, y; while (n < N_PTS && scanf("%d%lf%lf", &id, &x, &y) == 3) { struct pt_s pt = { id, x, y }; pts[n++] = pt; } for (i = 0; i < n; i++) { clear(); for (j = 0; j < n; j++) if (j != i) check_and_add(pts + i, pts + j); print(pts + i); } return 0; } On Dec 21, 1:00 am, SAMMM <somnath.nit...@gmail.com> wrote: > You are given a list of points in the plane, write a program that > outputs each point along with the three other points that are closest > to it. These three points ordered by distance. > The order is less then O(n^2) . > > For example, given a set of points where each line is of the form: ID > x-coordinate y-coordinate > > 1 0.0 0.0 > 2 10.1 -10.1 > 3 -12.2 12.2 > 4 38.3 38.3 > 5 79.99 179.99 > > Your program should output: > > 1 2,3,4 > 2 1,3,4 > 3 1,2,4 > 4 1,2,3 > 5 4,3,1 -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.