(*^
::[ Information =
"This is a Mathematica Notebook file. It contains ASCII text, and can be
transferred by email, ftp, or other text-file transfer utility. It should
be read or edited using a copy of Mathematica or MathReader. If you
received this as email, use your mail application or copy/paste to save
everything from the line containing (*^ down to the line containing ^*)
into a plain text file. On some systems you may have to give the file a
name ending with ".ma" to allow Mathematica to recognize it as a Notebook.
The line below identifies what version of Mathematica created this file,
but it can be opened using any other version as well.";
FrontEndVersion = "X Window System Mathematica Notebook Front End Version 2.2";
X11StandardFontEncoding;
fontset = title, inactive, noPageBreakBelow, noPageBreakInGroup, nohscroll, preserveAspect, groupLikeTitle, center, M7, bold, e8, 24, fontName, "times";
fontset = subtitle, inactive, noPageBreakBelow, noPageBreakInGroup, nohscroll, preserveAspect, groupLikeTitle, center, M7, bold, e6, 18, fontName, "times";
fontset = subsubtitle, inactive, noPageBreakBelow, noPageBreakInGroup, nohscroll, preserveAspect, groupLikeTitle, center, M7, italic, e6, 14, fontName, "times";
fontset = section, inactive, noPageBreakBelow, nohscroll, preserveAspect, groupLikeSection, grayBox, M22, bold, a20, 18, fontName, "times";
fontset = subsection, inactive, noPageBreakBelow, nohscroll, preserveAspect, groupLikeSection, blackBox, M19, bold, a15, 14, fontName, "times";
fontset = subsubsection, inactive, noPageBreakBelow, nohscroll, preserveAspect, groupLikeSection, whiteBox, M18, bold, a12, 12, fontName, "times";
fontset = text, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, 12, fontName, "times";
fontset = smalltext, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, 10, fontName, "times";
fontset = input, noPageBreakInGroup, nowordwrap, preserveAspect, groupLikeInput, M42, N23, bold, 12, fontName, "courier";
fontset = output, output, inactive, noPageBreakInGroup, nowordwrap, preserveAspect, groupLikeOutput, M42, N23, L-5, 12, fontName, "courier";
fontset = message, inactive, noPageBreakInGroup, nowordwrap, preserveAspect, groupLikeOutput, M42, N23, 12, fontName, "courier";
fontset = print, inactive, noPageBreakInGroup, nowordwrap, preserveAspect, groupLikeOutput, M42, N23, 12, fontName, "courier";
fontset = info, inactive, noPageBreakInGroup, nowordwrap, preserveAspect, groupLikeOutput, M42, N23, 12, fontName, "courier";
fontset = postscript, PostScript, formatAsPostScript, output, inactive, noPageBreakInGroup, nowordwrap, preserveAspect, groupLikeGraphics, M7, l34, w282, h287, 12, fontName, "courier";
fontset = name, inactive, noPageBreakInGroup, nohscroll, preserveAspect, M7, italic, B65535, 10, fontName, "times";
fontset = header, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, italic, 12, fontName, "times";
fontset = leftheader, 12, fontName, "times";
fontset = footer, inactive, nohscroll, noKeepOnOnePage, preserveAspect, center, M7, italic, 12, fontName, "times";
fontset = leftfooter, 12, fontName, "times";
fontset = help, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, 12, fontName, "times";
fontset = clipboard, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, 12, fontName, "times";
fontset = completions, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, 12, fontName, "courier";
fontset = special1, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, 12, fontName, "times";
fontset = special2, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, 12, fontName, "times";
fontset = special3, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, 12, fontName, "times";
fontset = special4, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, 12, fontName, "times";
fontset = special5, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, 12, fontName, "times";paletteColors = 128; showRuler; automaticGrouping; currentKernel;
]
:[font = title; inactive; preserveAspect; startGroup]
Nearest Neighbours Using k-d Trees
:[font = text; inactive; preserveAspect]
This program calculates the set of nearest neighbours for each point in the input data set using the algorithm descibed in[1]. A k-d tree is built from the data set in O(n log n) time which allows the computation of the nearest neighbours for a particular query point in O(log n) time.
:[font = section; inactive; Cclosed; preserveAspect; startGroup]
Reading In The Data
:[font = text; inactive; preserveAspect]
First the preliminaries - reading the data file. The following assumes a file format of
" ... , ... ,", which allows multiple inputs and outputs:
:[font = input; preserveAspect]
filename = "Math/Gamma/hen100.asc";
:[font = input; preserveAspect]
filedata = Partition[ReadList[filename, Word,
RecordLists -> True,
WordSeparators -> {" "},
RecordSeparators -> {",", "\n"}], 2];
(* WARNING USING THIS SYNTAX IS CONVENIENT BUT THE RESULTS
* ARE STRINGS NOT NUMBERS. TO FIX THIS WE DO THE FOLLOWING
*)
data = Map[ToExpression, filedata];
:[font = text; inactive; preserveAspect]
This package usefully provides all the statistical tools needed
:[font = input; preserveAspect]
Needs["Statistics`DescriptiveStatistics`"]
:[font = text; inactive; preserveAspect]
Now the data is ready to use. It can be seen that the data consists of a list of input-output pairs. The nearest neighbours calculation is only to be performed on the input set, so the output set can be removed to simplify future processing. The following does this:
:[font = input; preserveAspect; endGroup]
data = Table[data[[i]][[1]], {i, 1, Length[data]}];
:[font = section; inactive; Cclosed; preserveAspect; startGroup]
Constructing the kd-Tree
:[font = text; inactive; preserveAspect]
The next step is to build the k-d tree. This is done recursively using two basic steps at each stage. First the dimension (or key) with the largest spread of values over the records in this branch is found, and the median of the record values for this dimension is found. Second, the data is partitioned into two sets about the median previously found; the tree building then continues with each of the smaller sets. The recursion halts when the number of records to be processed falls below some preset value; the records become a terminal or leaf node in the tree.
:[font = text; inactive; preserveAspect]
In order to do this, the representation of the tree structure in Mathematica must be decided. At each non-terminal node, the dimension split on and the associated median value are recorded, together with the left and right branch of the recursively created subtrees. This leads to the following:
Tree = Terminal Node |
{Dimension Number, Partition Value, Left Tree, Right Tree}
:[font = text; inactive; preserveAspect]
This is complicted somewhat by the need to return a list of {record index, distance} pairs as the nearest neighbours for each node. As the tree-building mechanism destroys the ordering of the nodes, the simplest way to retain each node's index in the original list is to tag it with it. Each data point then becomes a pair {value vector, index number}.
:[font = text; inactive; preserveAspect]
In order to manipulate these without cluttering the code to much, a few data access functions have been defined. Given a list of index-tagged data points, "getValueFor" returns the value for dimension (d) at position (i) in the list, "getIndex" returns the index for the record at position (i) and "getPoint" returns the data vector (without index) for the record at position (i).
:[font = input; preserveAspect]
getValueFor[in_, i_, d_] := in[[i]][[1]][[d]];
getIndex[in_, i_] := in[[i]][[2]];
getPoint[in_, i_] := in[[i]][[1]];
:[font = text; inactive; noPageBreak; preserveAspect]
The following function is used to tag each point in the data set with its index number. This is called before the tree is to be built:
:[font = input; preserveAspect]
addIndex[data_] := Table[{data[[i]], i}, {i,1,Length[data]}];
:[font = text; inactive; preserveAspect]
The following module is used to create the k-d tree. It needs to be passed the data set and the dimensionality of the data (the variable "k"). The local variable "b" controls the number of records in each terminal node - the default is 1, but the paper by Bentley[1] mentions that: "... increasing the bucket size from one record per bucket considerably improves the performance of the search...". The paper by White and Jain[2] mentions that spliting the data on the dimension with the highest variance gives better query performance, and this should also be faster to compute. It might be interesting to compares these approaches.
:[font = text; PostScript; formatAsPostScript; inactive; noPageBreak; noPageBreakBelow; preserveAspect]
As the data set is approximately halved at each stage, the time required to build the k-d tree is O(n log n).
:[font = input; noPageBreak; preserveAspect]
buildTree[k_, inData_] :=
Module[
(* "b" is the number of records per bucket *)
{bucketsize = 1, maxspread = 0, i, dimension,
hi, low, thisHi, thisLow, medianval, pair, temp},
If[Length[inData] <= bucketsize,
(* This is a terminal node, so simply return the
* list as it was passed *)
Return[inData],
(* Find the dimension with the largest spread *)
For[i = 1, i <= k, i++,
hi = -Infinity; low = Infinity;
For [j = 1, j <= Length[inData], j++,
temp = getValueFor[inData, j, i];
If[hi < temp, hi = temp, ];
If[low > temp, low = temp, ]
];
If[hi - low >= maxspread,
maxspread = hi - low;
thisHi = hi; thisLow = low;
dimension = i, ]
];
(* Extract values at [dimension] and take median *)
medianval = Median[Map[Part[Part[#,1],dimension]&,
inData]];
(* If the median is the same as the hi or low values
* for the dimension, then repeated values must exist
* in the data set. Return the set without splitting
*)
If[thisLow == medianval || thisHi == medianval,
Return[inData],
(* Else return the node in the tree with the correct
* subtrees *)
pair = split[dimension, medianval, inData];
Return[{dimension, medianval,
buildTree[k, First[pair]],
buildTree[k, Last[pair]]}]
]
]
];
:[font = text; inactive; noPageBreakBelow; preserveAspect]
The final conditional is necessary to deal correctly with data sets where one or vectors are equal. If a particular vecotr is repeated enough, it is possible that the median can be
skewed to the maximum or minium of the range for the dimension. If this occurs, then the entire dataset is returned as a terminal node - no partitioning is possible as one branch will become empty, leading to an infinite loop.
:[font = text; inactive; noPageBreak; preserveAspect]
The following is used during the creation of the tree to split the records around a particular value (v) for a particular dimension (d). It may be quicker to do this "in place" in a programming language such as C.
:[font = input; preserveAspect; endGroup]
split[d_, v_, list_] :=
Module[
{i, hi = {}, low = {}},
For[i = 1, i <= Length[list], i++,
If [getValueFor[list, i, d] >= v,
hi = Append[hi, list[[i]]],
low = Append[low, list[[i]]]
]
];
Return[{low, hi}]
];
:[font = section; inactive; Cclosed; preserveAspect; startGroup]
Finding the Nearest Neighbours
:[font = text; inactive; preserveAspect]
Once the tree has been built, the task is then to search through it for the nearest neighbours of each point. The module takes parameters for the query vector to look for (query), the dimensionality of the data (k) and the previously constructed k-d tree (tree). Several "global" variables are used:
nearest:This is best set of nearest neighbours found at any one point in the
search. It is a pair of lists, one for the record indexes, the other for the
distances to the query record - both lists are maintained in
increasing distance from the query node.
lowerBounds: This is the set of lower bounds currently in use to define the
region being searched. There is one for each dimension.
upperBounds: These are the equivilent set for the upper bounds on the
search region
:[font = text; inactive; preserveAspect]
The nearest neighbours are found by only searching those parts of the tree which contain data points "close" to the query point. The distance to the furthest nearest neighbour found so far and the size of the geometrical region defined by the tree branches traversed previously are compared to determine whether or not a branch should be examined. The comparison is carried out in the "boundsOverlapBall" procedure.
:[font = text; inactive; noPageBreakBelow; preserveAspect]
The search can terminate whenever the "ballWithinBounds" test returns True. Note that this test is not strictly required for the algorithm to work correctly - it is only used to indicate that the solution has been found.
:[font = input; preserveAspect]
searchTree[query_, k_, tree_] :=
Module[
{medianval, dimension, temp, i, distance, maxloc, maxdist},
Print["upper = ", upperBounds, " lower = ", lowerBounds,
" tree = ", tree];
If[Not[NumberQ[tree[[1]]]],
(* Node is terminal - update nearest neighbours *)
For[i = 1, i <= Length[tree], i++,
(* Add points in bucket if closer than furthest
* found so far, so long as this is not the query
* record *)
maxdist = Max[nearest[[2]]];
distance = norm[query - tree[[i]][[1]]];
If [(distance < maxdist) &&
(query != getPoint[tree, i]),
maxloc = Flatten[Position[nearest[[2]], maxdist]][[1]];
nearest[[1, maxloc]] = getIndex[tree, i];
nearest[[2, maxloc]] = distance, ]
];
(* Sort nearest neighbours list *)
nearest = Transpose[Sort[Transpose[nearest],
(Part[#1, 2] < Part[#2, 2])&]];
(* Check for termination and return *)
If[ballWithinBounds[query, k],
Print["**done**"]; Return[ ],
Return[ ]],
];
(* Node not terminal - call searchTree recursively *)
dimension = tree[[1]];
medianval = tree[[2]];
(* Recursive call on closer son *)
If[query[[dimension]] <= medianval,
temp = upperBounds[[dimension]];
upperBounds[[dimension]] = medianval;
searchTree[query, k, tree[[3]]];
upperBounds[[dimension]] = temp,
(* else *)
temp = lowerBounds[[dimension]];
lowerBounds[[dimension]] = medianval;
searchTree[query, k, tree[[4]]];
lowerBounds[[dimension]] = temp
];
(* Recursive call on further son if necessary *)
If[query[[dimension]] <= medianval,
temp = lowerBounds[[dimension]];
lowerBounds[[dimension]] = medianval;
If[boundsOverlapBall[query, k],
searchTree[query, k, tree[[4]]],
];
lowerBounds[[dimension]] = temp,
(* else *)
temp = upperBounds[[dimension]];
upperBounds[[dimension]] = medianval;
If[boundsOverlapBall[query, k],
searchTree[query, k, tree[[3]]],
];
upperBounds[[dimension]] = temp
];
(* See if we should terminate *)
If[ballWithinBounds[query, k],
Print["**done**"]; Return[ ],
Return[ ]]
];
norm[x_] := N[Sqrt[x.x]];
:[font = text; inactive; preserveAspect]
The following two procedures are used to guide the search process. "ballWithinBounds" tests to see if the coordinate distance from the query record to the closer boundary along each dimension is less than the radius of the furthest nearest neighbour found so far. The test succeeds if all the coordinate distances are greater than the radius.
:[font = input; preserveAspect]
ballWithinBounds[query_, k_] :=
Module[
{d},
For [d = 1, d <= k, d++,
(* "Last[nearest[[2]]]" is the furthest
* nearest neighbour *)
If [((query[[d]] - lowerBounds[[d]])^2 <=
Last[nearest[[2]]]) ||
((query[[d]] - upperBounds[[d]])^2 <=
Last[nearest[[2]]]),
Return[False],
]
];
Return[True]
];
:[font = text; inactive; preserveAspect]
The "boundsOverlapBall" procedure is used on backtracking to decide if it is necessary to search down the opposite branch of the tree to the one previously searched. It determines whether the geometric boundaries of the subfile under consideration overlap a ball of radius equal to the distance of the furthest nearest neighbour found so far. The smallest distance between the query record and the bounded region is found - if this is less than the radius, then the branch of the subtree can be eliminated, as there is no overlap between the domain to be searched and the nearest neighbours.
:[font = input; preserveAspect]
boundsOverlapBall[query_, k_] :=
Module[
{total = 0, d},
(* "Last[nearest[[2]]]" is the furthest
* nearest neighbour *)
For[d = 1, d <= k, d++,
If[query[[d]] < lowerBounds[[d]],
total = total + (query[[d]] - lowerBounds[[d]])^2;
If[total > (Last[nearest[[2]]])^2,
Return[False],
(* else nothing *)
],
(* else *)
If[query[[d]] > upperBounds[[d]],
total = total + (query[[d]] - upperBounds[[d]])^2;
If[total > (Last[nearest[[2]]])^2,
Return[False],
(* else nothing *)
],
(* else nothing *)
]
]
];
Return[True]
];
:[font = text; inactive; preserveAspect]
The following module initialises the global variables to be used in the search. The number of nearest neighbours to be found is needed (numNearest), as is the query record (query), so that the dimensionality of the data cen be found. This initialisation must be repeated for each query point.
:[font = input; noPageBreak; noPageBreakBelow; preserveAspect]
(* Initialisations for globals *)
initialise[query_, numNearest_] :=
Module[
{},
nearest = {Table[-1, {numNearest}],Table[Infinity, {numNearest}]};
upperBounds = Table[Infinity, {Length[query]}];
lowerBounds = Table[-Infinity, {Length[query]}]
];
:[font = text; inactive; noPageBreak; noPageBreakBelow; preserveAspect]
The following calculates the (numNearest) nearest neighbours of the input data entered (data). As an example, the 30 nearest neighbours of the points in "data" can be found by entering "NNarray = nearestNeighbours[data, 30]"
:[font = input; preserveAspect; endGroup]
nearestNeighbours[inData_, numNearest_] :=
Module[
{tree, query, indexedData, currentList = {}, i},
indexedData = addIndex[inData];
Print["Building Search Tree..."];
tree = buildTree[Length[inData[[1]]], indexedData];
Print["Starting Nearest Neighbour Search..."];
For[i = 1, i <= Length[inData], i++,
Print["Processing ", i];
query = indexedData[[i]][[1]];
initialise[query, numNearest];
searchTree[query, Length[query], tree];
currentList = Append[currentList, nearest]
];
Return[currentList]
];
:[font = section; inactive; Cclosed; preserveAspect; startGroup]
Experimental Results
:[font = text; inactive; preserveAspect]
The algorithm above has been implemented in C, using long double arthimetic, togther with an naive O(n^2) algorithm to provide a comparison. Both were run initially on datafiles of sizes 100, 200, 400, 800, 1600 and 3200 3-dimensional points. Further runs were carried out using bucket-sizes of 4 and 8 on the same set of points. The results are presented below (in a fixed height cell):
:[font = input; preserveAspect; height = 122]
n2 = {{8,8,8}, {27,27,27}, {101,102,103}, {387,387,386},
{1490, 1490, 1490}, {5887, 5888, 5884}};
nlogn1 = {{8,8,8}, {16,16,16}, {34,34,34}, {67,67,67},
{145,145,146}, {290,289,290}};
nlogn4 = {{6,6,6}, {12,12,12}, {27,27,27}, {55,55,55},
{120,120,121}, {241,241,241}};
nlogn8 = {{6,6,6}, {12,12,12}, {26,26,26}, {53,53,53},
{116,116,117}, {234,233,233}};
xs = {100, 200, 400, 800, 1600, 3200};
n2bar = Transpose[{xs, Map[Mean, n2]}];
nlogn1bar = Transpose[{xs, Map[Mean, nlogn1]}];
nlogn4bar = Transpose[{xs, Map[Mean, nlogn4]}];
nlogn8bar = Transpose[{xs, Map[Mean, nlogn8]}];
p1 = ListPlot[n2bar, PlotJoined->True,
DisplayFunction->Identity,
AxesLabel->{"(n)", "Time"}];
p2 = ListPlot[nlogn1bar, PlotJoined->True,
DisplayFunction->Identity,
AxesLabel->{"(n)", "Time"}];
p3 = ListPlot[nlogn4bar, PlotJoined->True,
DisplayFunction->Identity,
AxesLabel->{"(n)", "Time"}];
p4 = ListPlot[nlogn8bar, PlotJoined->True,
DisplayFunction->Identity,
AxesLabel->{"(n)", "Time"}];
:[font = input; preserveAspect; startGroup]
a1 = Show[{p1, p2}, DisplayFunction->$DisplayFunction,
PlotLabel->"kd-Tree compared to n^2",
PlotRange->All,
Epilog->{Text["n^2", {2500, 5000}],
Text["kd-tree", {3000, 600}]}];
:[font = postscript; PostScript; formatAsPostScript; output; inactive; preserveAspect; pictureLeft = 34; pictureWidth = 325; pictureHeight = 200.062; endGroup]
%!
%%Creator: Mathematica
%%AspectRatio: .61803
MathPictureStart
%% Graphics
/Courier findfont 10 scalefont setfont
% Scaling calculations
-0.00691244 0.00030722 0.013914 0.000100131 [
[(500)] .1467 .01391 0 2 Msboxa
[(1000)] .30031 .01391 0 2 Msboxa
[(1500)] .45392 .01391 0 2 Msboxa
[(2000)] .60753 .01391 0 2 Msboxa
[(2500)] .76114 .01391 0 2 Msboxa
[(3000)] .91475 .01391 0 2 Msboxa
[(\(n\))] 1.025 .01391 -1 0 Msboxa
[(kd-Tree compared to n^2)] .5 .61803 0 -2 0 0 1 Mouter Mrotsboxa
[(1000)] -0.01941 .11405 1 0 Msboxa
[(2000)] -0.01941 .21418 1 0 Msboxa
[(3000)] -0.01941 .31431 1 0 Msboxa
[(4000)] -0.01941 .41444 1 0 Msboxa
[(5000)] -0.01941 .51457 1 0 Msboxa
[(6000)] -0.01941 .6147 1 0 Msboxa
[(Time)] -0.00691 .61803 0 -4 Msboxa
[(n^2)] .76114 .51457 0 0 Msboxa
[(kd-tree)] .91475 .07399 0 0 Msboxa
[ -0.00791 -0.001 0 0 ]
[ 1.001 .61903 0 0 ]
] MathScale
% Start of Graphics
1 setlinecap
1 setlinejoin
newpath
[ ] 0 setdash
0 g
p
p
.002 w
.1467 .01391 m
.1467 .02016 L
s
P
[(500)] .1467 .01391 0 2 Mshowa
p
.002 w
.30031 .01391 m
.30031 .02016 L
s
P
[(1000)] .30031 .01391 0 2 Mshowa
p
.002 w
.45392 .01391 m
.45392 .02016 L
s
P
[(1500)] .45392 .01391 0 2 Mshowa
p
.002 w
.60753 .01391 m
.60753 .02016 L
s
P
[(2000)] .60753 .01391 0 2 Mshowa
p
.002 w
.76114 .01391 m
.76114 .02016 L
s
P
[(2500)] .76114 .01391 0 2 Mshowa
p
.002 w
.91475 .01391 m
.91475 .02016 L
s
P
[(3000)] .91475 .01391 0 2 Mshowa
p
.001 w
.02381 .01391 m
.02381 .01766 L
s
P
p
.001 w
.05453 .01391 m
.05453 .01766 L
s
P
p
.001 w
.08525 .01391 m
.08525 .01766 L
s
P
p
.001 w
.11598 .01391 m
.11598 .01766 L
s
P
p
.001 w
.17742 .01391 m
.17742 .01766 L
s
P
p
.001 w
.20814 .01391 m
.20814 .01766 L
s
P
p
.001 w
.23886 .01391 m
.23886 .01766 L
s
P
p
.001 w
.26959 .01391 m
.26959 .01766 L
s
P
p
.001 w
.33103 .01391 m
.33103 .01766 L
s
P
p
.001 w
.36175 .01391 m
.36175 .01766 L
s
P
p
.001 w
.39247 .01391 m
.39247 .01766 L
s
P
p
.001 w
.4232 .01391 m
.4232 .01766 L
s
P
p
.001 w
.48464 .01391 m
.48464 .01766 L
s
P
p
.001 w
.51536 .01391 m
.51536 .01766 L
s
P
p
.001 w
.54608 .01391 m
.54608 .01766 L
s
P
p
.001 w
.5768 .01391 m
.5768 .01766 L
s
P
p
.001 w
.63825 .01391 m
.63825 .01766 L
s
P
p
.001 w
.66897 .01391 m
.66897 .01766 L
s
P
p
.001 w
.69969 .01391 m
.69969 .01766 L
s
P
p
.001 w
.73041 .01391 m
.73041 .01766 L
s
P
p
.001 w
.79186 .01391 m
.79186 .01766 L
s
P
p
.001 w
.82258 .01391 m
.82258 .01766 L
s
P
p
.001 w
.8533 .01391 m
.8533 .01766 L
s
P
p
.001 w
.88402 .01391 m
.88402 .01766 L
s
P
p
.001 w
.94547 .01391 m
.94547 .01766 L
s
P
p
.001 w
.97619 .01391 m
.97619 .01766 L
s
P
[(\(n\))] 1.025 .01391 -1 0 Mshowa
p
.002 w
0 .01391 m
1 .01391 L
s
P
[(kd-Tree compared to n^2)] .5 .61803 0 -2 0 0 1 Mouter Mrotshowa
p
.002 w
-0.00691 .11405 m
-0.00066 .11405 L
s
P
[(1000)] -0.01941 .11405 1 0 Mshowa
p
.002 w
-0.00691 .21418 m
-0.00066 .21418 L
s
P
[(2000)] -0.01941 .21418 1 0 Mshowa
p
.002 w
-0.00691 .31431 m
-0.00066 .31431 L
s
P
[(3000)] -0.01941 .31431 1 0 Mshowa
p
.002 w
-0.00691 .41444 m
-0.00066 .41444 L
s
P
[(4000)] -0.01941 .41444 1 0 Mshowa
p
.002 w
-0.00691 .51457 m
-0.00066 .51457 L
s
P
[(5000)] -0.01941 .51457 1 0 Mshowa
p
.002 w
-0.00691 .6147 m
-0.00066 .6147 L
s
P
[(6000)] -0.01941 .6147 1 0 Mshowa
p
.001 w
-0.00691 .03394 m
-0.00316 .03394 L
s
P
p
.001 w
-0.00691 .05397 m
-0.00316 .05397 L
s
P
p
.001 w
-0.00691 .07399 m
-0.00316 .07399 L
s
P
p
.001 w
-0.00691 .09402 m
-0.00316 .09402 L
s
P
p
.001 w
-0.00691 .13407 m
-0.00316 .13407 L
s
P
p
.001 w
-0.00691 .1541 m
-0.00316 .1541 L
s
P
p
.001 w
-0.00691 .17412 m
-0.00316 .17412 L
s
P
p
.001 w
-0.00691 .19415 m
-0.00316 .19415 L
s
P
p
.001 w
-0.00691 .2342 m
-0.00316 .2342 L
s
P
p
.001 w
-0.00691 .25423 m
-0.00316 .25423 L
s
P
p
.001 w
-0.00691 .27425 m
-0.00316 .27425 L
s
P
p
.001 w
-0.00691 .29428 m
-0.00316 .29428 L
s
P
p
.001 w
-0.00691 .33433 m
-0.00316 .33433 L
s
P
p
.001 w
-0.00691 .35436 m
-0.00316 .35436 L
s
P
p
.001 w
-0.00691 .37439 m
-0.00316 .37439 L
s
P
p
.001 w
-0.00691 .39441 m
-0.00316 .39441 L
s
P
p
.001 w
-0.00691 .43446 m
-0.00316 .43446 L
s
P
p
.001 w
-0.00691 .45449 m
-0.00316 .45449 L
s
P
p
.001 w
-0.00691 .47452 m
-0.00316 .47452 L
s
P
p
.001 w
-0.00691 .49454 m
-0.00316 .49454 L
s
P
p
.001 w
-0.00691 .5346 m
-0.00316 .5346 L
s
P
p
.001 w
-0.00691 .55462 m
-0.00316 .55462 L
s
P
p
.001 w
-0.00691 .57465 m
-0.00316 .57465 L
s
P
p
.001 w
-0.00691 .59467 m
-0.00316 .59467 L
s
P
[(Time)] -0.00691 .61803 0 -4 Mshowa
p
.002 w
-0.00691 0 m
-0.00691 .61803 L
s
P
P
p
.004 w
.02381 .01472 m
.05453 .01662 L
.11598 .02413 L
.23886 .05263 L
.48464 .16311 L
.97619 .60332 L
s
.02381 .01472 m
.05453 .01552 L
.11598 .01732 L
.23886 .02062 L
.48464 .02847 L
.97619 .04292 L
s
P
[(n^2)] .76114 .51457 0 0 Mshowa
[(kd-tree)] .91475 .07399 0 0 Mshowa
0 0 m
1 0 L
1 .61803 L
0 .61803 L
closepath
clip
newpath
% End of Graphics
MathPictureEnd
:[font = input; preserveAspect; startGroup]
a2 = Show[{p2, p3, p4},
PlotLabel->"kd-tree bucket size comparison",
DisplayFunction->$DisplayFunction,
PlotRange->All,
Epilog->{Text["1", {3300, 280}],
Text["4", {3300, 250}],
Text["8", {3300, 230}]}];
:[font = postscript; PostScript; formatAsPostScript; output; inactive; preserveAspect; pictureLeft = 34; pictureWidth = 335; pictureHeight = 206.188; endGroup]
%!
%%Creator: Mathematica
%%AspectRatio: .61803
MathPictureStart
%% Graphics
/Courier findfont 10 scalefont setfont
% Scaling calculations
-0.00691244 0.00030722 0.00226519 0.00207498 [
[(500)] .1467 .00227 0 2 Msboxa
[(1000)] .30031 .00227 0 2 Msboxa
[(1500)] .45392 .00227 0 2 Msboxa
[(2000)] .60753 .00227 0 2 Msboxa
[(2500)] .76114 .00227 0 2 Msboxa
[(3000)] .91475 .00227 0 2 Msboxa
[(\(n\))] 1.025 .00227 -1 0 Msboxa
[(kd-tree bucket size comparison)] .5 .61803 0 -2 0 0 1 Mouter Mrotsboxa
[(50)] -0.01941 .10601 1 0 Msboxa
[(100)] -0.01941 .20976 1 0 Msboxa
[(150)] -0.01941 .31351 1 0 Msboxa
[(200)] -0.01941 .41726 1 0 Msboxa
[(250)] -0.01941 .52101 1 0 Msboxa
[(Time)] -0.00691 .61803 0 -4 Msboxa
[(1)] 1.00691 .58326 0 0 Msboxa
[(4)] 1.00691 .52101 0 0 Msboxa
[(8)] 1.00691 .47951 0 0 Msboxa
[ -0.00791 -0.001 0 0 ]
[ 1.001 .61903 0 0 ]
] MathScale
% Start of Graphics
1 setlinecap
1 setlinejoin
newpath
[ ] 0 setdash
0 g
p
p
.002 w
.1467 .00227 m
.1467 .00852 L
s
P
[(500)] .1467 .00227 0 2 Mshowa
p
.002 w
.30031 .00227 m
.30031 .00852 L
s
P
[(1000)] .30031 .00227 0 2 Mshowa
p
.002 w
.45392 .00227 m
.45392 .00852 L
s
P
[(1500)] .45392 .00227 0 2 Mshowa
p
.002 w
.60753 .00227 m
.60753 .00852 L
s
P
[(2000)] .60753 .00227 0 2 Mshowa
p
.002 w
.76114 .00227 m
.76114 .00852 L
s
P
[(2500)] .76114 .00227 0 2 Mshowa
p
.002 w
.91475 .00227 m
.91475 .00852 L
s
P
[(3000)] .91475 .00227 0 2 Mshowa
p
.001 w
.02381 .00227 m
.02381 .00602 L
s
P
p
.001 w
.05453 .00227 m
.05453 .00602 L
s
P
p
.001 w
.08525 .00227 m
.08525 .00602 L
s
P
p
.001 w
.11598 .00227 m
.11598 .00602 L
s
P
p
.001 w
.17742 .00227 m
.17742 .00602 L
s
P
p
.001 w
.20814 .00227 m
.20814 .00602 L
s
P
p
.001 w
.23886 .00227 m
.23886 .00602 L
s
P
p
.001 w
.26959 .00227 m
.26959 .00602 L
s
P
p
.001 w
.33103 .00227 m
.33103 .00602 L
s
P
p
.001 w
.36175 .00227 m
.36175 .00602 L
s
P
p
.001 w
.39247 .00227 m
.39247 .00602 L
s
P
p
.001 w
.4232 .00227 m
.4232 .00602 L
s
P
p
.001 w
.48464 .00227 m
.48464 .00602 L
s
P
p
.001 w
.51536 .00227 m
.51536 .00602 L
s
P
p
.001 w
.54608 .00227 m
.54608 .00602 L
s
P
p
.001 w
.5768 .00227 m
.5768 .00602 L
s
P
p
.001 w
.63825 .00227 m
.63825 .00602 L
s
P
p
.001 w
.66897 .00227 m
.66897 .00602 L
s
P
p
.001 w
.69969 .00227 m
.69969 .00602 L
s
P
p
.001 w
.73041 .00227 m
.73041 .00602 L
s
P
p
.001 w
.79186 .00227 m
.79186 .00602 L
s
P
p
.001 w
.82258 .00227 m
.82258 .00602 L
s
P
p
.001 w
.8533 .00227 m
.8533 .00602 L
s
P
p
.001 w
.88402 .00227 m
.88402 .00602 L
s
P
p
.001 w
.94547 .00227 m
.94547 .00602 L
s
P
p
.001 w
.97619 .00227 m
.97619 .00602 L
s
P
[(\(n\))] 1.025 .00227 -1 0 Mshowa
p
.002 w
0 .00227 m
1 .00227 L
s
P
[(kd-tree bucket size comparison)] .5 .61803 0 -2 0 0 1 Mouter Mrotshowa
p
.002 w
-0.00691 .10601 m
-0.00066 .10601 L
s
P
[(50)] -0.01941 .10601 1 0 Mshowa
p
.002 w
-0.00691 .20976 m
-0.00066 .20976 L
s
P
[(100)] -0.01941 .20976 1 0 Mshowa
p
.002 w
-0.00691 .31351 m
-0.00066 .31351 L
s
P
[(150)] -0.01941 .31351 1 0 Mshowa
p
.002 w
-0.00691 .41726 m
-0.00066 .41726 L
s
P
[(200)] -0.01941 .41726 1 0 Mshowa
p
.002 w
-0.00691 .52101 m
-0.00066 .52101 L
s
P
[(250)] -0.01941 .52101 1 0 Mshowa
p
.001 w
-0.00691 .02302 m
-0.00316 .02302 L
s
P
p
.001 w
-0.00691 .04376 m
-0.00316 .04376 L
s
P
p
.001 w
-0.00691 .06451 m
-0.00316 .06451 L
s
P
p
.001 w
-0.00691 .08526 m
-0.00316 .08526 L
s
P
p
.001 w
-0.00691 .12676 m
-0.00316 .12676 L
s
P
p
.001 w
-0.00691 .14751 m
-0.00316 .14751 L
s
P
p
.001 w
-0.00691 .16826 m
-0.00316 .16826 L
s
P
p
.001 w
-0.00691 .18901 m
-0.00316 .18901 L
s
P
p
.001 w
-0.00691 .23051 m
-0.00316 .23051 L
s
P
p
.001 w
-0.00691 .25126 m
-0.00316 .25126 L
s
P
p
.001 w
-0.00691 .27201 m
-0.00316 .27201 L
s
P
p
.001 w
-0.00691 .29276 m
-0.00316 .29276 L
s
P
p
.001 w
-0.00691 .33426 m
-0.00316 .33426 L
s
P
p
.001 w
-0.00691 .35501 m
-0.00316 .35501 L
s
P
p
.001 w
-0.00691 .37576 m
-0.00316 .37576 L
s
P
p
.001 w
-0.00691 .39651 m
-0.00316 .39651 L
s
P
p
.001 w
-0.00691 .43801 m
-0.00316 .43801 L
s
P
p
.001 w
-0.00691 .45876 m
-0.00316 .45876 L
s
P
p
.001 w
-0.00691 .47951 m
-0.00316 .47951 L
s
P
p
.001 w
-0.00691 .50026 m
-0.00316 .50026 L
s
P
p
.001 w
-0.00691 .54176 m
-0.00316 .54176 L
s
P
p
.001 w
-0.00691 .56251 m
-0.00316 .56251 L
s
P
p
.001 w
-0.00691 .58326 m
-0.00316 .58326 L
s
P
p
.001 w
-0.00691 .60401 m
-0.00316 .60401 L
s
P
[(Time)] -0.00691 .61803 0 -4 Mshowa
p
.002 w
-0.00691 0 m
-0.00691 .61803 L
s
P
P
p
.004 w
.02381 .01887 m
.05453 .03546 L
.11598 .07281 L
.23886 .14129 L
.48464 .30383 L
.97619 .60332 L
s
.02381 .01472 m
.05453 .02716 L
.11598 .05829 L
.23886 .11639 L
.48464 .25195 L
.97619 .50234 L
s
.02381 .01472 m
.05453 .02716 L
.11598 .05621 L
.23886 .11224 L
.48464 .24365 L
.97619 .48643 L
s
P
[(1)] 1.00691 .58326 0 0 Mshowa
[(4)] 1.00691 .52101 0 0 Mshowa
[(8)] 1.00691 .47951 0 0 Mshowa
0 0 m
1 0 L
1 .61803 L
0 .61803 L
closepath
clip
newpath
% End of Graphics
MathPictureEnd
:[font = text; inactive; preserveAspect]
The first graph compares the performance of the O(n^2) algorithm and the kd-tree method. It can be seen that the kd-tree algorithm does indeed have O(n log n) performance. At 3200 points, the O(n^2) algorithm took on average 1 hour 38 minutes to complete, whereas the kd-tree took just under 5 minutes.
:[font = text; inactive; preserveAspect]
The second graph compares different setting for the bucket size on the same set of points. The top line is bucket size = 1, the middle is bucket size = 4, the lowest line if bucket size = 8. It can be seen that increasing the size does give a performance increase, particularly noticable in the jump from 1 to 4. The increase from 4 to 8 is less marked.
:[font = text; inactive; preserveAspect]
In order to determine how the algorithm scales with increasing dimension, a series of tests were performed where the dimension ranged from 2 to 40 and the number of points ranged from 100 to 2000 (ie. 100 tests in all). All tests were perfomed on an
Alpha workstation. The raw results are in the following fixed height cell:
:[font = input; wordwrap; preserveAspect; height = 54]
rawdata = {{2, 200, 0}, {2, 400, 0}, {2, 600, 0}, {2, 800, 0}, {2, 1000, 0}, {2, 1200, 0},
{2, 1400, 0}, {2, 1600, 0}, {2, 1800, 1}, {2, 2000, 1}, {4, 200, 0},{4, 400,
0}, {4, 600, 0}, {4, 800, 0}, {4, 1000, 1}, {4, 1200, 1}, {4, 1400, 2}, {4,
1600, 2}, {4, 1800, 3}, {4, 2000, 3}, {6, 200, 0}, {6, 400, 0}, {6, 600, 1},
{6, 800, 2}, {6, 1000, 3}, {6, 1200, 5}, {6, 1400, 6}, {6, 1600, 7}, {6, 1800,
9}, {6, 2000, 10}, {8, 200, 0}, {8, 400, 0}, {8, 600, 2}, {8, 800, 5}, {8,
1000, 7}, {8, 1200, 11}, {8, 1400, 14}, {8, 1600, 18}, {8, 1800, 21}, {8, 2000,
25}, {10, 200, 0}, {10, 400, 1}, {10, 600, 4}, {10, 800, 7}, {10, 1000, 11},
{10, 1200, 18}, {10, 1400, 23}, {10, 1600, 29}, {10, 1800, 36}, {10, 2000, 43},
{12, 200, 0}, {12, 400, 1}, {12, 600, 4}, {12, 800, 9}, {12, 1000, 13}, {12,
1200, 22}, {12, 1400, 29}, {12, 1600, 39}, {12, 1800, 44}, {12, 2000, 56}, {14,
200, 0}, {14, 400, 1}, {14, 600, 5}, {14, 800, 9}, {14, 1000, 15}, {14, 1200,
24}, {14, 1400, 32}, {14, 1600, 45}, {14, 1800, 51}, {14, 2000, 62}, {16, 200,
1}, {16, 400, 2}, {16, 600, 6}, {16, 800, 11}, {16, 1000, 17}, {16, 1200, 27},
{16, 1400, 42}, {16, 1600, 47}, {16, 1800, 62}, {16, 2000, 71}, {18, 200, 1},
{18, 400, 2}, {18, 600, 6}, {18, 800, 12}, {18, 1000, 18}, {18, 1200, 29}, {18,
1400, 42}, {18, 1600, 52}, {18, 1800, 62}, {18, 2000, 77}, {20, 200, 0}, {20,
400, 2}, {20, 600, 9}, {20, 800, 13}, {20, 1000, 20}, {20, 1200, 32}, {20,
1400, 44}, {20, 1600, 56}, {20, 1800, 71}, {20, 2000, 82}, {22, 200, 0}, {22,
400, 3}, {22, 600, 8}, {22, 800, 15}, {22, 1000, 22}, {22, 1200, 35}, {22,
1400, 49}, {22, 1600, 61}, {22, 1800, 74}, {22, 2000, 89}, {24, 200, 1}, {24,
400, 3}, {24, 600, 9}, {24, 800, 17}, {24, 1000, 24}, {24, 1200, 39}, {24,
1400, 52}, {24, 1600, 70}, {24, 1800, 79}, {24, 2000, 96}, {26, 200, 0}, {26,
400, 3}, {26, 600, 10}, {26, 800, 17}, {26, 1000, 25}, {26, 1200, 40}, {26,
1400, 55}, {26, 1600, 75}, {26, 1800, 87}, {26, 2000, 104}, {28, 200, 0}, {28,
400, 4}, {28, 600, 11}, {28, 800, 18}, {28, 1000, 27}, {28, 1200, 43}, {28,
1400, 61}, {28, 1600, 80}, {28, 1800, 91}, {28, 2000, 119}, {30, 200, 1}, {30,
400, 4}, {30, 600, 11}, {30, 800, 19}, {30, 1000, 28}, {30, 1200, 47}, {30,
1400, 69}, {30, 1600, 83}, {30, 1800, 100}, {30, 2000, 119}, {32, 200, 0}, {32,
400, 4}, {32, 600, 12}, {32, 800, 22}, {32, 1000, 33}, {32, 1200, 50}, {32,
1400, 67}, {32, 1600, 88}, {32, 1800, 116}, {32, 2000, 138}, {34, 200, 0}, {34,
400, 5}, {34, 600, 12}, {34, 800, 22}, {34, 1000, 32}, {34, 1200, 52}, {34,
1400, 71}, {34, 1600, 87}, {34, 1800, 114}, {34, 2000, 134}, {36, 200, 0}, {36,
400, 5}, {36, 600, 13}, {36, 800, 23}, {36, 1000, 33}, {36, 1200, 53}, {36,
1400, 89}, {36, 1600, 105}, {36, 1800, 159}, {36, 2000, 135}, {38, 200, 0},
{38, 400, 6}, {38, 600, 14}, {38, 800, 24}, {38, 1000, 36}, {38, 1200, 66},
{38, 1400, 94}, {38, 1600, 130}, {38, 1800, 162}, {38, 2000, 180}, {40, 200,
1}, {40, 400, 10}, {40, 600, 27}, {40, 800, 49}, {40, 1000, 67}, {40, 1200,
105}, {40, 1400, 115}, {40, 1600, 156}, {40, 1800, 168}, {40, 2000, 154}};
:[font = input; preserveAspect; startGroup]
Needs["Graphics`Graphics3D`"];
plotdata = Partition[
Table[rawdata[[i,3]], {i,1,Length[rawdata]}],
10];
a3 = ListPlot3D[plotdata,
AxesLabel->{"Dimension", "Num Vectors", Runtime},
Ticks->{Table[{i,4*i},{i,0,10}],
Table[{2j,200*j},{j,1,10}],
Automatic},
PlotLabel->"Surface Plot of the Runtime in Seconds"]
:[font = postscript; PostScript; formatAsPostScript; output; inactive; preserveAspect; pictureLeft = 34; pictureWidth = 381; pictureHeight = 313]
%!
%%Creator: Mathematica
%%AspectRatio: .82055
MathPictureStart
%% SurfaceGraphics
/Courier findfont 10 scalefont setfont
% Scaling calculations
0.0249355 0.99742 -0.0396341 0.99742 [
[(Surface Plot of the Runtime in Seconds)] .5 .82055 0 -1.5 Msboxa
[(4)] .05113 .25884 1 .93395 Msboxa
[(8)] .11298 .23449 1 .97619 Msboxa
[(12)] .17647 .20951 .97806 1 Msboxa
[(16)] .24165 .18387 .93173 1 Msboxa
[(20)] .30859 .15753 .8854 1 Msboxa
[(24)] .37738 .13048 .83907 1 Msboxa
[(28)] .44808 .10268 .79274 1 Msboxa
[(32)] .52077 .07411 .7464 1 Msboxa
[(36)] .59555 .04472 .70007 1 Msboxa
[(40)] .6725 .0145 .65374 1 Msboxa
[(Dimension)] .30204 .09689 .86223 1 Msboxa
[(200)] .70814 .04674 -1 .38545 Msboxa
[(400)] .7413 .0975 -1 .37378 Msboxa
[(600)] .77288 .14586 -1 .36279 Msboxa
[(800)] .80299 .19197 -1 .35243 Msboxa
[(1000)] .83174 .23599 -1 .34264 Msboxa
[(1200)] .8592 .27805 -1 .33339 Msboxa
[(1400)] .88548 .31829 -1 .32462 Msboxa
[(1600)] .91064 .35682 -1 .3163 Msboxa
[(1800)] .93475 .39375 -1 .30839 Msboxa
[(2000)] .95788 .42917 -1 .30087 Msboxa
[(Num Vectors)] .89773 .2266 -1 .34028 Msboxa
[(0)] .04785 .27682 1 -0.3906 Msboxa
[(50)] .03893 .33271 1 -0.37954 Msboxa
[(100)] .02966 .39078 1 -0.36801 Msboxa
[(150)] .02003 .45116 1 -0.35598 Msboxa
[(Runtime)] -0.02691 .40064 1 -0.37036 Msboxa
[ 0 0 0 0 ]
[ 1 .82055 0 0 ]
] MathScale
% Start of Graphics
1 setlinecap
1 setlinejoin
newpath
[ ] 0 setdash
0 g
[(Surface Plot of the Runtime in Seconds)] .5 .82055 0 -1.5 Mshowa
p
p
.002 w
.06024 .26735 m
.67932 .02494 L
s
P
p
.002 w
.06024 .26735 m
.0648 .2716 L
s
P
[(4)] .05113 .25884 1 .93395 Mshowa
p
.002 w
.1219 .2432 m
.12636 .24756 L
s
P
[(8)] .11298 .23449 1 .97619 Mshowa
p
.002 w
.18518 .21843 m
.18954 .22288 L
s
P
[(12)] .17647 .20951 .97806 1 Mshowa
p
.002 w
.25014 .19299 m
.25439 .19755 L
s
P
[(16)] .24165 .18387 .93173 1 Mshowa
p
.002 w
.31686 .16687 m
.32099 .17153 L
s
P
[(20)] .30859 .15753 .8854 1 Mshowa
p
.002 w
.38539 .14003 m
.3894 .14481 L
s
P
[(24)] .37738 .13048 .83907 1 Mshowa
p
.002 w
.45582 .11245 m
.45969 .11734 L
s
P
[(28)] .44808 .10268 .79274 1 Mshowa
p
.002 w
.52823 .0841 m
.53196 .08909 L
s
P
[(32)] .52077 .07411 .7464 1 Mshowa
p
.002 w
.6027 .05494 m
.60628 .06005 L
s
P
[(36)] .59555 .04472 .70007 1 Mshowa
p
.002 w
.67932 .02494 m
.68274 .03015 L
s
P
[(40)] .6725 .0145 .65374 1 Mshowa
[(Dimension)] .30204 .09689 .86223 1 Mshowa
P
p
p
.002 w
.67932 .02494 m
.94594 .43277 L
s
P
p
.002 w
.69651 .05122 m
.69069 .05346 L
s
P
[(200)] .70814 .04674 -1 .38545 Mshowa
p
.002 w
.72962 .10187 m
.72378 .10405 L
s
P
[(400)] .7413 .0975 -1 .37378 Mshowa
p
.002 w
.76116 .15011 m
.7553 .15224 L
s
P
[(600)] .77288 .14586 -1 .36279 Mshowa
p
.002 w
.79123 .19611 m
.78535 .19819 L
s
P
[(800)] .80299 .19197 -1 .35243 Mshowa
p
.002 w
.81994 .24003 m
.81404 .24205 L
s
P
[(1000)] .83174 .23599 -1 .34264 Mshowa
p
.002 w
.84738 .282 m
.84146 .28397 L
s
P
[(1200)] .8592 .27805 -1 .33339 Mshowa
p
.002 w
.87362 .32214 m
.86769 .32407 L
s
P
[(1400)] .88548 .31829 -1 .32462 Mshowa
p
.002 w
.89875 .36058 m
.89281 .36246 L
s
P
[(1600)] .91064 .35682 -1 .3163 Mshowa
p
.002 w
.92284 .39743 m
.91688 .39926 L
s
P
[(1800)] .93475 .39375 -1 .30839 Mshowa
p
.002 w
.94594 .43277 m
.93997 .43456 L
s
P
[(2000)] .95788 .42917 -1 .30087 Mshowa
[(Num Vectors)] .89773 .2266 -1 .34028 Mshowa
P
p
p
.002 w
.06024 .26735 m
.02494 .49015 L
s
P
p
.002 w
.05946 .27229 m
.06527 .27002 L
s
P
[(0)] .04785 .27682 1 -0.3906 Mshowa
p
.002 w
.05058 .32829 m
.05641 .32608 L
s
P
[(50)] .03893 .33271 1 -0.37954 Mshowa
p
.002 w
.04136 .38648 m
.04721 .38432 L
s
P
[(100)] .02966 .39078 1 -0.36801 Mshowa
p
.002 w
.03178 .44698 m
.03765 .44489 L
s
P
[(150)] .02003 .45116 1 -0.35598 Mshowa
p
.001 w
.05771 .28332 m
.0612 .28196 L
s
P
p
.001 w
.05595 .29443 m
.05944 .29309 L
s
P
p
.001 w
.05418 .30563 m
.05767 .30429 L
s
P
p
.001 w
.05239 .31692 m
.05588 .31558 L
s
P
p
.001 w
.04877 .33975 m
.05227 .33843 L
s
P
p
.001 w
.04694 .3513 m
.05044 .34998 L
s
P
p
.001 w
.0451 .36293 m
.0486 .36163 L
s
P
p
.001 w
.04324 .37466 m
.04674 .37336 L
s
P
p
.001 w
.03948 .39839 m
.04299 .3971 L
s
P
p
.001 w
.03757 .41039 m
.04109 .40912 L
s
P
p
.001 w
.03566 .42249 m
.03918 .42122 L
s
P
p
.001 w
.03372 .43469 m
.03725 .43342 L
s
P
p
.001 w
.02981 .45937 m
.03334 .45812 L
s
P
p
.001 w
.02783 .47186 m
.03136 .47062 L
s
P
p
.001 w
.02584 .48445 m
.02937 .48322 L
s
P
[(Runtime)] -0.02691 .40064 1 -0.37036 Mshowa
P
0 0 m
1 0 L
1 .82055 L
0 .82055 L
closepath
clip
newpath
p
.002 w
.06024 .26735 m
.02494 .49015 L
s
.02494 .49015 m
.40296 .79562 L
s
.40296 .79562 m
.41001 .59401 L
s
.41001 .59401 m
.06024 .26735 L
s
.67932 .02494 m
.94594 .43277 L
s
.94594 .43277 m
.97506 .64585 L
s
.97506 .64585 m
.69286 .25814 L
s
.69286 .25814 m
.67932 .02494 L
s
.06024 .26735 m
.02494 .49015 L
s
.02494 .49015 m
.69286 .25814 L
s
.69286 .25814 m
.67932 .02494 L
s
.67932 .02494 m
.06024 .26735 L
s
.41001 .59401 m
.94594 .43277 L
s
.94594 .43277 m
.97506 .64585 L
s
.97506 .64585 m
.40296 .79562 L
s
.40296 .79562 m
.41001 .59401 L
s
P
p
.62 .716 .914 r
.0015 w
.39451 .58425 .40982 .59955 .46421 .59234 .44926 .5737 Metetra
.611 .675 .887 r
.44926 .5737 .46421 .59234 .52009 .5932 .50541 .56493 Metetra
.605 .593 .813 r
.50541 .56493 .52009 .5932 .57791 .59936 .56312 .55802 Metetra
.596 .529 .75 r
.56312 .55802 .57791 .59936 .63772 .60144 .62258 .55303 Metetra
.534 .473 .734 r
.62258 .55303 .63772 .60144 .70082 .62565 .68485 .56733 Metetra
.548 .461 .709 r
.68485 .56733 .70082 .62565 .76474 .61927 .74971 .58003 Metetra
.487 .483 .778 r
.74971 .58003 .76474 .61927 .83397 .64842 .81824 .60246 Metetra
.518 .48 .754 r
.81824 .60246 .83397 .64842 .90299 .64449 .88972 .62129 Metetra
.534 .624 .887 r
.88972 .62129 .90299 .64449 .9701 .60949 .96243 .62404 Metetra
.626 .731 .923 r
.37887 .56969 .39451 .58425 .44926 .5737 .43397 .55782 Metetra
.604 .71 .919 r
.43397 .55782 .44926 .5737 .50541 .56493 .49044 .54876 Metetra
.587 .704 .924 r
.49044 .54876 .50541 .56493 .56312 .55802 .54848 .54155 Metetra
.587 .704 .924 r
.54848 .54155 .56312 .55802 .62258 .55303 .60823 .53413 Metetra
.508 .643 .916 r
.60823 .53413 .62258 .55303 .68485 .56733 .67025 .53728 Metetra
.446 .508 .829 r
.67025 .53728 .68485 .56733 .74971 .58003 .73577 .55832 Metetra
.551 .64 .892 r
.73577 .55832 .74971 .58003 .81824 .60246 .80257 .55752 Metetra
.413 .419 .757 r
.80257 .55752 .81824 .60246 .88972 .62129 .87661 .60125 Metetra
.773 .762 .844 r
.87661 .60125 .88972 .62129 .96243 .62404 .94323 .55348 Metetra
.626 .731 .923 r
.36293 .55485 .37887 .56969 .43397 .55782 .41837 .54269 Metetra
.609 .726 .928 r
.41837 .54269 .43397 .55782 .49044 .54876 .47518 .53229 Metetra
.587 .704 .924 r
.47518 .53229 .49044 .54876 .54848 .54155 .53356 .52477 Metetra
.587 .704 .924 r
.53356 .52477 .54848 .54155 .60823 .53413 .59366 .51702 Metetra
.49 .662 .938 r
.59366 .51702 .60823 .53413 .67025 .53728 .65603 .51989 Metetra
.5 .667 .937 r
.65603 .51989 .67025 .53728 .73577 .55832 .72069 .52175 Metetra
.576 .549 .788 r
.72069 .52175 .73577 .55832 .80257 .55752 .7875 .5203 Metetra
.524 .52 .793 r
.7875 .5203 .80257 .55752 .87661 .60125 .85807 .53147 Metetra
.569 .462 .693 r
.85807 .53147 .87661 .60125 .94323 .55348 .93078 .53485 Metetra
.634 .734 .92 r
.34669 .53973 .36293 .55485 .41837 .54269 .4025 .52622 Metetra
.604 .711 .919 r
.4025 .52622 .41837 .54269 .47518 .53229 .45962 .51654 Metetra
.582 .717 .935 r
.45962 .51654 .47518 .53229 .53356 .52477 .51835 .50872 Metetra
.573 .713 .937 r
.51835 .50872 .53356 .52477 .59366 .51702 .57885 .50173 Metetra
.502 .698 .957 r
.57885 .50173 .59366 .51702 .65603 .51989 .64149 .50105 Metetra
.529 .666 .924 r
.64149 .50105 .65603 .51989 .72069 .52175 .70637 .50036 Metetra
.506 .629 .906 r
.70637 .50036 .72069 .52175 .7875 .5203 .774 .50417 Metetra
.369 .628 .953 r
.774 .50417 .7875 .5203 .85807 .53147 .84518 .51627 Metetra
.425 .677 .968 r
.84518 .51627 .85807 .53147 .93078 .53485 .91879 .52177 Metetra
.64 .749 .928 r
.33008 .52535 .34669 .53973 .4025 .52622 .38628 .51048 Metetra
.609 .726 .928 r
.38628 .51048 .4025 .52622 .45962 .51654 .44377 .49944 Metetra
.604 .711 .919 r
.44377 .49944 .45962 .51654 .51835 .50872 .50285 .48915 Metetra
.601 .684 .9 r
.50285 .48915 .51835 .50872 .57885 .50173 .56364 .47964 Metetra
.528 .629 .894 r
.56364 .47964 .57885 .50173 .64149 .50105 .62662 .48076 Metetra
.488 .633 .918 r
.62662 .48076 .64149 .50105 .70637 .50036 .69216 .48527 Metetra
.525 .725 .965 r
.69216 .48527 .70637 .50036 .774 .50417 .75968 .48085 Metetra
.544 .637 .893 r
.75968 .48085 .774 .50417 .84518 .51627 .82994 .47974 Metetra
.557 .551 .803 r
.82994 .47974 .84518 .51627 .91879 .52177 .90318 .48095 Metetra
.635 .721 .909 r
.31326 .5086 .33008 .52535 .38628 .51048 .36975 .49443 Metetra
.609 .726 .928 r
.36975 .49443 .38628 .51048 .44377 .49944 .42758 .48305 Metetra
.609 .726 .928 r
.42758 .48305 .44377 .49944 .50285 .48915 .48704 .47136 Metetra
.596 .707 .922 r
.48704 .47136 .50285 .48915 .56364 .47964 .54821 .46149 Metetra
.532 .681 .933 r
.54821 .46149 .56364 .47964 .62662 .48076 .61144 .45899 Metetra
.532 .642 .904 r
.61144 .45899 .62662 .48076 .69216 .48527 .67706 .45862 Metetra
.54 .603 .866 r
.67706 .45862 .69216 .48527 .75968 .48085 .74526 .45939 Metetra
.582 .679 .907 r
.74526 .45939 .75968 .48085 .82994 .47974 .8153 .45091 Metetra
.483 .562 .86 r
.8153 .45091 .82994 .47974 .90318 .48095 .89007 .4622 Metetra
.642 .736 .917 r
.29605 .49258 .31326 .5086 .36975 .49443 .35294 .47701 Metetra
.612 .714 .917 r
.35294 .47701 .36975 .49443 .42758 .48305 .41111 .46528 Metetra
.612 .714 .917 r
.41111 .46528 .42758 .48305 .48704 .47136 .47092 .45322 Metetra
.604 .711 .919 r
.47092 .45322 .48704 .47136 .54821 .46149 .53246 .44189 Metetra
.548 .674 .921 r
.53246 .44189 .54821 .46149 .61144 .45899 .59601 .43791 Metetra
.552 .664 .911 r
.59601 .43791 .61144 .45899 .67706 .45862 .66183 .43379 Metetra
.525 .616 .885 r
.66183 .43379 .67706 .45862 .74526 .45939 .73041 .43521 Metetra
.58 .655 .887 r
.73041 .43521 .74526 .45939 .8153 .45091 .80095 .4274 Metetra
.541 .646 .902 r
.80095 .4274 .8153 .45091 .89007 .4622 .87464 .42521 Metetra
.648 .751 .924 r
.27842 .47728 .29605 .49258 .35294 .47701 .33574 .4603 Metetra
.618 .729 .925 r
.33574 .4603 .35294 .47701 .41111 .46528 .3943 .44715 Metetra
.604 .711 .92 r
.3943 .44715 .41111 .46528 .47092 .45322 .45446 .43578 Metetra
.61 .726 .928 r
.45446 .43578 .47092 .45322 .53246 .44189 .5164 .42299 Metetra
.542 .685 .932 r
.5164 .42299 .53246 .44189 .59601 .43791 .58033 .41864 Metetra
.561 .693 .929 r
.58033 .41864 .59601 .43791 .66183 .43379 .64647 .41188 Metetra
.527 .652 .914 r
.64647 .41188 .66183 .43379 .73041 .43521 .71528 .41059 Metetra
.601 .664 .883 r
.71528 .41059 .73041 .43521 .80095 .4274 .78592 .3988 Metetra
.554 .61 .864 r
.78592 .3988 .80095 .4274 .87464 .42521 .85994 .39602 Metetra
.642 .723 .907 r
.26059 .45956 .27842 .47728 .33574 .4603 .31819 .44325 Metetra
.626 .731 .922 r
.31819 .44325 .33574 .4603 .3943 .44715 .37717 .42866 Metetra
.612 .714 .917 r
.37717 .42866 .3943 .44715 .45446 .43578 .4377 .41583 Metetra
.614 .702 .907 r
.4377 .41583 .45446 .43578 .5164 .42299 .50002 .40262 Metetra
.565 .682 .918 r
.50002 .40262 .5164 .42299 .58033 .41864 .56427 .39564 Metetra
.564 .657 .899 r
.56427 .39564 .58033 .41864 .64647 .41188 .6308 .38954 Metetra
.576 .675 .907 r
.6308 .38954 .64647 .41188 .71528 .41059 .6996 .38094 Metetra
.58 .615 .852 r
.6996 .38094 .71528 .41059 .78592 .3988 .77092 .3732 Metetra
.56 .644 .89 r
.77092 .3732 .78592 .3988 .85994 .39602 .84511 .36752 Metetra
.649 .738 .914 r
.24232 .44255 .26059 .45956 .31819 .44325 .30035 .42479 Metetra
.612 .714 .918 r
.30035 .42479 .31819 .44325 .37717 .42866 .35957 .41195 Metetra
.633 .746 .93 r
.35957 .41195 .37717 .42866 .4377 .41583 .42062 .39547 Metetra
.614 .702 .907 r
.42062 .39547 .4377 .41583 .50002 .40262 .4833 .38183 Metetra
.574 .686 .917 r
.4833 .38183 .50002 .40262 .56427 .39564 .54792 .37331 Metetra
.577 .675 .906 r
.54792 .37331 .56427 .39564 .6308 .38954 .61475 .3645 Metetra
.581 .654 .887 r
.61475 .3645 .6308 .38954 .6996 .38094 .68392 .35538 Metetra
.56 .644 .89 r
.68392 .35538 .6996 .38094 .77092 .3732 .75582 .34942 Metetra
.584 .679 .906 r
.75582 .34942 .77092 .3732 .84511 .36752 .83001 .33851 Metetra
.656 .752 .921 r
.22357 .42625 .24232 .44255 .30035 .42479 .28208 .40702 Metetra
.634 .733 .92 r
.28208 .40702 .30035 .42479 .35957 .41195 .34184 .39055 Metetra
.622 .693 .895 r
.34184 .39055 .35957 .41195 .42062 .39547 .40315 .3758 Metetra
.62 .716 .915 r
.40315 .3758 .42062 .39547 .4833 .38183 .46625 .36062 Metetra
.582 .689 .915 r
.46625 .36062 .4833 .38183 .54792 .37331 .53124 .35054 Metetra
.569 .671 .908 r
.53124 .35054 .54792 .37331 .61475 .3645 .59848 .34237 Metetra
.59 .693 .914 r
.59848 .34237 .61475 .3645 .68392 .35538 .66799 .33048 Metetra
.593 .671 .894 r
.66799 .33048 .68392 .35538 .75582 .34942 .73989 .31818 Metetra
.567 .609 .854 r
.73989 .31818 .75582 .34942 .83001 .33851 .81487 .31132 Metetra
.656 .74 .911 r
.20453 .40853 .22357 .42625 .28208 .40702 .26341 .38888 Metetra
.634 .733 .92 r
.26341 .38888 .28208 .40702 .34184 .39055 .32356 .37199 Metetra
.627 .731 .922 r
.32356 .37199 .34184 .39055 .40315 .3758 .38532 .35572 Metetra
.62 .716 .915 r
.38532 .35572 .40315 .3758 .46625 .36062 .44883 .34008 Metetra
.588 .704 .923 r
.44883 .34008 .46625 .36062 .53124 .35054 .51422 .32843 Metetra
.548 .674 .921 r
.51422 .32843 .53124 .35054 .59848 .34237 .58192 .32205 Metetra
.625 .732 .924 r
.58192 .32205 .59848 .34237 .66799 .33048 .6517 .30394 Metetra
.559 .644 .89 r
.6517 .30394 .66799 .33048 .73989 .31818 .72441 .29686 Metetra
.592 .72 .932 r
.72441 .29686 .73989 .31818 .81487 .31132 .79933 .28242 Metetra
.656 .728 .902 r
.1852 .38937 .20453 .40853 .26341 .38888 .24445 .36928 Metetra
.635 .721 .91 r
.24445 .36928 .26341 .38888 .32356 .37199 .30497 .35194 Metetra
.635 .721 .91 r
.30497 .35194 .32356 .37199 .38532 .35572 .36717 .33411 Metetra
.621 .705 .905 r
.36717 .33411 .38532 .35572 .44883 .34008 .43106 .31799 Metetra
.598 .696 .911 r
.43106 .31799 .44883 .34008 .51422 .32843 .49686 .30473 Metetra
.607 .688 .9 r
.49686 .30473 .51422 .32843 .58192 .32205 .56481 .28991 Metetra
.578 .607 .846 r
.56481 .28991 .58192 .32205 .6517 .30394 .63522 .28031 Metetra
.619 .706 .907 r
.63522 .28031 .6517 .30394 .72441 .29686 .70776 .26223 Metetra
.59 .606 .836 r
.70776 .26223 .72441 .29686 .79933 .28242 .78316 .24943 Metetra
.657 .74 .911 r
.16536 .37089 .1852 .38937 .24445 .36928 .22499 .35035 Metetra
.642 .736 .917 r
.22499 .35035 .24445 .36928 .30497 .35194 .28598 .33147 Metetra
.628 .719 .912 r
.28598 .33147 .30497 .35194 .36717 .33411 .34851 .31426 Metetra
.634 .733 .919 r
.34851 .31426 .36717 .33411 .43106 .31799 .41292 .29545 Metetra
.598 .696 .911 r
.41292 .29545 .43106 .31799 .49686 .30473 .47912 .28168 Metetra
.613 .702 .908 r
.47912 .28168 .49686 .30473 .56481 .28991 .54751 .26518 Metetra
.592 .682 .903 r
.54751 .26518 .56481 .28991 .63522 .28031 .61823 .25158 Metetra
.626 .666 .869 r
.61823 .25158 .63522 .28031 .70776 .26223 .69112 .23171 Metetra
.583 .636 .869 r
.69112 .23171 .70776 .26223 .78316 .24943 .76702 .21939 Metetra
.657 .74 .911 r
.14509 .35201 .16536 .37089 .22499 .35035 .20511 .33101 Metetra
.642 .736 .917 r
.20511 .33101 .22499 .35035 .28598 .33147 .2665 .31166 Metetra
.642 .736 .917 r
.2665 .31166 .28598 .33147 .34851 .31426 .32959 .29176 Metetra
.635 .71 .901 r
.32959 .29176 .34851 .31426 .41292 .29545 .3944 .27242 Metetra
.614 .702 .907 r
.3944 .27242 .41292 .29545 .47912 .28168 .46105 .25587 Metetra
.627 .686 .885 r
.46105 .25587 .47912 .28168 .54751 .26518 .52984 .23653 Metetra
.62 .663 .87 r
.52984 .23653 .54751 .26518 .61823 .25158 .6008 .21772 Metetra
.612 .625 .84 r
.6008 .21772 .61823 .25158 .69112 .23171 .67411 .19946 Metetra
.613 .642 .855 r
.67411 .19946 .69112 .23171 .76702 .21939 .74991 .18059 Metetra
.664 .741 .908 r
.12438 .33273 .14509 .35201 .20511 .33101 .18491 .31016 Metetra
.649 .726 .905 r
.18491 .31016 .20511 .33101 .2665 .31166 .24678 .28921 Metetra
.642 .712 .899 r
.24678 .28921 .2665 .31166 .32959 .29176 .31026 .26879 Metetra
.648 .715 .896 r
.31026 .26879 .32959 .29176 .3944 .27242 .3756 .24668 Metetra
.634 .688 .883 r
.3756 .24668 .3944 .27242 .46105 .25587 .44271 .22619 Metetra
.637 .661 .857 r
.44271 .22619 .46105 .25587 .52984 .23653 .51185 .20395 Metetra
.629 .641 .843 r
.51185 .20395 .52984 .23653 .6008 .21772 .58306 .18219 Metetra
.631 .627 .828 r
.58306 .18219 .6008 .21772 .67411 .19946 .65643 .15861 Metetra
.621 .595 .803 r
.65643 .15861 .67411 .19946 .74991 .18059 .73213 .13546 Metetra
.664 .741 .908 r
.10321 .31302 .12438 .33273 .18491 .31016 .16415 .28995 Metetra
.657 .739 .911 r
.16415 .28995 .18491 .31016 .24678 .28921 .22655 .26739 Metetra
.656 .728 .902 r
.22655 .26739 .24678 .28921 .31026 .26879 .29062 .24422 Metetra
.654 .706 .885 r
.29062 .24422 .31026 .26879 .3756 .24668 .35643 .22043 Metetra
.647 .693 .879 r
.35643 .22043 .3756 .24668 .44271 .22619 .42401 .19709 Metetra
.649 .675 .861 r
.42401 .19709 .44271 .22619 .51185 .20395 .49355 .17196 Metetra
.646 .657 .846 r
.49355 .17196 .51185 .20395 .58306 .18219 .56506 .14612 Metetra
.636 .629 .826 r
.56506 .14612 .58306 .18219 .65643 .15861 .63867 .12067 Metetra
.639 .624 .819 r
.63867 .12067 .65643 .15861 .73213 .13546 .71441 .09332 Metetra
.664 .741 .908 r
.08158 .29288 .10321 .31302 .16415 .28995 .14293 .26929 Metetra
.664 .741 .908 r
.14293 .26929 .16415 .28995 .22655 .26739 .20587 .24509 Metetra
.663 .73 .9 r
.20587 .24509 .22655 .26739 .29062 .24422 .27047 .22026 Metetra
.655 .717 .894 r
.27047 .22026 .29062 .24422 .35643 .22043 .33672 .19587 Metetra
.661 .719 .891 r
.33672 .19587 .35643 .22043 .42401 .19709 .40486 .16969 Metetra
.652 .695 .877 r
.40486 .16969 .42401 .19709 .49355 .17196 .47485 .14391 Metetra
.658 .698 .875 r
.47485 .14391 .49355 .17196 .56506 .14612 .54683 .11626 Metetra
.651 .685 .869 r
.54683 .11626 .56506 .14612 .63867 .12067 .62089 .08897 Metetra
.655 .678 .86 r
.62089 .08897 .63867 .12067 .71441 .09332 .69705 .05974 Metetra
.664 .741 .908 r
.05946 .27229 .08158 .29288 .14293 .26929 .12122 .24816 Metetra
.664 .741 .908 r
.12122 .24816 .14293 .26929 .20587 .24509 .1846 .22341 Metetra
.664 .741 .908 r
.1846 .22341 .20587 .24509 .27047 .22026 .24966 .19799 Metetra
.664 .741 .908 r
.24966 .19799 .27047 .22026 .33672 .19587 .31649 .17189 Metetra
.662 .73 .9 r
.31649 .17189 .33672 .19587 .40486 .16969 .38514 .14508 Metetra
.662 .73 .9 r
.38514 .14508 .40486 .16969 .47485 .14391 .4557 .11752 Metetra
.661 .719 .892 r
.4557 .11752 .47485 .14391 .54683 .11626 .52824 .08918 Metetra
.655 .717 .893 r
.52824 .08918 .54683 .11626 .62089 .08897 .60288 .06118 Metetra
.661 .719 .892 r
.60288 .06118 .62089 .08897 .69705 .05974 .67969 .03119 Metetra
P
p
.002 w
.67932 .02494 m
.94594 .43277 L
s
.94594 .43277 m
.97506 .64585 L
s
.97506 .64585 m
.69286 .25814 L
s
.69286 .25814 m
.67932 .02494 L
s
.06024 .26735 m
.02494 .49015 L
s
.02494 .49015 m
.69286 .25814 L
s
.69286 .25814 m
.67932 .02494 L
s
.67932 .02494 m
.06024 .26735 L
s
P
p
p
.002 w
.06024 .26735 m
.67932 .02494 L
s
P
p
.002 w
.06024 .26735 m
.0648 .2716 L
s
P
[(4)] .05113 .25884 1 .93395 Mshowa
p
.002 w
.1219 .2432 m
.12636 .24756 L
s
P
[(8)] .11298 .23449 1 .97619 Mshowa
p
.002 w
.18518 .21843 m
.18954 .22288 L
s
P
[(12)] .17647 .20951 .97806 1 Mshowa
p
.002 w
.25014 .19299 m
.25439 .19755 L
s
P
[(16)] .24165 .18387 .93173 1 Mshowa
p
.002 w
.31686 .16687 m
.32099 .17153 L
s
P
[(20)] .30859 .15753 .8854 1 Mshowa
p
.002 w
.38539 .14003 m
.3894 .14481 L
s
P
[(24)] .37738 .13048 .83907 1 Mshowa
p
.002 w
.45582 .11245 m
.45969 .11734 L
s
P
[(28)] .44808 .10268 .79274 1 Mshowa
p
.002 w
.52823 .0841 m
.53196 .08909 L
s
P
[(32)] .52077 .07411 .7464 1 Mshowa
p
.002 w
.6027 .05494 m
.60628 .06005 L
s
P
[(36)] .59555 .04472 .70007 1 Mshowa
p
.002 w
.67932 .02494 m
.68274 .03015 L
s
P
[(40)] .6725 .0145 .65374 1 Mshowa
[(Dimension)] .30204 .09689 .86223 1 Mshowa
P
% End of Graphics
MathPictureEnd
:[font = output; output; inactive; preserveAspect; endGroup]
SurfaceGraphics["<<>>"]
;[o]
-SurfaceGraphics-
:[font = text; inactive; preserveAspect; endGroup]
The above graph is a surface plot of the results. The x-axis is the number of dimensions, the y-axis ("into" the page) is the number of popints, and the vertical axis the runtime required. It can be seen once again that the run-time is approximately linear with the number of points, but scales approximately as the square of the number of dimensions.
:[font = section; inactive; Cclosed; preserveAspect; startGroup]
References
:[font = text; inactive; preserveAspect; endGroup; endGroup]
[1] "An Algorithm for Finding Best Matches in Logarthimic Expected Time"
J.H Friedman, J.L Bentley, R.A Finkel
ACM Transactions on Mathematical Software, Vol 3 Number 3, 1977
Pages 200-226
[2] "Similarity Indexing: Algorithms and Performance"
D.A White, R Jain
Technical Report 1996, available at "http://vision.ucsd.edu/papers"
^*)