# The Rectilinear Steiner Forest Arborescence problem

###### Abstract

Let $r$ be a point in the first quadrant $Q_{1}$ of the plane $\mathbb{R}^{2}$
and let $P\subset Q_{1}$ be a set of points such that for any $p\in P$, its
$x$\- and $y$-coordinate is at least as that of $r$. A rectilinear Steiner
arborescence for $P$ with the root $r$ is a rectilinear Steiner tree $T$ for
$P\cup\\{r\\}$ such that for each point $p\in P$, the length of the (unique)
path in $T$ from $p$ to the root $r$ equals $({\rm x}(p)-{\rm x}(r))+({\rm
y}(p))-({\rm y}(r))$, where ${\rm x}(q)$ and ${\rm y}(q)$ denote the $x$\- and
$y$-coordinate, respectively, of point $q\in P\cup\\{r\\}$.

Given two point sets $P$ and $R$ lying in the first quadrant $Q_{1}$ and such
that $(0,0)\in R$, the Rectilinear Steiner Forest Arborescence (RSFA) problem
is to find the minimum-length spanning forest $F$ such that each connected
component $F$ is a rectilinear Steiner arborescence rooted at some root in
$R$. The RSFA problem is a natural generalization of the Rectilinear Steiner
Arborescence problem, where $R=\\{(0,0)\\}$, and thus it is NP-hard. In this
paper, we provide a simple exact exponential time algorithm for the RSFA
problem, design a polynomial time approximation scheme as well as a fixed-
parameter algorithm.

THE RECTILINEAR STEINER
FOREST ARBORESCENCE PROBLEM

Łukasz Mielewczyk
Institute of Informatics
University of Gdańsk, 80-308 Gdańsk, Poland
<EMAIL_ADDRESS>
Leonidas Palios
Department of Computer Science and Engineering
University of Ioannina, GR-45110 Ioannina, Greece
<EMAIL_ADDRESS>
Paweł Żyliński
Institute of Informatics
University of Gdańsk, 80-308 Gdańsk, Poland
<EMAIL_ADDRESS>
Keywords:
aaarectilinear Steiner arborescence
aaadynamic programming
aaaexact algorithm
aaaPTAS
aaaFPT

AMS subject classifications: 68W25, 68Q25

##  1 Introduction

A rectilinear graph $G=(V(G),E(G))$ is a plane graph with (weighted) edges
corresponding to horizontal or vertical line segments that connect two
vertices in the plane $\mathbb{R}^{2}$, intersecting only at their endpoints.
The weight $l(e)$ of an edge $e\in E(G)$ is equal to the length of the segment
it corresponds to, the weight of $G$, denoted by $l(G)$, is defined as the sum
of all edge weights in $G$, and the union of all the line segments (edges) in
$G$, regarded as a point set, is denoted by ${\rm Un}(G)$.111However,
sometimes, we shall leave the notation ${\rm Un}(\cdot)$ out, when this does
not lead to misunderstanding. A rectilinear Steiner tree for a set $P$ of
points in the plane is a rectilinear acyclic graph such that each point in $P$
is an endpoint of some edge in the tree.

Let $r$ be a point in the first quadrant $Q_{1}$ of the plane $\mathbb{R}^{2}$
and let $P\subset Q_{1}$ be a set of points such that for any $p\in P$, its
$x$\- and $y$-coordinate is at least as that of $r$. A rectilinear Steiner
arborescence (RSA) for $P$ with the root $r$ is a rectilinear Steiner tree $T$
for $P\cup\\{r\\}$ such that for each point $p\in P$, the length of the
(unique) path in $T$ from $p$ to the root $r$ equals $({\rm x}(p)-{\rm
x}(r))+({\rm y}(p))-({\rm y}(r))$, where ${\rm x}(q)$ and ${\rm y}(q)$ denote
the $x$\- and $y$-coordinate, respectively, of point $q\in P\cup\\{r\\}$. A
minimum rectilinear Steiner arborescence (MRSA) for $P$ with the root $r$ is
an RSA for $P$ with the root $r$ that has the minimum weight $l(\cdot)$ over
all RSA’s for $P$ (with the root $r$).

The problem of determining the minimum rectilinear Steiner arborescence —
having applications in the field of performance-driven VLSI design [12, 13] —
was first studied by Nastansky et al. [38] who proposed an integer programming
formulation with exponential time complexity. In 1979, Laderia de Matos [29]
proposed an exponential time dynamic programming algorithm. In 1985, Trubin
[45] claimed that the problem is polynomially solvable, however, in 1992, Rao
et al. [41] showed Trubin’s algorithm to be incorrect; Rao et al. also
provided a simple greedy 2-approximation for this problem, with $O(n\log n)$
running time, and their result was extended by Cordova and Lee [14] to the
more general case where points can be located in all four quadrants, with the
root located at the origin of $\mathbb{R}^{2}$. Another fast
$2$-approximation, even in the presence of obstacles, was presented by Ramanth
[40]. Some other optimal exponential time algorithms can be found in [24, 30],
and some heuristics in [1, 12, 44]. More recently, [31, 47] presented
polynomial time approximation schemes for the problem, and the NP-hardness of
the problem was shown by Shi and Su [42]. In addition, Fomin et al. [19]
proposed the first subexponential algorithm for the problem, inspired by the
work of Klein and Marx [27], who obtained a subexponential algorithm for
Subset Traveling Salesman Problem on planar graphs. The depth-restricted
variant of the rectilinear Steiner arborescence problem was studied by Maßberg
in [32], and the angle-restricted Steiner arborescence problem was studied in
[6, 46]. Finally, a more general problem, the Generalized Minimum Manhattan
Network problem, was defined by Chepoi et al. [9] and then studied in [16,
36].

### The rectilinear Steiner arborescence with the prespecified sub-RSA.

From a practical point of view, in real life, when considering optimization
problems, we sometimes have to deal with scenarios in which we want to
temporarily add extra points without however modifying the solution that we
already had. Therefore, it is natural to consider such a scenario for the RSA
problem as well.

Suppose that we are given a (not necessarily minimum) rectilinear Steiner
arborescence $T$ for a point set $P$ with the root $r$, so-called prespecified
sub-RSA, and let $P^{\ast}$ be a set of points in the bounding box ${\rm
BB}(T)$ of $T$; w.l.o.g. we assume that none of the points in $P^{\ast}$ lies
on an edge of $T$. Now, we would like to connect the new points in $P^{\ast}$
to the arborescence $T$, thus getting a (rectilinear) arborescence for all
points in $P\cup P^{\ast}$ (see Fig. 1). Formally, we are interested in
computing the minimum rectilinear Steiner arborescence $T^{\ast}$ for $P\cup
P^{\ast}$ with the root $r$ such that ${\rm Un}(T)\subset{\rm Un}(T^{\ast})$.

${\rm BB}(T)$$T$

Fig. 1. The RSA problem with the prespecified sub-RSA:

an optimal solution is marked with gray.

The above problem formulation is natural, however, when we start with
examining some basic properties of an (optimal) solution $T^{\ast}$ (Lemma 1.1
and discussion below it), we are driven to a property which motivates us to
introduce a more natural and general problem: the Rectilinear Steiner Forest
Arborescence problem which we shall discuss in the next paragraph.

### The rectilinear Steiner forest arborescence.

Let us start with some definitions. Let $T=(V(T),E(T))$ be a rectilinear
Steiner arborescence for a point set $P$ with the root $r=(0,0)$ in the plane
and let $P^{\ast}$ be a set of points in the bounding box ${\rm BB}(T)$ of
$T$. For a vertex $v\in V(T)$, let $\deg_{T}(v)$ denote the degree of $v$ in
$T$, that is, the number of edges in $E(T)$ that $v$ is incident to. A vertex
$v\in V(T)$ is called essential if either $\deg_{T}(v)=1$ or $\deg_{T}(v)=2$
and its two adjacent edges (segments) are not parallel; notice that since $T$
is an RSA, it may have degree 2 vertices that are not essential. For a point
$p\in P^{\ast}\cup V(T)$, define its right extension as the maximal horizontal
line segment $l$ with the left endpoint at $p$ such that $l$ has no points in
common, except its endpoints, with ${\rm Un}(T)$ and the boundary of ${\rm
BB}(T)$; the left, upward and downward extensions, respectively, of $p$ are
defined analogously, see Fig. 1(a) for an illustration. Notice that an
extension may degenerate to a single point.

