Kd-Tree Question

Question

I am trying to implementation and understand KdTree, Following is the link I found. http://ldots.org/kdtree/#buildingAkDTree But I fail to understand following algorithm

tuple function build_kd_tree(int depth, set points):
    if points contains only one point:
        return that point as a leaf.

    if depth is even:
        Calculate the median x-value.
        Create a set of points (pointsLeft) that have x-values less than
            the median.
        Create a set of points (pointsRight) that have x-values greater
            than or equal to the median.
    else:
        Calculate the median y-value.
        Create a set of points (pointsLeft) that have y-values less than
            the median.
        Create a set of points (pointsRight) that have y-values greater
            than or equal to the median.

    treeLeft = build_kd_tree(depth + 1, pointsLeft)
    treeRight = build_kd_tree(depth + 1, pointsRight)

    return(median, treeLeft, treeRight)

I do not understand what is the meaning of Calculate the median x-value.

Answer 1

Your points have x and y values. The median of x values can be obtained by sorting by x, then taking the middle element's x (for an odd number of points) or the mean of the two middle points' x (for an even number of points).

Alternatively, use a fast selection algorithm such as median-of-medians.