# Decomposition of multidimensional point set

I am trying to use point sets to define the subdivisions of a multidimensional space and use a hash table to store the subvisions. This approach requires decomposing the multidimensional space into multidimensional subdivisions. Each subdivision represents a slot in the hash table and is labelled by a multidimensional hash table index. I need to prove Theorem 1 but I am not sure how to proceed. Any help you could give would be appreciated

==============================================================

Definition 1 Let $[SMIN_d, SMAX_d)$ be the boundary of a space $\pmb{S}$ in $d$ dimension, for $d = 1,2,...,n$.

$\displaystyle \pmb{S} = \{(x_1,x_2,...,x_n) \mid x_d\in \mathbb{R} \wedge SMIN_d\leq x_d < SMAX_d, for \quad d = 1,2,...,n\}.$

Alternatively, $\pmb{S}$ can be expressed as the Cartesian product of its one-dimensional boundaries.

Definition 2 Let $[SMIN_d, SMAX_d)$ be the boundary of a space $\pmb{S}$ in $d$ dimension, for $d = 1,2,...,n$.

$\pmb{S} = [SMIN_1,SMAX_1) \times [SMIN_2,SMAX_2) \times ... \times [SMIN_n,SMAX_n)\\ \quad = \prod^n_{d=1} [SMIN_d,SMAX_d).$

The hashing approach requires decomposing $\pmb{S}$ into uniform subdivisions. Each subdivision represents a slot in the hash table, which is labelled by a multidimensional hash table index. The uniform subdivision is defined as follows:

Definition 3 Let $[SMIN_d, SMAX_d)$ be the boundary of a space in $d$ dimension. The boundary can be uniformly divided into $N_d$ sub-boundaries with unit length $L_d$, such that

$\displaystyle L_d = \frac{SMAX_d - SMIN_d}{N_d}$

$\forall N_d \in \mathbb{Z^+}$, $\forall L_d \in \mathbb{R^+}$, for $d = 1,2,...,n$.

Definition 4 Let $[SMIN_d, SMAX_d)$ be the boundary of a space in $d$ dimension, for $d = 1,2,...,n$. The boundary is uniformly divided into $N_d$ sub-boundaries with unit length $L_d$. The uniform subdivision $\pmb{Z}$ of $\pmb{S}$ is labelled by a multidimensional hash table index $(z_1,z_2,...,z_n)$, such that

$\pmb{Z}(z_1,z_2,...,z_n) = \{(x_1,x_2,...,x_n) \mid x_d\in \mathbb{R} \wedge SMIN_d+z_d L_d\leq x_d < SMIN_d + (z_d + 1)L_d, \qquad{} \qquad{} \qquad{} \qquad{}for \quad d = 1,2,...,n\}$

for $z_d = 0,1,...,N_d-1$.

Similar to all axis-aligned point sets, the uniform subdivision can be express as the Cartesian product of its one-dimensional boundaries, which is given in Definition 5.

Definition 5 Let $[SMIN_d, SMAX_d)$ be the boundary of a space in $d$ dimension, for $d = 1,2,...,n$. The boundary is uniformly divided into $N_d$ sub-boundaries with unit length $L_d$. The uniform subdivision $\pmb{Z}$ of $\pmb{S}$ can be defined as

$\pmb{Z}(z_1,z_2,...,z_n) = [SMIN_1+z_1 L_1,SMIN_1 + (z_1 + 1)L_1)\\ \qquad{}\qquad{}\qquad{}\qquad{} \times [SMIN_2+z_2 L_2,SMIN_2 + (z_2 + 1)L_2) \times ...\\ \qquad{}\qquad{}\qquad{}\qquad{} \times [SMIN_n+z_n L_n,SMIN_n + (z_n + 1)L_n)\\ \qquad{}\qquad{}\qquad{} = \prod^n_{d=1} [SMIN_d+z_d L_d,SMIN_d + (z_d + 1)L_d)$

for $z_d = 0,1,...,N_d-1$.

Theorem 1 Given a set which contains all hash table indices $\pmb{H} = \{(z_1,z_2,...,z_n) \mid z_d = 0,1,...,N_d-1 \wedge d = 1,2,...,n\}$

where $N_d$ is the number of subdivisions of space $\pmb{S}$ in $d$ dimension. Then, $\pmb{S}$ can be expressed as the union of all uniform subdivisions, such that

$\pmb{S} = \bigcup_{k \in \pmb{HI}} \pmb{Z}(k).$

proof

-
Where does the [elementary] set theory kick in? –  Asaf Karagila Apr 10 '12 at 22:37
Transform your set such that $SMIN_d = 0$ and $SMAX_d = 1$, and then express the $k$-th coordinate $x_k$ of a point in your space $S$ in base $N_k$ (or $N_k+1$, I am not sure of your notation). Then, the first digit will coincide with $z_k$ and thus $S = \bigcup_k Z(k)$. –  dtldarek Apr 10 '12 at 22:50
Hi Asaf. I am new to this site, so I apologize if I used the wrong tag. I am trying to prove the set S is the union of the sets Z(k). If this is not an [elementary] set theory problem, can you suggest an alternative? –  Steve M Apr 10 '12 at 22:53