We present an algorithm for solving the nearest neighbor problem with respect to $L_{\infty}$-distance. It requires no preprocessing and storage only for the point set $P$. Its average runtime assuming that the set $P$ of $n$ points is drawn randomly from the unit cube $[0,1]^{d}$ under uniform distribution is essentially $\Theta (nd/ln\; n)$ thereby improving the brute-force method by a factor of $\Theta (1/ln\; n)$. Several generalizations of the method are also presented, in particular to other “well-behaved” probability distributions and to the important problem of finding the $k$ nearest neighbors to a query point.

This paper investigates reduced ordered binary decision diagrams (OBDD) of partially symmetric Boolean functions when using variable orders where symmetric variables are adjacent. We prove upper bounds for the size of such symmetry ordered OBDDs (SymOBDD). They generalize the upper bounds for the size of OBDDs of totally symmetric Boolean functions and nonsymmetric Boolean functions proven by M.A. Heap and M.R. Mercer (1994) and I. Wegener (1984). Experimental results based on these upper bounds show that the nontrivial symmetry sets of a Boolean function should be located either right up at the beginning or right up at the end of the variable order in order to obtain best upper bounds.

This paper investigates the sizes of symmetric variable order based reduced binary decision diagrams for partially symmetric Boolean functions. It gives exact bounds for the maximum number of nonterminal vertices for the cases that the set of symmetric variables is treated as block which is located either at the front or at the back of the variable order.