# Urban Free-Space Optical Network Optimization
## 2 Problems Statement  
This section presents the main optimization problems related to the construction of FSO networks. A core component in any FSO-related problem is the _visibility graph_[14; 28; 29], in which a vertex (node) represents a point on the terrain, and an edge represents a link between two points with LOS between them. Herein, an FSO graph is defined as a visibility graph with red and blue vertices [26]. Next, we present five optimization problems of interest in the context of constructing FSO networks, followed by some required definitions and models:  
1. Given a visibility graph, find the spanning tree (network) with maximum endpoints (leaves). 2. Given an FSO graph, find the network with minimum intermediate points that connects all terminal points. 3. Given an FSO graph with positive-weighted vertices, find the network with minimum overall node cost that connects all terminal points. 4. Given an FSO graph with positive-weighted edges, find the network with the minimum overall edge cost that connects all terminal points. 5. Given an FSO graph with positive-weighted vertices and edges, find the network with the minimum overall (combined node and edge) cost that connects all terminal points. To formalize the above problems, we define the following preliminaries. * Terrain: \(\tau\), 2-dimensional (D) function from \((x,y)\to z\) where \((x,y)\) is the location on the terrain and \(z\) is the height of this point. * Building \(P\): a 2.5D polygon on the terrain with height from the ground. * Line of sight: Between two buildings, there is LOS (i.e., visibility) if and only if there is a straight line between them that does not intersect any other building on the terrain. * City map: Subcase of a terrain that represents an urban canyon (2.5D polygons). In this work, we consider the ground to be flat terrain and the buildings to be of rectangular shape, each with a positive height \(z\) from the ground. * Terminal points, denoted as \(B\): The subset of buildings that require communication (blue vertices). * Intermediate points, denoted as \(R\): The set of all buildings that are not \"blue\" and on which a communication facility can be positioned (red vertices). * Sink (root): A communication source point for the terminal points. In general, there might be a few sinks that, combined, should supply all the city's communication demands. However, we mainly consider the case of a single source. * \(FSO_{link}\) function: FSO communication requires a clear LOS. Two buildings may have an FSO link between them if there is visibility between rooftops and the distance between them is below some maximum value. Thus, we define a binary function \(FSO_{link}(p_{i},p_{j})\rightarrow\{1\}\) if \(p_{i}\), \(p_{j}\) satisfy the function requirements, \(0|else\), where the function requirements are as follows. * LOS exists: No third building blocks the LOS between \(p_{i}\) and \(p_{j}\). * Distance: The distance between these buildings is not longer than a predefined maximal range. We now define the main graph model used in this paper, the FSO visibility graph model. The visibility graph is an undirected graph defined by the binary function \(FSO_{link}\). The following types of simple graph models enable us to define our problems of interest (Figure 1), demonstrating the visibility graph on a group of buildings. * Let \(G_{v}=(V,E)\) be a visibility graph, which is an undirected graph. This graph is defined by the binary function \(FSO_{link}\) on a terrain \(\tau\), where each vertex represents a building. * Let \(G_{rb}=(B,R,E)\) be a red-blue visibility graph. In this graph, \(B\) is a set of terminal points and \(R\) is a set of intermediate points. The edges in this graph are defined as follows. For every \(u,v\in R\bigcup B\), \(e=\{u,v\}\in E\) if and only if \(FSO_{link}(p_{u},p_{v})=1\), where \(p_{u},p_{v}\) are the buildings represented by \(u\) and \(v\), respectively. * Let \(G_{b}\) be a \(G_{rb}\), where \(R=\mathcal{O}\) (all vertices are blue).