(a)$v$$1$$2$$2$$1$$4$$3$$3$

(b)

Fig. 2. (a) An illustration of the left (1), upward (2), right (3) and
downward (4) extensions. Notice that the downward extension of $v$ degenerates
to a single point. (b) The subgrid ${\rm H}(T,P^{\ast})$.

Let ${\rm H}(T,P^{\ast})$ be the subgrid consisting of all points of (i) the
boundary of the bounding box ${\rm BB}(T)$, (ii) the edges of $T$, (iii) all
extensions of all points in $P^{\ast}$, and (iv) only right and upward
extensions of all essential vertices of $T$; see Fig. 1(b) for an
illustration. We have the following lemma.

Lemma 1.1.  There exists a minimum rectilinear Steiner arborescence for $P\cup
P^{\ast}$ with the root $r$ and with the prespecified sub-RSA $T$ for $P$ with
the root $r$ such that it uses only subsegments of the grid ${\rm
H}(T,P^{\ast})$.

Proof. It follows by arguments similar to those in the proof of Lemma 3 in
[15]. Namely, let $F$ be a minimum rectilinear Steiner arborescence for $P\cup
P^{\ast}$ with the root $r$ and with the pre-specified sub-RSA $T$ for $P$
with the root $r$. Suppose now that $F$ does not use only subsegments of the
grid ${\rm H}(T,P^{\ast})$. The idea is to move the solution into ${\rm
H}(T,P^{\ast})$ by repeating the following steps. While there exists a
vertical edge of $F$ not lying on ${\rm H}(T,P^{\ast})$, pick a vertical path
$\pi\subseteq{\rm Un}(F)$ of maximum length that does not lie on the grid.
Observe that by minimality of $F$, it follows that $\pi$ does not cross an
edge of $T$. Since the number of horizontal edges touching $\pi$ from the left
is at most one (by minimality of $F$) and the number of horizontal edges
touching $\pi$ from the right is at least one, move $\pi$ to the right (by
creating and/or extending a left edge and shortening all right edges) until
$\pi$ is no longer a vertical path of maximal length (and so overlaps with
another vertical path) or $\pi$ reaches the grid ${\rm H}(T,P^{\ast})$.
Clearly, this will not increase the length of $F$. Finally, eliminate
horizontal paths not lying on the grid ${\rm H}(T,P^{\ast})$ in the same way.
$\Box$

(a)

(b)

Fig. 3. (a) Grey points constitute the set $R$ of roots: essential vertices of
the pre-specified RSA and all essential endpoints of the left/downward
extensions of points in $P^{\ast}$. (b) The RFSA problem corresponding to the
RSA problem with the pre-specified RSA in Fig. 1.

The left endpoint of the left extension (resp. the bottom endpoint of the
downward extension) of a point $p\in P^{\ast}$ is called essential if it is a
point of ${\rm Un}(T)$, that is, it lies on an edge of $T$. Let $R$ be the set
of all essential vertices of $T$ and all essential endpoints of the
left/downward extensions of points in $P^{\ast}$ (see Fig. 1(a)); notice that
$|R|=O(|P^{\ast}|+|V(T)|)$. Taking into account the above lemma, one can
observe that there exists an optimal solution $T^{\ast}$, that is, a minimum
rectilinear Steiner arborescence $T^{\ast}$ for $P\cup P^{\ast}$ with the root
$r$ and with the pre-specified sub-RSA $T$ for $P$ (with the root $r$), such
that each point in $P^{\ast}$ is connected to $T$ with an rectilinear path
whose one endpoint is in $R$. And so, rather then considering the pre-
specified rectilinear Steiner arborescence $T$, in particular, its edge set
$E(T)$, we may restrict ourselves only to the set $P^{\ast}$ of points and, as
possible roots, to the set of all points in $R$. This observation is crucial,
and hence we introduce the following general problem (see Fig. 1(b)).

The Rectilinear Steiner Forest Arborescence (RSFA) problem.

Given two disjoint sets $P$ and $R$ of $n$ points and $m$ roots, respectively,
lying in the first quadrant of $\mathbb{R}^{2}$ and such that $(0,0)\in R$,
find the minimum rectilinear spanning forest $F$, called a rectilinear Steiner
forest arborescence for $P$ with the root set $R$, such that each of connected
components of $F$ is an RSA rooted at some root in $R$, that is, for each
point $p\in P$, there exists a root $r\in R$ and a path $\pi$ in $F$ such that
the length of $\pi$ is equal to $({\rm x}(p)-{\rm x}(r))+({\rm y}(p)-{\rm
y}(r))$.

As alluded above, our restatement of the problem definition asymptotically
preserves the size of the input, and thus, any efficient algorithm for the
RSFA problem can be applied to the RSA problem with the pre-specified sub-RSA,
the problem defined formerly. Next, since the RSA problem is a special case of
the RSFA problem where $R=\\{(0,0)\\}$, bearing in mind [42], we immediately
obtain the NP-hardness of the RSFA problem.

Corollary 1.2.  The RSFA problem is NP-hard.

It is worth pointing out that a restricted variant of the RSFA problem, called
the $(1,k)$-MRDPT problem (the Minimum Cost Rectilinear Distance Preserving
Tree problem), where $k$ is the number of non-root input points, has been
studied in [44], for the purpose of a new efficient heuristic for the four-
quadrant RSA problem. In this variant, we have one “independent” layer of
roots and several independent points in a second layer. And, based upon
dynamic programming, Téllez and Sarrafzadeh provided a quadratic time
algorithm that optimally solves the $(1,k)$-MRDPT problem; see [44] for more
details.

### Our contribution.

In this paper, we rely on Corollary 1.1 and the algorithmic results for the
RSA problem [7, 30, 31] in order to provide an exact exponential time
algorithm (Section 2), to propose a PTAS (Section 3) and an FPT algorithm
(Section 4). Finally, some future improvements as well as some open problems,
related to Manhattan networks, are discussed.

### Notation.

Unless otherwise stated, all points lie in the first quadrant of
$\mathbb{R}^{2}$ and the origin $(0,0)$ always belongs to the root set $R$.
For a point $p$, $||p||$ denotes the sum of coordinates ${\rm x}(p)+{\rm
y}(p)$, while the nearest root in $R$ that covers $p$ (ties are broken
arbitrarily) is denoted by $r(p)$; notice that if $p$ is a root itself, then
$r(p)=p$. For two points $p$ and $q$, the shortest distance between two points
$p$ and $q$ (distances are measured in the $L_{1}$-metric) is denoted with
${\rm dist}(p,q)$, the point with coordinates $(\min\\{{\rm x}(p),{\rm
x}(q)\\},\min\\{{\rm y}(p),{\rm y}(q)\\})$ is denoted with $\langle
p,q\rangle$, and a point $p$ is said to cover $q$ if and only if ${\rm
x}(p)\leq{\rm x}(q)$ and ${\rm y}(p)\leq{\rm y}(q)$. Finally, we shall use an
abbreviation RSFA for a rectilinear Steiner forest arborescence.

##  2 Exact algorithm

In 1992, Ho et al. presented an $O(n^{2}\,3^{n})$ time algorithm for the
problem of determining a minimum rectilinear Steiner arborescence of $n$
points in the plane [24]. Their algorithm is based upon a dynamic programming
approach, it originates a classical algorithm for the minimum Steiner tree
problem in [18], and as we show below, its time complexity can be slightly
improved to $O(3^{n})$, which then leads to an exponential time algorithm that
optimally solves the RSFA problem in $O(mn^{2}+3^{n})$ time, where $n$ and $m$
is the number of input points and roots, respectively.

