arrays - Algorithm balanced K-D tree with O(kn log n) -

i tried implement balanced k-d tree o(kn log n), used presorted k arrays (sorted arrays each index) o(kn log n), , median balanced tree.

the problem faced median value @ level ,for example median x axis, maybe chosen again @ subsequent level, example y axis.

i tried solve dividing y sorted array 2 arrays using chosen x value pivot, way wouldn't yield balanced tree.

any idea how k-d balanced tree o(kn log n)?

edit

quoted wiki https://en.wikipedia.org/wiki/k-d_tree

alternative algorithms building balanced k-d tree presort data prior building tree. maintain order of presort during tree construction , hence eliminate costly step of finding median @ each level of subdivision. 2 such algorithms build balanced k-d tree sort triangles in order improve execution time of ray tracing three-dimensional computer graphics. these algorithms presort n triangles prior building k-d tree, build tree in o(n log n) time in best case.[5][6] algorithm builds balanced k-d tree sort points has worst-case complexity of o(kn log n).[7] algorithm presorts n points in each of k dimensions using o(n log n) sort such heapsort or mergesort prior building tree. maintains order of these k presorts during tree construction , thereby avoids finding median @ each level of subdivision.

anyone provide such algorithm provided above?

edit

the came way doesn't work if there duplicate value of specific axis median.

for example

x1 = [ (0, 7), (1, 3), (3, 0), (3, 1), (6, 2) ] y1 = [ (3, 0), (3, 1), (6, 2), (1, 3), (0, 7) ]

the median of x-axis 3. when want split array y11 , y12 have use > , < distribute y array left , right considering pivot delimiter.

there no guarantee 1 of them correct if median on specific axis duplicated

consider partition on x axis, , there no problem on x1 array following completion of above example of first step partition:

median=(3,0) pivot = 3 // it's median of x axis y11[],y12[]  for(i = 0 ; < x1.size;i++)   if(y1[i].getx()<pivot)     y11.add(y1[i])   else      if(y1[i].getx()>pivot)      y12.add(y1[i]) 

this result y11 = [(2 ,1) , (1, 3), (0, 7) ] y12 = [ (6,2) ]

any idea how handle such case? or there presorting kd-tree presorting algorithm o(kn log n) ?

to elaborate on comment (and anony-mousse's answer, probably):

the key idea pre-sorting in constructing kd-trees keep order during split. overhead looks quite high, comparative benchmark re-sorting (and k-select) seems in order.
proof-of principle java source code:

package net.*.coder.greybeard.sandbox;  import java.util.arrays; import java.util.comparator; import java.util.linkedlist;  /** finger exercise pre-sorting & split kd-tree construction  *  (re. https://stackoverflow.com/q/35225509/3789665) */ public class kdpresort {  /** k-dimensional key, dimensions fixed   *   number of coordinates in construction */     static class kkey {         public static kkey[] none = {};         final comparable[]coordinates;         public kkey(comparable ...coordinates) {             this.coordinates = coordinates;         }     /** @return {@code comparator<kkey>} coordinate {@code n}*/         static comparator<kkey> comparator(int n) { // cached             return new comparator<kdpresort.kkey>() { @override                     public int compare(kkey l, kkey r) {                         return l.coordinates[n]                             .compareto(r.coordinates[n]);                     }                 };         }         @override         public string tostring() {             stringbuilder sb = new stringbuilder(                 arrays.deeptostring(coordinates));             sb.setcharat(0, '(');             sb.setcharat(sb.length()-1, ')');             return sb.tostring();         }     }   // static boolean trimlists = true; // introduced when arraylist used in interface  /** @return 2 arrays of {@code kkey}s: comparing smaller  *    or equal {@code pivot} (according {@code comp)},  *    , greater pivot -  *    in same order in {@code keys}. */     static kkey[][] split(kkey[] keys, kkey pivot, comparator<kkey> comp) {         int length = keys.length;         arraylist<kkey>             se = new arraylist<>(length),             g = new arraylist<>(length);         (kkey k: keys) {         // pick list add             list<kkey>d = comp.compare(k, pivot) <= 0 ? se : g;             d.add(k);         } //      if (trimlists) { se.trimtosize(); g.trimtosize(); }         return new kkey[][] { se.toarray(kkey.none), g.toarray(kkey.none) };     }  /** @return 2 arrays of <em>k</em> arrays of {@code kkey}s:   *  comparing smaller or equal {@code pivot}   *   (according {@code comp)}, , greater pivot,   *  in same order in {@code keysbycoordinate}. */     static kkey[][][]         splits(kkey[][] keysbycoordinate, kkey pivot, comparator<kkey> comp) {         final int length = keysbycoordinate.length;         kkey[][]             se = new kkey[length][],             g = new kkey[length][],             splits;         (int = 0 ; < length ; i++) {             splits = split(keysbycoordinate[i], pivot, comp);             se[i] = splits[0];             g[i] = splits[1];         }         return new kkey[][][] { se, g };     }  // demo     public static void main(string[] args) {     // https://stackoverflow.com/q/17021379/3789665         integer [][]copairs = {// {0, 7}, {1, 3}, {3, 0}, {3, 1}, {6, 2},                 {12, 21}, {13, 27}, {19, 5}, {39, 5}, {49, 63}, {43, 45}, {41, 22}, {27, 7}, {20, 12}, {32, 11}, {24, 56},             };         kkey[] somekeys = new kkey[copairs.length];         (int = 0; < copairs.length; i++) {             somekeys[i] = new kkey(copairs[i]);         }     //presort         arrays.sort(somekeys, kkey.comparator(0));         list<kkey> x = new arraylist<>(arrays.aslist(somekeys));         system.out.println("by x: " + x);         kkey pivot = somekeys[somekeys.length/2];         arrays.sort(somekeys, kkey.comparator(1));         system.out.println("by y: " + arrays.deeptostring(somekeys));     // split x         kkey[][] allordered = new kkey[][] { x.toarray(kkey.none), somekeys },             xsplits[] = splits(allordered, pivot, kkey.comparator(0));         (kkey[][] c: xsplits)             system.out.println("split x of " + pivot + ": "                 + arrays.deeptostring(c));     // split "higher x" y         pivot = xsplits[1][1][xsplits[1][1].length/2];         kkey[][] ysplits[] = splits(xsplits[1], pivot, kkey.comparator(1));         (kkey[][] c: ysplits)             system.out.println("split y of " + pivot + ": "                 + arrays.deeptostring(c));     } } 

(didn't find suitable answer/implementation on se while not investing energy. output non-convincing example, longer one, had re-format believe it.
code looks ugly, in likelihood because is: if inclined re-read licence of code posted on se, visit code review.) (consider there's voting, accepting, , awarding bounties, , re-visit anony-mousse's answer.)