Squarish k-d trees

We modify the k-d tree on [0, 1](d) by always cutting the longest edge inst ead of rotating through the coordinates. This modi cation makes the expecte d time behavior of lower-dimensional partial match queries behave as perfec tly balanced complete k-d trees on n nodes. This is in contrast to a result of Flajolet and Puech [J. Assoc. Comput. Mach., 33 (1986), pp. 371-407], w ho proved that for (standard) random k-d trees with cuts that rotate among the coordinate axes, the expected time behavior is much worse than for bala nced complete k-d trees. We also provide results for range searching and ne arest neighbor search for our trees.