Let $o=(0,0)$ be the origin, let $P$ be a set of $n$ points in the first
quadrant $Q_{1}$ of the plane (excluding the origin $o$). For a non-empty
subset $X\subseteq P$, let $r(X)=(\min_{p\in P}{\rm x}(p),\min_{p\in P}{\rm
y}(p))$ denote its local root. We observe that the local root $r(X)$ of $X$
can be determined in $\Theta(|X|)$ time, and hence all the subsets of $P$
together with their local roots can be determined in total
$O(n\,2^{n})=O(3^{n})$ time, in the preprocessing step. (On the other hand,
notice that although there are $2^{n}$ subsets of $P$, there are only
$O(n^{2})$ distinct roots in total.) Next, let $A(X)$ denote the minimum
rectilinear Steiner arborescence for $X$ with the root $r(X)$. Now, following
[24], taking into account the definition of the local root, we observe that
the length $l(A(X))$ can be expressed by the following dynamic programming
recursion (Bellman equation).

$l(A(X))=\left\\{\begin{array}[]{ll}0&\textnormal{if }|X|=1;\\\
\min_{\,U\varsubsetneq X}\ l(A(U))+{\rm dist}(r(X),r(U))&\\\
{\color[rgb]{1,1,1}\min_{\,U\varsubsetneq X}}+l(A(X\setminus U))+{\rm
dist}(r(X),r(X\setminus U))&\textnormal{otherwise.}\end{array}\right.$

We tabulate the values $l(A(X))$ with respect to the increasing size of $X$:
handling the case $|X|=1$ requires $O(1)$ time, while for $|X|\geq 2$,
evaluation of $l(A(X))$ requires consideration of $O(2^{|X|})$ choices of $U$
in evaluating the recursion. Thus, the overall running time is

$\sum_{k=1}^{n}\left[{n\choose k}\cdot 2^{k}\cdot O(1)\right]=O(3^{n}).$

Finally, to determine the optimal RSA $A_{o}(P)$ for $P$ with the root
$o=(0,0)$, all we need is to observe that $l(A_{o}(P))=l(A(P))+{\rm
dist}(o,r(P))$. Therefore, we may conclude that the RSA problem (in the first
quadrant $Q_{1}$ of the plane) can be solved in $O(3^{n})$ time.

Next, let $P$ and $R$ be two disjoint sets of $n$ points and $m$ roots,
respectively, all lying in the first quadrant of $\mathbb{R}^{2}$ and such
that $(0,0)\in R$. For a subset $X\subseteq P$, let $F(X,R)$ denote an optimal
rectilinear Steiner forest arborescence for $X$ with the root set $R$;
clearly, we are interested in determining $F(P,R)$. Let $H=H(P\cup R)$ be the
Hanan grid of $P\cup R$, that is, the grid formed by the vertical and
horizontal straight lines passing through all points in $P\cup R$ [23]; notice
that each point in $P\cup R$ corresponds to some intersection grid point of
$H$.

Lemma 2.1.  There exists an optimal RSFA for $X$ with the root set $R$ such
that it uses only subsegments of the Hanan grid $H(X\cup R)\subseteq H(P\cup
R)$.

Proof. It follows by arguments similar to those in the proof of Lemma 1.1; we
omit details. $\Box$

Taking into account the above lemma, the idea of our dynamic programming
approach is as follows. First, for each possible location $q$ of the local
root of a subset of $P$, we determine (and tabulate) the root $r(q)\in R$ and
the distance ${\rm dist}(q,r(q))$. Notice that since the coordinates of such
local root are defined by the relevant $x$\- and $y$-coordinates of at most
two points in $P$, there are at $O(n^{2})$ possible locations for roots, and
so this step can be done in $O(mn^{2})$ time. Next, for each non-empty subset
$X$ of $P$, we determine (and tabulate) the minimum rectilinear Steiner
arborescence $A(X)\subset H(X)$ for $X$ with the root $r(X)$; following the
above approach for the RSA problem, this can be done in total $O(3^{n})$ time.
We also determine (and tabulate) the minimum rectilinear Steiner arborescence
$F^{\ast}(X,R)\subset H(X\cup R)$ for $X$ with the root $r(r(X))\in R$; this
can be done in $O(2^{n})$ time (since we have already tabulated all $A(X)$’s).

Now, having tabulated all the above data, for each point $p\in P$, we set
$l(F(\\{p\\},R))\doteq{\rm dist}(p,r(p))$ and set $F(\\{p\\},R)$ as any
shortest path realizing $l(F(\\{p\\},R))$ within $H(\\{p\\}\cup R)$; this
takes $O(n)$ time (since the local root $r(\\{p\\})=p$ and we have already
computed ${\rm dist}(r(\\{p\\}),r(p))$ in the first step). Assume now that for
any at most $k$-element subset $Y$ of $P$, $1\leq k<n$, we have already
computed and stored $F(Y,R)$. Let $Z$ be a $(k+1)$-element subset of $P$.
Observe that $F(Z,R)$ either consists of one connected component (and so
$F(Z,R)=F^{\ast}(Z,R)$) or has at least two connected components (and so
$F(Z,R)=F(Z_{1},R)\cup F(Z_{2},R)$ for some partition $Z_{1}\cup Z_{2}$ of
$Z$). In particular,

$l(F(Z,R))=\min\\{l(F^{\ast}(Z,R),)\min_{Y\subsetneq
Z}(l(F(Y,R))+l(F(Z\setminus Y,R))\\}.$

Since determining $\min_{Y\subsetneq Z}(l(F(Y,R))+l(F(Z\setminus Y,R))\\}$
takes $O(2^{k+1})$ time, the overall time complexity of our approach for
determining $F(P,R)$ is

$O(mn^{2})+O(3^{n})+O(2^{n})+O(n)+\sum_{k=2}^{n}\left[{n\choose k}\cdot
2^{k}\cdot O(1)\right]=O(mn^{2}+3^{n}).$

Therefore, we may conclude with the following theorem.

Theorem 2.2.  The RSFA problem can be solved in $O(mn^{2}+3^{n})$ time.

Note that if the number $n$ of points is $O(\log m)$, we obtain a polynomial
time algorithm for the RSFA problem.

##  3 Polynomial time approximation scheme

A standard approach for approximation algorithms for geometric optimization
problems builds on the techniques developed for polynomial-time approximation
schemes (PTAS) for geometric optimization problems due to Arora [2] and
Mitchell [35]. In the former approach, to obtain a
$(1+\epsilon)$-approximation in $n^{O(1/\epsilon)}$ time, the instance is
first scaled and perturbated to vertices of a polynomial-size integer grid.
Next, the grid is recursively partitioned into dissection squares using a
quadtree of logarithmic depth, and the so-called Structure Theorem is proved,
which guarantees the existence of an almost-optimal solution that crosses the
boundary of each dissection square only a few times and only in a number
(depending on $\frac{1}{\epsilon}$) of pre-specified portals. Finally, to find
a solution satisfying the Structure Theorem, dynamic programming is employed
over the recursive decomposition, and by introducing the concept of portals,
the running time becomes $n^{c}(\log n)^{O(\frac{1}{\epsilon})}$, where $n$ is
the size of an input instance, $\epsilon$ is any given constant
$0<\epsilon<1$, and $c$ is a constant.

In particular, Arora’s method has been successfully applied to solve the RSA
problem [31, 47], but without the portal technique and thus obtaining a
$(1+\epsilon)$-approximation only in $n^{O(1/\epsilon)}$ time.222As observed
in [10], the portal technique seems to be non-applicable to a class of
optimization problems with the ,,monotone path” requirement. It is natural
then to try to apply this technique for the RSFA problem as well. However, an
instance depicted in Fig. 3 shows that rounding in Arora’s technique may
result to optimal solutions that cannot be transformed to the sub-optimal one
for the original input, by a small relative cost increase. Consequently,
rather then taking an effort in adapting Arora’s technique, we make use of the
latter aforementioned method, that is, the idea of $c$-guillotine subdivisions
proposed by Mitchell [35], which has been also successfully applied to the
symmetric rectilinear Steiner arborescence problem [8].333The difference
between the RSA problem and its symmetric variant is that in the latter one,
the constraint for a path from a point in $P$ to the root is weaker, namely,
such a path must be only $y$-monotone [39]; in the RSA problem, such a path
must be both $x$\- and $y$-monotone.

(a)pointrootthe optimalsolution for MRSFA$\cdots$$\vdots$

(b)$\cdots$$\vdots$

Fig. 4. Rounding may result in the perturbated instance whose optimal solution
for the RSFA problem cannot be transformed to the sub-optimal one for the
original input, by a small relative cost increase. (b) In the perturbated
instance of (a), the non-root (perturbated) points coincides with the
(perturbated) root, so the cost of optimal solution for the perturbated
instance is $0$.

We follow most of the notation of [33, 34, 35]. Let $G=(V(G),E(G))$ be a
rectilinear graph, inducing a rectilinear polygonal subdivision of the plane.
Without loss of generality, assume that $G$ is restricted to the unit square
$B$, i.e. ${\rm Un}(G)\subseteq{\rm int}(B)$. (Then, each facet ($2$-face) of
$G$ is a bonded rectilinear polygon, possibly with holes.) Let $W$ be a closed
axis-aligned rectangle such that $W\subseteq B$ (we shall refer to $W$ as a
window), and let $l$ be a axis-aligned line such that $l\cap{\rm
int}(W)\neq\emptyset$ (we shall refer to $l$ as a cut for $G$ with respect to
$W$). The intersection $l\cap{\rm int}(W)\cap{\rm Un}(G)$ consists of a
(finite) number of subsegments of $l$. (Some of these “segments” may
degenerate to a single point when $l$ crosses an edge of $G$.) The endpoints
of these subsegments are called the endpoints along $l$ (with respect to $W$);
we emphasize that the two points where $l$ crosses the boundary of $W$ are not
considered to be endpoints along $l$.

$W$$l$

$p_{1}$$p_{2}$$p_{3}$$p_{\xi(l)-2}$$p_{\xi(l)-1}$$p_{\xi(l)}$$l\cap{\rm
Un}(G)$($\xi(l)=6$)

$p_{1}$$p_{\xi(l)}$$\sigma_{1}(l)$$\sigma_{4}(l)=\sigma_{5}(l)=\ldots=\emptyset$

$p_{2}$$p_{\xi(l)-1}$$\sigma_{2}(l)$

$p_{3}$$p_{\xi(l)-2}$$\sigma_{3}(l)$

Fig. 5. Definition of the $k$-span.

Let $\xi(l)$ be the number of endpoints along $l$ and let
$p_{1},\ldots,p_{\xi(l)}$ be the endpoints along $l$, ordered downward. For a
positive integer $k$, we define the $k$-span, denoted by $\sigma_{k}(l)$, of
$l$ with respect to $W$ as follows (see Fig. 3 for an illustration). If
$\xi(l)\leq 2(m-1)$, then $\sigma_{k}(l)\doteq\emptyset$; otherwise,
$\sigma_{k}(l)$ is defined to be the (possibly zero-length) line segment
$p_{k}p_{\xi(l)-k+1}$. Now, we say that $l$ is an $k$-perfect cut with respect
to $W$ if $\sigma_{k}(l)\subseteq{\rm Un}(G)$, see Fig. 3. Notice that if
$\xi(l)\leq 2(m-1)$, then $l$ is trivially a $k$-perfect cut as
$\sigma_{k}(l)=\emptyset$, and if $\xi(l)=2m-1$, then $l$ is $k$-perfect as
$\sigma_{k}(l)$ is a single point.

$W$$l_{2}$$l_{1}$$l_{3}$$l_{4}$

Fig. 6. The vertical cuts $l_{1},l_{2},l_{3},l_{4}$ are $3$-perfect (also $k$
perfect, $k\geq 4$).

The cut $l_{4}$ is also $2$-perfect but not $1$-perfect.

Following the above definitions, we say that $G$ is a $k$-guillotine
subdivision with respect to a window $W$ if either (1) $V(G)\cap{\rm
int}(W)=\emptyset$ or (2) there exists a $k$-perfect cut $l$ with respect to
$W$ such that $G$ is a $k$-guillotine subdivision with respect to windows
$W\cap H^{+}$ and $W\cap H^{-}$, where $H^{+}$ and $H^{-}$ are the closed
half-planes induced by the cut $l$. Finally, we say that $G$ is a
$k$-guillotine subdivision if $G$ is a $k$-guillotine subdivision with respect
to the unit square $B$.

Theorem 3.1. [33] Let $G$ be a rectilinear graph. Then, for any integer $k\geq
1$, there exists a $k$-guillotine subdivision $G_{k}$ such that
$l(G_{k})\leq(1+\frac{1}{k})\,l(G)$ and ${\rm Un}(G)\subseteq{\rm Un}(G_{k})$.

Let $F_{\rm OPT}$ be a minimum rectilinear Steiner forest arborescence for an
$n$-point set $P$ with an $m$-root set $R$, both lying in the first quadrant
of $\mathbb{R}^{2}$ and such that $(0,0)\in R$. By the above theorem, $F_{\rm
OPT}$ can be converted to a $k$-guillotine subdivision $F_{k}$ without
increasing its length by much and such that ${\rm Un}(G)\subseteq{\rm
Un}(G_{k})$. In particular, in the resulting subdivision $F_{k}$, for each
point $p\in P$, there exists a root $r\in R$ and a path $\pi$ in $F_{k}$ such
that the length of $\pi$ is equal to $({\rm x}(p)-{\rm x}(r))+({\rm y}(p)-{\rm
y}(r))$. On the other hand, if $G$ is a $k$-guillotine (rectilinear)
subdivision such that for each point $p\in P$, there exists a root $r\in R$
and a path $\pi$ in $G$ such that the length of $\pi$ is equal to $({\rm
x}(p)-{\rm x}(r))+({\rm y}(p)-{\rm y}(r))$, then $G$ can be converted into a
rectilinear Steiner forest arborescence $F_{G}$ for $P\cup R$ of length
$l(F_{G})\leq l(G)$, in a simple greedy manner, be deleting some edges.
Moreover, by minimality of $l(G)$, we have $l(F_{G})\leq l(F_{k})$. Therefore,
using the recursive structure of a $k$-guillotine subdivisions, the idea is to
find a minimum-length $k$-guillotine (rectilinear) subdivision $G$ such that
for each point $p\in P$, there exists a root $r\in R$ and a path $\pi$ in $G$
such that the length of $\pi$ is equal to $({\rm x}(p)-{\rm x}(r))+({\rm
y}(p)-{\rm y}(r))$. Note that an optimal solution will be necessarily a
forest, since any cycle is formed can be broken without violating the
connectivity requirements in the objective function (defined below).

### A minimum-length subdivision.

We assume, without loss of generality, that no two points of the input sets
$P$ and $R$ lie on a common vertical or horizontal line. Otherwise, we
slightly perturbate points in $P\cup R$, but in such a way that for a given
root $r\in R$, perturbating does not change the subset of points in $P$ that
are covered by $r$.

Let $x_{1}<x_{2}<\ldots<x_{2(n+m)-1}$ (resp.
$y_{1}<y_{2}<\ldots<y_{2(n+m)-1}$) denote the sorted $x$\- (resp. $y$-)
coordinates of the $n+m$ points in $P\cup R$ as well as the $n+m-1$ midpoints
of the intervals determined by these coordinates. Recall that by [35], we may
discretise $k$-perfect cuts, that is, we may restrict the $x$-coordinate of a
vertical $k$-perfect cut (resp. the $y$-coordinate of a horizontal $k$-perfect
cut) to be in $\\{x_{1},\ldots,x_{2(n+m)-1}\\}$ (resp. in
$\\{y_{1},\ldots,y_{2(n+m)-1}\\}$). Observe that by the construction, in
particular, by the definition of the $k$-span, the $k$-guillotine subdivision
$G_{k}$ obtained in Theorem 3.3 has the following property: if $p\in{\rm
Un}(G_{k})$, then there exists a root $r\in R$ and a path $\pi$ in $G_{k}$
such that the length of $\pi$ is equal to $({\rm x}(p)-{\rm x}(r))+({\rm
y}(p)-{\rm y}(r))$. This fact is crucial since it allows us to restrict
ourselves only to $k$-guillotine subdivisions that satisfy this property,
without loosing the estimate on the approximation ratio. Specifically, our
dynamic programming is based on solving the following subproblems, see Fig. 3.
SUBPROBLEM

Instance.

  * (1)

An axis-aligned window $W=W(l,r,b,t)$ determined by two points $(x_{l},y_{b})$
and $(x_{r},y_{t})$, $x_{l}<x_{r}$ and $y_{b}<y_{t}$, with $e_{r},e_{t},e_{l}$
and $e_{b}$ as its right, top, left and bottom edge, respectively.

  * (2)

For each edge $e$ of $W$, a set $X_{e}$ of at most $2k+2$ points of $e$, among
them at most $2k$ distinct internal points of $e$ and at most two points
corresponding to the endpoints of $e$.

  * (3)

For each set $X_{e}$, a set $S_{e}$ of disjoint line segments (vertical or
horizontal), called gates, with endpoints in $S_{e}$ such that if a point
$p\in P$ lies on the boundary of $W$, then $p$ belongs to some segment in
$S_{e}$; in addition, if $X_{e}$ has $2k$ distinct internal points of $e$,
then the segment formed by the middle two of them belongs to $S_{e}$.

Objective. Let $P_{W}=P\cap{\rm int}(W)$, let $P_{r}$ be the set of the bottom
endpoints of segments in $S_{e_{r}}$, including the degenerate segments in
$S_{e_{r}}$, and let $P_{t}$ be the set of the left endpoints of segments in
$S_{e_{t}}$, including the degenerate segments in $S_{e_{t}}$. Set
$I_{W}\doteq(P_{W}\cup P_{r}\cup P_{t})\setminus R$. The objective is to
compute a minimum-length guillotine rectilinear subdivision $G=(V_{G},E_{G})$
such that:

  * (1)

Edges in $E_{G}$ are axis-aligned line segments not lying on the boundary of
$W$.

  * (2)

For each point $p\in I_{W}$, there is a path $\pi$ in ${\rm Un}(G)$ to either
a root $r\in R\cap{\rm int}(W)$ or to a point $q$ of a segment in
$X_{e_{l}}\cup X_{e_{b}}$ such that the length of $\pi$ is equal to $({\rm
x}(p)-{\rm x}(u))+({\rm y}(p)-{\rm y}(u))$, for some $u\in\\{r,s\\}$.

As regards the condition (1) in the objective function — by arguments similar
to those in the proof of Lemma 1.1, so we omit details — observe that, without
loss of generality, we may assume that the edges in $E_{G}$ lie also within
the Hanan grid induced by all points in $((P\cup R)\cap W)\cup\bigcup_{e\in
E(W)}X_{e}$, where $E(W)=\\{e_{r},e_{t},e_{l},e_{b}\\}$.

$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\color[rgb]{1,1,1}\blacksquare$$\square$$\blacksquare$$\blacksquare$$\color[rgb]{1,1,1}\blacksquare$$\square$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$at
most $2k$ points and at most two endpoints (in corners)in each side of the
window; here, $k=3$a)

$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$O(2^{k})$choices
for gates in each side of the window; here $k=3$if there are $2k$ points in
the side, then one of its gates is the $k$-span$k$-spanb)

