Relative Neighbor Graphs -------- -------- ------ Given a set of points in a plane, the associated rel- ative neighbor graph has an edge between two points P1 and P2 if and only if there is NO point P3 such that d(P3,P1) < d(P1,P2) and d(P3,P2) < d(P1,P2) where d(Px,Py) is the distance between Px and Py. You have been asked to compute the relative neighbor graph of a set of points. Input ----- For each test case, first a line containing just the test case name, and then lines containing the numbers N x[1] y[1] x[2] y[2] ... x[N] y[N] where there are N points and (x[i],y[i]) is the i'th point for 1 <= i <= N. On these lines numbers may be separated by any whitespace, including spaces, tabs, and line feeds. 3 <= N <= 100. The x,y coordinates may be any floating point numbers. Input ends with an end of file. Output ------ For each test case, first a line that is an exact copy of the test case name input line. Then one line for each edge in the relative neighbor graph, this line having the format i j to specify that there is an edge from (x[i],y[i]) to (x[j],y[j]). Here 1 <= i,j <= N. Do NOT output any edge more than once. The output may be printed as a graph or displayed in an X-window by the commands: print_graph display_graph provided the input and output of your program has been stored in the files relativeneighbor.in relativeneighbor.out and the test case name lines in these files do not have a digit as their first non-whitespace character. To see the sample output instead use the commands print_graph sample.in sample.test display_graph sample.in sample.test (here sample.test is the output for sample.in). Sample Input ------ ----- -- SAMPLE 1 -- 3 1 4 3 2 5 8 -- SAMPLE 2 -- 7 -1.01 0 -1.01 5 1.01 2.01 3.04 3.02 5.05 2.003 8.21 0 8.22 5.03 Sample Output ------ ------ -- SAMPLE 1 -- 1 2 1 3 -- SAMPLE 2 -- 1 3 2 3 3 4 4 5 5 6 5 7 File: relativeneighbor.txt Author: Bob Walton Date: Sun Oct 2 03:59:50 EDT 2011 The authors have placed this file in the public domain; they make no warranty and accept no liability for this file. RCS Info (may not be true date or author): $Author: walton $ $Date: 2011/10/02 08:05:34 $ $RCSfile: relativeneighbor.txt,v $ $Revision: 1.6 $