## 2 Construction of Unit Tetrahedron Cells  
We represent a wireless sensor network by a graph, \(G(V,E)\), where the vertices (\(V\)) denote the sensor nodes and the edges (\(E\)) indicate the communication links in the network. **Definition 1**. : _A unit tetrahedron cell (UTC) is a tetrahedron formed by four network nodes, which does not intersect with any other tetrahedrons._  
We let \(UTC(A,B,C,D)\) denote the UTC formed by Nodes \(A\), \(B\), \(C\) and \(D\), which includes four faces, _i.e._, \(Face(A,B,C)\), \(Face\)\((A,B,D)\), \(Face(A,C,D)\) and \(Face(B,C,D)\). The union of all UTCs, called a UTC mesh (see Figure 0(c)), represent the network. A simple algorithm is employed to create a UTC mesh, which starts from any arbitrary tetrahedron that contains its own vertex nodes only. By removing all edges that intersect this tetrahedron, the algorithm yields the first UTC, denoted by \(UTC(A,B,C,D)\). Next, the algorithm expands it to form other UTCs. Based on each face of \(UTC(A,B,C,D)\), such as \(Face(A,B,C)\), the algorithm looks for the common neighbors of Nodes \(A\), \(B\) and \(C\). Let \(E\) be such a common neighbor. Nodes \(A\), \(B\), \(C\) and \(E\) form a valid UTC only if it neither overlaps with any existing UTCs nor contains any other nodes. Multiple such nodes, like \(E\), may exist, and the algorithm arbitrarily chooses one of them to form the new UTC. The algorithm repeats the above procedure, until no new UTC can be formed. Here, we have assumed that no degenerated edges or nodes exist in the network, and any internal hole (as small as a unit cube) has been identified by [29] to ensure the successful establishment of the UTC mesh. Moreover, we assume a node can create a local coordinates system by using local distance information estimated via standard methods [30]. Multiple available schemes are available for creating such a local coordinates system [31; 32; 33; 34]. Our implementation adopts [34] for its efficiency of filtering noises in distance measurement and its tolerance of distance errors. **Definition 2**. : _A Delaunay unit tetrahedron cell (DUTC) is a UTC whose circumsphere contains no other nodes, except its vertices._  
For example, \(UTC(A,B,C,D)\), shown in Figure 3(a), is a DUTC, since its circumsphere contains no nodes, except \(A,B,C\) and \(D\). On the other hand, Figure 3(b) illustrates \(UTC(A,B,C,D)\) that is not a DUTC, because Node \(E\) is inside its circumsphere. Similarly, neither is \(UTC(E,B,C,D)\) a DUTC. Note that the UTCs constructed by the algorithm introduced above are not necessarily DUTCs. **Definition 3**. : _A face is a boundary face if it is contained in one UTC only._  
**Definition 4**. : _A UTC is a boundary UTC if it contains at least one boundary face. A non-boundary UTC is call an internal UTC._  
**Definition 5**. : _A hole of a network is formed by a closed surface that consists of boundary faces. The outer boundary of the network is considered as a special hole._  
For example, a set of boundary faces are highlighted in magenta in Figure 1c, which, together, form the surface of the hole. **Definition 6**. : _Two UTCs are neighbors if and only if they share a face._  
Apparently, a \(UTC\) has at most four neighboring \(UTCs\). Similarly, we have:  
**Definition 7**. : _Two faces are neighbors if and only if they share an edge._  
**Definition 8**. : _Node \(i\) is greedily reachable to Node \(j\) if a packet can be greedily routed from the former to the latter based on a metric that is kept locally and consumes constant storage space._  
Our objective is to enable greedy routing from any source to any destination in a given sensor network. More specifically, we aim to map an arbitrary 3D sensor network to a greedily reachable network, as defined below:  
**Definition 9**. : _A network is called a greedily reachable network if every two nodes in the network are greedily reachable to each other._  
Based on the above definitions, we next discuss how to enable a greedily reachable network.