$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$the
instance of a subproblem(fixed gates along the boundary)c)

$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$a
cut with at most $2k$ points along it; here $k=3$d)

$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$O(2^{k})$choices
for gates along the cut; here, $k=3$if there are $2k$ points along the cut,
then one of its gates is the $k$-span$k$-spane)

$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$an
optimal solution of the subproblemwith respect to the gates along the cutf)

Fig. 7. An illustration of the subproblem and the recursive approach.

The initial problem is specified by the bounding box $B$ such that $P\cup
R\cup{\rm int}(B)$ (and so $X_{e}=S_{e}=\emptyset$ for each side of $B$). The
output is a $k$-guillotine $G$ such that if $p\in{\rm Un}(G_{k})$, then there
exists a root $r\in R$ and a path $\pi$ in $G_{k}$ such that the length of
$\pi$ is equal to $({\rm x}(p)-{\rm x}(r))+({\rm y}(p)-{\rm y}(r))$ (and so,
in particular, for a point $p\in P$, then there exists a root $r\in R$ and a
path $\pi$ in $G_{k}$ such that the length of $\pi$ is equal to $({\rm
x}(p)-{\rm x}(r))+({\rm y}(p)-{\rm y}(r))$).

The base subproblem is specified by (a) a window $W$ containing inside no
point in $P$, and (b) a constant number of gates: at most $2k+1$ of them per
each side of $W$ (see Fig. 3). Thus it can be also solved in
$(k+m)^{3}\,2^{O(k)}$ time by using the exact algorithm described in Section
2. For all other subproblems, we can find the optimal solution recursively, by
joining the solutions of the two obtained by splitting the problem, and
optimizing over all choices associated with a cut (including the cost of the
cut, that is, the sum of the lengths of its gates):

  * (a)

