@Gene, The algorithm which you have given below is O(n^2). I tried too and could not figure out anything better than this unless we go for data structures like kd-trees, as you already suggested.
Is it really the case that w/o using kd-tree, there is no better algorithm? On Fri, Dec 23, 2011 at 5:50 PM, Carol Smith <[email protected]>wrote: > @Gene - > Cool algorithm! I tried before in java and messed a little to get exact > output format. > Just wondering how you came up with simple yet working code? > > -Carol > > On Thu, Dec 22, 2011 at 6:08 PM, Gene <[email protected]> wrote: > >> 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 <[email protected]> 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 [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> >> > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- Regards, Piyush Kansal -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
