On Space Information Flow: Single multicast

Departing from Network Information Flow (NIF) that studies network coding in graphs, Space Information Flow (SIF) is a new paradigm that studies network coding in a geometric space. This work focuses on the problem of min-cost multicast network coding in a 2-dimensional Euclidean space. We prove a number of properties of the optimal SIF solutions, and propose a two-phase heuristic algorithm for computing the optimal SIF. The first phase computes the optimal topology through space partitioning that translates the SIF problem into a NIF problem, which is then solved using linear optimization. The second phase computes the min-cost embedding of the SIF topology found in the first phase, by fine tuning the location of each relay node using properties that an optimal SIF must satisfy.