$O(n+m)$ choices of a cut by a horizontal or vertical line (determined by some
$x_{i}$ or $y_{j}$);

  * (b)

$O(2^{4k}\cdot(n+m)^{2k})$ choices of a set of gates on the cut within the
window: $O(2^{2k}\cdot(n+m)^{2k})$ choices of internal points on the cut
within the window, each of them generating $O(2^{2k})$ sets of gates.

Therefore, each subproblem takes $O(2^{4k}\cdot(n+m)^{2k+1})$ time. Since each
subproblem, i.e., the sides of its window, inherits the structure of a cut,
the total number of subproblems is $O(2^{16k}\cdot(n+m)^{8k+4})$: there are
$O(n+m)^{4}$ windows and $O(2^{4k}\cdot(n+m)^{2k})$ choices of a set of gates
on each of the four sides of a window. Consequently, we obtain an overall time
complexity of $O(2^{20k}\cdot(n+m)^{10k+5})=O((n+m)^{10k+5})$.

Theorem 3.2.  Given any fixed positive integer $k$, any set $P$ of $n$ points,
and any set $R$ of $m$ roots, all lying in the first quadrant of the plane,
there is an $O((n+m)^{10k+5})$-time algorithm to compute an approximate
rectilinear Steiner forest arborescence for $P$ with the root set $R$ whose
length is within factor $(1+\frac{1}{k})$ of optimal.

##  4 Fixed-parameter algorithm

In this section, following [5, 7, 28], we show that the RSFA problem is fixed-
parameter tractable with respect to the parameter $h$, the minimum number of
horizontal lines that all points are lying on. In particular, we show that the
RSFA problem can be solved in $O^{\ast}(2^{h})$ time (here, the
$O^{\ast}$-notation neglects polynomial factors). Recall that the idea behind
fixed-parameter tractability is to separate out the complexity into two pieces
— some piece that depends purely and polynomially (if possible) on the size of
the input, and some piece that depends on some “parameter” to the problem.

Let $P$ and $R$ be two disjoint sets of $n$ points and $m$ roots,
respectively, all lying in the first quadrant of $\mathbb{R}^{2}$ (with
$(0,0)\in R$), and let $H=H(P\cup R)$ be the Hanan grid of $P\cup R$; recall
that each point in $P\cup R$ corresponds to some intersection grid point of
$H$ and for any $X\subseteq P$, there exists an optimal RSFA for $X$ with the
root set $R$ such that it uses only subsegments of the Hanan grid $H(X\cup
R)\subseteq H(P\cup R)$ (see Lemma 1.2). Assume without loss of generality
that all intersection points of $H(P\cup R)$ are located on $v$ vertical lines
and $h$ horizontal lines, with $2\leq h\leq v$, and let
$C=\\{c_{1},c_{2},\ldots,c_{vh}\\}$ be the set of interection points of
$H(P\cup R)$ sorted lexicographically.

Let $k\in\\{1,2,\ldots,vh\\}$ be an integer and set $j:=\max(1,k-h+1)$. Now,
let

$f_{k}\colon\\{c_{j},c_{j+1}\ldots,c_{k}\\}\rightarrow\\{0,1\\}$

be a function — which we refer to as $k$-eligible — such that

$(P\cup R)\cap\\{c_{j},c_{j+1},\ldots,c_{k}\\}\subseteq f_{k}^{-1}(1),$

and let $F_{f_{k}}$ denote an optimal rectilinear Steiner forest arborescence
for $(P\cap\\{c_{1},c_{2},\ldots,c_{k}\\})\cup f_{k}^{-1}(1)$ with the root
set $R$. The idea is that for each $k$-eligible function $f_{k}$, the RSFA
$F_{f_{k}}$ candidates to be a partial solution for the global optimum (for
$P$), where intersection points in $f_{k}^{-1}(1)$ play a role of gates, that
is, the only points that a partial solution may expand through towards a
global solution, see Fig. 4(a-d) for an illustration. Clearly, in order to
solve the RFSA problem for $P$ with the root set $R$, we need to compute
$F_{f_{k}}$ for $k=vh$ and the function $f_{k}$ such that

$f_{k}^{-1}(1)=(P\cup R)\cap\\{c_{k-h+1},c_{k-h+2}\ldots,c_{k}\\}.$

a)$p$$r$

b)$c_{29}$$c_{30}$$c_{31}$$c_{32}$$c_{28}$$c_{27}$$c_{26}$$0$$1$$0$$0$$1$$0$$0$

c)$c_{29}$$c_{30}$$c_{31}$$c_{32}$$c_{28}$$c_{27}$$c_{26}$$0$$0$$0$$1$$1$$1$$0$

d)$c_{29}$$c_{30}$$c_{31}$$c_{32}$$c_{28}$$c_{27}$$c_{26}$$0$$1$$0$$1$$1$$1$$0$

e)$c_{36}$$c_{37}$$c_{38}$$c_{39}$$c_{35}$$c_{32}$$c_{31}$$c_{40}$$1$$1$$?$

f)$c_{36}$$c_{37}$$c_{38}$$c_{39}$$c_{35}$$c_{32}$$c_{31}$$c_{40}$$1$$?$$1$

Fig. 8. (a) The RSFA for the input set $P$ (white dots) with the root set $R$
(gray dots) here $h=7$.

(b) Since $c_{27},c_{32}\in P\cup R$, the depicted 0/1-assignment $f_{32}$ is
non $32$-eligible for points $c_{26},c_{27},\dots,c_{32}$. (c, d) Eligible
0/1-assignments for points $c_{26},c_{27},\dots,c_{32}$. Notice that the
assignment $f_{32}$ depicted in (c), although $32$-eligible, will be
eventually “useless” for the input sets $P$ and $R$ since any RSFA for $P$
with the root set $R$ has to use point $c_{29}$ or $c_{30}$, in order to
connect the point $p$ to the root $r=(0,0)$. (e, f) Since $c_{40}\in P$, we
must have $f_{40}(c_{40})=1$ for any $40$-eligible function $f_{40}$. Next, in
order to construct the RSFA $F_{f_{40}}$ recursively, we must have (e)
$f_{39}(c_{31})=1$ or (f) $f_{39}(c_{39})=1$ for the relevant $39$-eligible
function $f_{39}$.

All this can be done by dynamic programming method, and the rationale for such
approach is the following: given a $k$-eligible function $f_{k}$, an optimal
RSFA $F_{f_{k}}$ consists of an optimal RSFA $F_{f_{k-1}}$ for the relevant
$(k-1)$-eligible function $f_{k-1}$, being “consistent” with the status of the
intersection point $c_{k}$, which can be ’$0/R$’ or ’$1/P$’, in particular,
the status $1/P$ of $c_{k}$ requires $f_{k-1}$ such that $c_{k-1}\in
f_{k-1}^{-1}(1)$ if $k\leq v$, and $\\{c_{\max(1,k-h)},c_{k-1}\\}\cap
f_{k-1}^{-1}(1)\neq\emptyset$ otherwise.

To be more specific, the dynamic programming recursion (Bellman equation) is
defined as follows. The base of the recursion is $k=1$, namely, for $k=1$, the
only $1$-eligible function $f_{1}\colon\\{c_{1}\\}\rightarrow\\{0,1\\}$ is the
one with $f_{1}(c_{1})=1$ (since $c_{1}=(0,0)\in R$), and so $F_{f_{1}}$
constitutes of the singleton $c_{1}$. Next, for $2\leq k\leq h$, if
$c_{k}\notin R$ and $f_{k}$ is a $k$-eligible function with $f_{k}(c_{k})=1$,
then $F_{f_{k}}$ is the RSFA constructed from the RSFA $F_{f_{k-1}}$ (already
tabulated) by adding the edge $c_{j}c_{k}$, where
$j=\max\\{i:f_{k-1}(c_{i})=1\\}$ and $f_{k-1}$ is the restriction of $f_{k}$
to $\\{c_{1},\ldots,c_{k-1}\\}$, that is, $f_{k}(x)=f_{k-1}(x)$ for each
$x\in\\{c_{1},\ldots,c_{k-1}\\}$. (Notice that $f_{k-1}$ is a $(k-1)$-eligible
function by $k$-eligibility of $f_{k}$.) Otherwise, if either $c_{k}\in R$ or
$f_{k}(c_{k})=0$, then we just set $F_{f_{k}}:=F_{f_{k-1}}$, with $f_{k-1}$
defined as for the case $c_{k}\notin R$ and $f_{k}(c_{k})=1$.

Assume now that $k>h$ and let $f_{k}$ be a $k$-eligible function. If
$c_{k}\notin R$ and $f_{k}(c_{k})=1$, then the RSFA $F_{f_{k}}$ is constructed
from the RSFA $F_{f_{k-1}}$ (already tabulated) by adding the edge
$c_{j}c_{k}$, where $f_{k-1}$ is a $(k-1)$-eligible function such that
$f_{k-1}(x)=f_{k}(x)$ for each $x\in\\{c_{k-h+1},c_{k-h+2},\ldots,c_{k-1}\\}$,
and:

  * a)

$j=k-h$ if $f_{k-1}(c_{k-h})=1$, or

  * b)

$j=k-1$ if $k\neq 1\bmod h$ and $f_{k-1}(c_{k-1})=1$.

Clearly, among cases (a-b) we choose the one that minimizes the sum

$l(F_{f_{k-1}})+{\rm dist}(c_{j},c_{k}),$

taken over all such $(k-1)$-eligible functions $f_{k-1}$. Otherwise, if either
$c_{k}\in R$ or $f_{k}(c_{k})=0$, we just set $F_{f_{k}}:=F_{f_{k-1}}$, where
$f_{k-1}$ is a ($k-1$)-eligible function such that $f_{k-1}(x)=f_{k}(x)$ for
each $x\in\\{c_{k-h+1},c_{k-h+2},\ldots,c_{k-1}\\}$.

The correctness of the above approach, in particular, the fact that at each
single step, the constructed object is an optimal RSFA, directly follows from
the construction (by induction on $k$; we omit details). And, since we
tabulate the values/RSFAs $F_{f_{k}}$ for each $k\in\\{1,\ldots,vh\\}$ and
each $k$-eligible function $f_{k}$, which are at at most $O(2^{h})$ of them
for each $k$, and the RSFA $F_{f_{k}}$ can be computed in $O(1)$ time from all
the already tabulated data, the overall time complexity of our approach is
$O(vh2^{h})$, and so $O((n+m)h2^{h})$ since $v\leq n+m$. Consequently, the
RSFA problem is fixed-parameter tractable with respect to the parameter $h$.

Theorem 4.1. Given a set $P$ of $n$ points and a set $R$ of $m$ roots, with
$(0,0)\in R$ lying on $h$ horizontal lines in the first quadrant of the plane,
the RSFA for $P$ with the root set $R$ can computed in $O((n+m)h2^{h})$ time
and $O(2^{h})$ space.

##  5 Future work

In this section, we discuss briefly two results that are sought to make our
RFSA-survey complete. We expect that all approaches (those discussed above as
well as these discussed below), following for example [40], can be extended
for the case when points and roots can be located in any of four quadrants,
that is, to the variant when the following constraint is imposed: for any for
each point $p\in P$, there exists a path $\pi$ to some root $r\in R$ in the
same quadrant as $p$ such that the length of $\pi$ is equal to $|{\rm
x}(p)-{\rm x}(r)|+|{\rm y}(p)-{\rm y}(r)|$.

### Faster exact algorithm.

Recently, inspired by the work of Klein and Marx [27] on a subexponential-time
algorithm for the Subset Traveling Salesman problem on planar graphs, Fomin et
al. [19] proposed the first subexponential algorithm for the RSA problem, with
the running time of $O(2^{\sqrt{n}\log n})$; recall that the relevant
algorithm in Section 2 runs in $O(3^{n})$ time. We believe that their result
can be extended to the RSFA problem as well.

### Efficient $2$-approximation algorithm.

From a practical point of view, the running time of our PTAS for the RSFA
problem is unsatisfactory, which motivates us to design a fast constant factor
approximation algorithm. For the RSA problem, there are two greedy
2-approximated algorithms [40, 41]. It is natural then to try to apply similar
approaches for the RSFA problem.

The idea of the 2-approximation algorithm of Rao et al. [41] for the RSA
problem is as follows. Given a set of points $P$ and the root $r$, the
arborescence is generated by iteratively replacing the pair of points $p$ and
$q$ in $P$ by $\langle p,q\rangle$ until a single point (which has to be $r$)
remains. The points $p$ and $q$ are chosen to maximize $||\langle
p,q\rangle||$ over all points in the current set $P$, and the resulting
arborescence consists of all relevant edges from $\langle p,q\rangle$ to $p$
and $q$ (a degenerate case is possible if $\langle p,q\rangle$ is either $p$
or $q$). Now, for the RSFA problem, when considering a set of roots $R$, a
natural idea is to apply above heuristic with the only difference that we must
handle also elements in $R$ as possible roots for some trees in the current
partial solution. Observe that simple replacing points $p$ and $q$ whenever it
is possible does not have a reasonable relative performance guarantee as
illustrated in Fig. 5. Clearly, one can abstain from the relevant replacement,
since the distance from $p$ to the nearest root $r_{1}$ is smaller then the
sum of distances from $p$ to $\langle p,q\rangle$ and from $\langle
p,q\rangle$ to $r$. This introduces, however, another principle in the
(possible) correctness proof, and so another attempt is trying to rely
directly on the $2$-approximation method in [40], using that algorithm as a
subroutine. We believe that simple modification of this method will result in
an effective $2$-approximation algorithm for the RSFA problem as well.

a)pointroot$\cdots$$\vdots$$r$$r_{1}$$p$$q$$x$$x$$\varepsilon$$\varepsilon$$c$$c$

b)pointroot$\cdots$$\vdots$$x$$x$$\varepsilon$$\varepsilon$$c$$c$$r$$r_{1}$$p$$q$

Fig. 9. (a) Replacing points $p$ and $q$ with $u=\langle p,q\rangle$ results
in a rectilinear Steiner arborescence of the cost $2(c+x)$, while (b) the cost
of the optimal solution is $2(c+\varepsilon)$.

##  6 Open problem — Manhattan networks

Given a set of points $P$ in $\mathbb{R}^{2}$, a network $(G,P)$ is said to be
a Manhattan network for $P$ if for all $p,q\in P$, there exists a Manhattan
path between $p$ and $q$ with all its segments in $G$; the length of $(G,P)$,
denoted by $L(G)$, is the total length of all segments in $G$. For the given
set $S$, the Minimum Manhattan Network (MNN) problem is to find a Manhattan
network $(G,S)$ of minimum length $L(G)$. The MNN problem was first introduced
by Gudmundson et al. [21], who proposed an $O(n^{3})$-time $4$-approximation
algorithm and an $O(n\log n)$-time $8$-approximation algorithm. After [21],
much research has been devoted to finding better approximation algorithms —
see for example [3, 4, 9, 22, 26, 43] — and only in $2009$, Chin et al. [11]
proved the MMN problem to be NP-hard. In addition, a fixed-parameter algorithm
running in $O^{\ast}(2^{14h})$ time (neglecting a factor that is polynomial in
$n$), where the parameter $h$ is the minimum number of axis-parallel straight-
lines (either all horizontal or all vertical) that contain all the points in
$P$, was proposed by Knauer and in [28], the MNN problem in higher dimensions
has been considered in [17, 37], while [20, 25] consider a variant of the
problem where the goal is to minimize the number of vertices (Steiner points)
and edges.

Keeping in mind the motivation of RSFA, it is natural to define a relevant
variant of MNN. Namely, given a minimum Manhattan network $(G_{1},P_{1})$ and
the input set $P_{2}$ of points within the bounding box of $P_{1}$, the
Minimum Manhattan Network with the Backbone $G_{1}$ (MMNB) problem is to
compute the minimum Manhattan network $(G_{2},P_{1}\cup P_{2})$ such that
${\rm Un}(G_{1})\subseteq{\rm Un}(G_{2})$, where ${\rm Un}(G)$ denotes the
union of all line segments (edges) in a Manhattan network $G$. In particular,
one can be interested in designing a fast $2$-approximation algorithm for the
MMNB problem.

## References

  * [1] M.J. Alexander, G. Robins:  New performance-driven FPGA routing algorithms.  IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 15 (12), pp. 1505-1517, 1996.
  * [2] S. Arora:  Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems.  Journal of the ACM 45 (5), pp. 753-782, 1998.
  * [3] M. Benkert, A. Wolff, F. Widmann:  The minimum Manhattan network problem: a fast factor-3 approximation.  Proceedings of the 8th Japaneese Conference on Discrete and Computational Geometry, pp. 16-28, 2004.
  * [4] M. Benkert, A. Wolff, F. Widmann, T. Shirabe:  The minimum Manhattan network problem: Approximations and exact solutions.  Computational Geometry: Theory and Applications 35 (3), pp. 188-208, 2006.
  * [5] M. Brazil, D.A. Thomas, J.F. Weng:  Rectilinear Steiner minimal trees on parallel lines.  In: Advances in Steiner Trees (COOP, vol. 6), pp. 27-37 (2000).
  * [6] K. Buchin, B. Speckmann, K. Verbeek:  Angle-restricted Steiner arborescences for flow map layout.  Algorithmica 72 (2), pp. 656-685, 2015.
  * [7] H. Cambazard, N. Catusse:  Fixed-parameter algorithms for rectilinear Steiner tree and rectilinear traveling salesman problem in the plane.  European Journal of Operational Research 270 (2), pp. 419-429, 2018.
  * [8] X. Cheng, B. DasGupta, B. Lu:  Polynomial time approximation scheme for the symmetric rectilinear Steiner arborescence problem.  Journal of Global Optimization 21 (4), pp. 385-396, 2001.
  * [9] V. Chepoi, K. Nouioua, Y. Vaxes:  A rounding algorithm for approximating minimum Manhattan networks.  Theoretical Computer Science pp. 56-69, 2008.
  * [10] X. Cheng, D.-Z. Du, J.-M. Kim, H.Q. Ngo:  Guillotine cut in approximation algorithms.  In: Cooperative Control and Optimization. Applied Optimization 66, pp. 21-34, 2002
  * [11] F.Y.L. Chin, Z. Guo, H. Sun:  Minimum Manhattan network problem is NP-complete.  Discrete & Computational Geometry 45 (4), pp. 701-722, 2011
  * [12] J. Cong, A.B. Kahng, K.-S. Leung:  Efficient algorithms for the minimum shortest path Steiner arborescence problem with applications to VLSI physical design.  IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 17 (1), pp. 24-39, 1999.
  * [13] J. Cong, K.-S. Leung, D. Zhou:  Performance-driven inteconnect design based on distributed RC delay model.  Proceedings of the 30th international Design Automation Conference, pp. 606-611, 1993.
  * [14] J. Córdova, Y.-H. Lee:  Fast optimal algorithms for the minimum rectilinear Steiner arborescence problem.  Technical Report TR-94-25, University of Florida, 1994.
  * [15] A. Czumaj, J. Czyzowicz, L. Gąsieniec, J. Jansson, A. Lingas, P. Żyliński:  Approximation algorithms for buy-at-bulk geometric network design.  International Journal of Foundations of Computer Science 22 (8), pp. 1949-1969, 2011.
  * [16] A. Das, K. Fleszar, S.G. Kobourov, J. Spoerhase, S. Veeramoni, A. Wolff:  Approximating the generalized minimum Manhattan network problem.  Algorithmica 80, pp. 1170-1190, 2018.
  * [17] A. Das, E.R. Gansner, M. Kaufmann, S. Kobourov, J. Spoerhase, A. Wolff:  Approximating minimum Manhattan networks in higher dimensions.  Algorithmica 71, pp. 36–52, 2015.
  * [18] S.E. Dreyer, R.A. Wagner:  The Steiner problem in graphs.  Networks 1, pp. 195-207, 1972.
  * [19] F.V. Fomin, S. Kolay, D. Lokshtanov, F. Panolan, S. Saurabh:  Subexponential algorithms for rectilinear Steiner tree and arborescence problems.  ACM Transactions on Algorithms, 16 (2), Article No.: 21, pp. 1–37, 2020.
  * [20] J. Gudmundsson, O. Klein, C. Knauer, M. Smid:  Small Manhattan networks and algorithmic applications for the Earth mover’s distance.  Proceedings of the 23rd European Workshop on Computational Geometry, pp. 174-177, 2007.
  * [21] J. Gudmundsson, Ch. Levcopoulos, G. Narasimhan:  Approximating a minimum Manhattan network.  Nordic Journal of Computing 8 (2), pp. 219-232, 2001.
  * [22] Z. Guo, H. Sun, H. Zhu:  Greedy construction of $2$-approximation minimum Manhattan network.  International Journal of Computational Geometry & Applications 21 (3), pp. 331-350, 2011.
  * [23] M. Hanan:  On Steiner’s problem with rectilinear distance.  SIAM Journal on Applied Mathematics 14, pp. 255 - 265, 1966.
  * [24] J.-M. Ho, M.T. Ko, T.H. Ma, T.Y. Sung:  Algorithms for rectilinear optimal multicast trees.  Proccedings of the 3rd International Symposium on Algorithms and Computation, Lecture Notes in Computer Science 650, pp. 106-115, 1992.
  * [25] S. Jana, A. Maheshwari, S. Roy:  Linear-size planar Manhattan network for convex point sets.  Computational Geometry 100, #101819, 2022.
  * [26] R. Kato, K. Imai, T. Asano:  An improved algorithm for the minimum Manhattan network problem.  Proceedings of the 13th International Symposium on Algorithms and Computation, Lecture Notes in Computer Science 2518, pp. 344-356, 2002.
  * [27] P.N. Klein, D. Marx:  A subexponential parameterized algorithm for Subset TSP on planar graphs.  Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1812-1830, 2014.
  * [28] C. Knauer, A. Spillner:  A fixed-parameter algorithm for the minimum Manhattan network problem.  Journal of Computational Geometry 2 (1), pp. 189-204, 2011.
  * [29] R.R. Laderia de Matos:  A rectilinear arborescence problem.  Ph.D. Thesis, University of Alabama, 1979.
  * [30] K.-S. Leung, J. Cong:  Fast optimal algorithms for the minimum rectilinear Steiner arborescence problem.  Proceedings of the IEEE International Symposium on Circuits and Systems, pp. 1568-1571, 1997.
  * [31] B. Lu, L. Ruan:  Polynomial time approximation scheme for the rectilinear Steiner arborescence problem.  Journal of Combinatorial Optimization 4 (3), pp. 357-363, 2000.
  * [32] J. Maßberg:  The depth-restricted rectilinear Steiner arborescence problem is NP-complete.  arXiv:1508.06792, 2015.
  * [33] J.S.B. Mitchell:  Guillotine subdivisions approximate polygonal subdivisions: Part III — Faster polynomial-time approximation schemes for geometric network optimization.  Manuscript May 29, 1997.
  * [34] J.S.B. Mitchell:  A constant-factor approximation algorithm for the geometric $k$-MST problems in the plane.  SIAM Journal on Computing 28 (3), pp. 771–781, 1998.
  * [35] J.S.B. Mitchell:  Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric TSP, $k$-MST, and related problems.  SIAM Journal on Computing 28 (4), pp. 1298–1309, 1999.
  * [36] Y. Masumura, T. Oki, Y. Yamaguchi:  Dynamic programming approach to the generalized minimum Manhattan network problem.  Algorithmica 83 (12) pp. 3681–3714, 2021.
  * [37] X. Muñoz, S. Seibert, W. Unger:  The minimal Manhattan network problem in three dimensions.  Proceedings of the 3-rd International Workshop on Algorithms and Computation. Lecture Notes Computer Science 5431, pp. 369-380, 2009.
  * [38] L . Nastansky, S.M. Selkow, N.F. Stewart:  Cost minimum trees in directed acyclic graphs.  Mathematical Methods of Operations Research 18, pp. 59-67, 1974.
  * [39] F.P. Preparata, M.I. Shamos:  Computational Geometry.  Springer Verlag, New York, 1985.
  * [40] S. Ramnath:  New approximations for the rectilinear Steiner arborescence problem [VLSI layout].  IEEE Transactions Computer-Aided Design of Integrated Circuits and Systems 22(7), pp. 859-869, 2003.
  * [41] S.K. Rao, P. Sadayappan, F.K. Hwang, P.W. Shor:  The rectilinear Steiner arborescence problem.  Algorithmica 7 (1-6), pp. 277-288, 1992.
  * [42] W. Shi, C. Su:  The rectilinear Steiner arborescence problem is NP-complete.  SIAM Journal on Computing 35 (3), pp. 729-740, 2006.
  * [43] S. Seibert, W. Unger:  A 1.5-approximation of the minimal Manhattan network problem.  Proceedings of the 16-th International Symposium on Algorithms and Computation, Lecture Notes in Computer Science 3827, pp. 246-255, 2005.
  * [44] G.E. Téllez, M. Sarrafzadeh:  On rectilinear distance-preserving trees.  VLSI Design 7 (1), pp. 15-30, 1998.
  * [45] V.A. Trubin:  Subclass of the Steiner problems on a plane with rectilinear metric.  Cybernetics 21, pp. 320-322, 1995.
  * [46] K. Verbeek, K. Buchin, B. Speckmann:  Flow map layout via spiral trees.  IEEE Transactions on Visualization and Computer Graphics 17 (12), pp. 2536-2544, 2011.
  * [47] M. Zachariasen:  On the approximation of the rectilinear Steiner arborescence problem in the plane. Manuscript, 2000.