数理解析研究所講究録
第 1799 巻 2012 年 123-129

123

On the base-line location problem for the maximum weightregion decomposable into base-monotone shapes
Takashi Horiyama

Takehiro Ito

Hirotaka Ono

Yota Otachi

Ryuhei Uehara

Takeaki Uno
March 19, 2012

1 Introduction

is a based -monotone region if there is a horizontal baseline $y=b$ such that $(i_{J})\in R$ implies$(i,j-1)\in R$ for $j\geq b+1$ , and $(i_{J})\in R$ implies$(i,j+1)\in R$ for $j<b$ (see Figure 2). Based ymonotone regions are analogously defined. Basedx- and -monotone regions are base-monotone regions. Given a set of baselines, a region is
$R$

$x$

Let be an
pixel grid. A pixel $(i,])$ of is
the unit square whose top-right corner is the grid
point $(i,j)\in Z^{2}$ . For example the bottom-left cellof is (1, 1) and the top-right cell is $(n,n)$ . Eachpixel $p=(i_{J})$ , where $1\leq i,j\leq n$ , has its weight$w(p)\in$ Z. Now we define the following generalbase-monotone feasible if it can be decomposed
problem.
into pairwise disjoint base-monotone regions withrespect to the baselines. The baseline MWRP is
Problem: $MAxn Ub\iota$ WEIGHT REGION PROBLEM MWRP in which we are given (vertical or hori(MWRP)
zontal) baselines, and we find a maximum-weight
Instance: An
feasible region respect to the basebase-monotone
pixel grid .
Objective: Find a region $R\in r$ maximizing the lines. Chun et al. showed that the baseline
MWRP can be solved in polynomial time. They
weight $w(R)= \sum_{p\epsilon R}w(p)$ , wherebealso studied the base-segment MWRP, in which
a fixed family of pixel regions.
we are given segments and find a region decomThe general problem MWRP has been studied for posable into base-monotone regions respect to theseveral families S7““. Observe that if $r=2^{P}$ , then given base-segments. (We will define this problem
can be arbitrarily chosen, and thus the answer is more precisely in the next section.) They showed
the set of all positive cells. On the other hand, if some partial results on this problem. For other for“is the famuily of connected regions (in the usual mulations, as optimization problems, of the image-neighbor topology), then the problem becomes segmentation problem, see the recent work by GibNP-hard [1]. For the complexity of MWRP for son, Han, Sonka, and Wu [5].
other families, see the paper by Chun, Kasai, KorIn the setting of the baseline MWRP, we areman, and Tokuyama [2] and the references therein.
Motivated by thesegmentation problem, given baselines. Thus a natura! question would be
Chun et al. [2] stud\’ied more complicated family of “What if baselines are not given¿‘ In other words,(see Figure 1). A baseline “How can we divide the pixel ghd into subgrids
pixel regions for
We study thisof anpixel grid is a vertical line $x=b$ or hor- with vertical and horizontal
that
and
the
of optimallyproblemshow
problem$0\leqb\leqn$izontal line $y=b$ , where. A pixel region
locating baselines is NP-hard but can be approx’Saitama University.
imated within factor 2. Next we propose another
tTohoku University.
way to divide the pixel grid into subgrid, and show
*Kyusyu University.
this variant can be solved in polynomial time.
thatsTohoku University.
z JAIST
Finally, we study the base-segment MWRP and||NII
present sharp contrasts of its computational com$P$$P$$n\cross n$

$P$

$y$

$R$

$k$

$k$

$k$

$P$

$n\cross n$$k$$\mathcal{F}’\subseteq 2^{P}$

$k$

$k$

$R$

$k$

$k$

$imag\tilde{e}$$b\mathfrak{X}$$1ines^{\eta}$$n\cross n$

$P$

$k$

$k$

”

124
Theorem 2.1 ([2]). The baseline MWRP can be$k$solved in$O(n^{3})$time.

To complement this result, we study the computational complexity of the following problem.
Problem: BASELINE LOCATION

inteInstance: An $nxn$ pixel grid andgers and .
Question: Is there baselines insuch that amaximum-weight base-monotone feasible region has weight at least ?
$P$

$k$

$posi\dot{\mathfrak{a}}ve$

$w$

$P$

$k$

$w$

Figure 1: Image segmentation via
baseline
MWRP. We first convelt a picture to a gray scale
image. Next, with some suitable hnction, we construct a pixel gnid in which each dark pixel has
positive weight and each light pixel has negative
weight Finally we solve the baseline MWRP
to segment the back gound fiom the objects. In
this example, the edges of the picture is used asbaselines $(k=4)$ . For example, the red region in
the thuird figure (from left) uses the top edge as its
baseline.
$k$$k$possiIt is easy to see that there
only
ble allocations of baselines. Therefore, BASELmE
LOCATION can be solved in $o(2^{k}n^{k+3})$ time. However, tluis is far Rom efficient if is a part of the
input. We would like to solve this problem in$O(f(k)\cdot poly(n))$ time or even in $O(poly(k\cdot n))$time. Unfortunately, the latter case very unlikely
happens as we will prove the problem is NP-hard
if is a part of the input. The possibility of theformer case remains unsettled in this paper.
$a\infty$$(\begin{array}{l}2n+2k\end{array})$

$k$

$k$

$k$

2.2 The base-segment MWRP$k$Consider a segment in a baseline . If a monotone
region with baseline intersects only in , thenhas as its base-segment. Chun et al. [2] alsostudied base-segment MWRP, in which base$l$

$s$

$l$

$R$

$R$

$l$

$s$

$s$

$k$

$k$

segments are given, and one wants to find a region
that can be decomposed into disjoint monotone
regions with respect to the given base-segments.
Figure 2: A based x-monotone region (left) and a They also smdied two-directional version of thisbased y-monotone region (right).
problem in which the region can be built only on
the right side of each vertical base-segment andon
the upper side of each horizontal base-segment.
plexity.
They
showed the following results.
Due to space hmitation all proofs are omitted.

ne2Pre 殖皿血 naries

Theorem 2.2 ([2]).
two-directional basesegment MWRP can be solved in $O(kn)$ time.
The originwl base-segment MWRP can be solved
in
time.
$k$

$k$

$O(n\alpha k))$In this paper we study three different but well related problem. This section introduces these three
The first statement says that the two-directional
problems.
version is fixed parameter tractable when parameterized by . The second statement says thatthe original problem can be solved in polynomial
2.1 BAsELmr LocmoNtime if is not a part of the input. It was not
Chun et al. [2] presented the following positive re- known whether the two-directional version can besult.
solved in polynomial time with both and , and
$k$

$k$

$n$

$k$

125

$k–$

whether the original version is NP-hard whenis a part of the input. We will answer these twoquestions: the original problem is NP-hard and thetwo-directional version is polynomial-time solvable, when is a part of the input.

$\frac{x}{x\cdot x_{-}}$$-\underline{X}$Figure3: A baseline forcer: forcing one baseline.

$k$3-hardness of BASELmE LOCA-$—-$$\overline{\frac{x}{\frac\cross\bullet x}}---$$TIONNP$$\overline{\frac{x}{A^{*}\Delta*}}$As the first step of the smdy on BASELINE LOCATION,
Figure 4: A vertical baseline forcer: forcing one
we prove the following theorem.
vertical baseline or two horizontal baselines.
Theorem 3.1. BASELmE LOCATION is NP-completein the strong sense.
Next we consider a similar gadget depicted in

Figure 4. To take all positive cells and not to takeany negative cell, we need either one vertical baseline or two horizontal baselines. Therefore, if weneed to mimimize the number of baselines, then we
have to use one vertical baseline. We call this gadget a vertical baseline forcer. By rotating this gadProblem: INDEPENDENT SET
get, we can also obtain a gadget for forcing two
vertical baselines or one horizontal baseline. We
Instance: A graph and a positive integer .
call it a horizontal baseline forcer. Two positive
Question: Does have an independent set of size cells in this gadget have the same weight, and theirat least ?
weight is the weight of the vertical or horizontal
Note that INDEPENDENT SET is NP-complete even baseline forcer. The position of a vertical or horizontal baseline forcer is the position of its bottomwith the restriction $|V(G)|=|E(G)|$ .
.
left cell.
Proposition 3.2. INDBPENDENr SET is NP-complete
Vertical and horizontal baseline forcers work
ven if we insert some space between columns orfor the instances $with|V(G)|=|E(G)|$ .
ows as in Figure 5. The location of the baseline
is restricted to the area depicted in the fig3.1 Gadgets
re. We say that a vertical (horizontal) baseline
We first define two small gadgets for forcing base- 1 orcer intersects a vertical (horizontal resp.) baselines into restricted zones. Throughout this paper, ] ine if the baseline is in the restricted area; that is,each red in a pixel grid represents a huge neg- a base monotone shape with the vertical or horiative weight whose absolute value is equal to the zontal baseline can contain the positive cells in thesum of all the positive weights in the gnd. Also, ertical or horizontal baseline forcer. The number
each blue represents a (not necessarily large) pos- of the columns used by a vertical baseline forcer isitive weight. All the other cells have weight .
its width, and the number of rows used by a horOur first gadget is thegrid depicted in Fig- izontal baseline forcer is its height. For example,
ure 3. If we want to take the positive cell at the 1 he original vertical baseline forcer in Figure 4 iscenter, we need one baseline as in the figure. Since of width 3.
we cannot take any huge negative cell, the possible
locations of the baselines are restricted to the four
3.2 Reductionin the figure. We call this gadget a baseline forcer.
The weight of a baseline forcer is the weight of theiven an instance $(G, s)$ of INDEPENDENT SET, we
positive cell, and the position of a baseline forcer construct an instance $(P,k,w)$ of BASELINE LOCATION
is the position of its bottom-left cell.
a follows. It is easy to see that the reduction below
asThe problem is clearly in NP. We prove its NPhardness by reducing INDEPENDENT SET to this problem. An independent set of a graph is a set of pairwise non-adjacent vertices. It is known that the following decision problem is NP-complete [3].

$G$

$s$

$G$

$s$

$1$

$\rceil$$\cross$

.

$z$

1

$($

$0$

$i$

$3\cross 3$$i$$\langle$$’$$\langle$

$($

126
へ

$\wedge$x
X X X$-$—$x^{----}$$\bullet$$\bullet$X$\cross\cross\bullet X$$x$$x\bullet x$xx
Figure 5: Forced baselines are restricted to the area
indicated by double headed arrows.

can be done in polynomial time, and the absolutevalues of the weights are bounded by a polynomialof the input size.
By Proposition 3.2, we may assume $|V(G)|=$$|E(G)|$ for notational convenience.
Let $V(G)=$and $E(G)=\{e_{1}, \ldots,e_{m}\}$ . We set the
number of baselines $k=2m$ and the required FFigure 6: Gadgets for an edge
: black thickweight $w=8m^{3}+8m^{2}+s$. The grid is the llines are the candidates of required baselines, two$(20m+20)\cross(20m+20)$ pixel grid with the fol- vertical and one horizontal.
lowing entries. (see Figure 6).
$\nu_{j}$$v_{i}$$\{v_{1}, \ldots,v_{m}\}$$\{v_{i},v_{j}\}$$P$

The total weight of the positive cells is $W=$
$4m(2m^{2}+n)+6m^{2}+n=8m^{3}+10m^{2}+m$ We.

Vertex gadgets

sset the weight of the negative cells $to-W$ so that
For each vertex , we put a vertical baseline forcer these cells cannot be taken in any solution with a, atof width 5 and weight $2m^{2}+m$ , denoted
ppositive total weight.
the position $(10i, 5i)$ . We also put a baseline forcer, at the position $(10i-$of weight 1, denoted
3.3 Equivalence$1,20m+15)$$v_{i}$$VF_{i}$$BF_{i}$.

Lemma 3.3. $(G, s)$ is a yes-instance of INDEPENDENT
if and only $\iota f(P,k,w)$ is a yes-instance ofBAsmntE LOCATION.

Edge gadgets$SF\Gamma$

Let $e_{h}=\{v_{i},v_{j}\}\in E(G)$ be an edge with $i<j$.
We put a honizontal baseline forcer of height 10, at the position
and weight $2m^{2}+m$ , denoted$(10m+5h,5m+15h)$ . Next we pm two horizontal
baseline forcersof height 3 andandweight at the positions $(10i-3,5m+15h-1)$
and $(10j-3,5m+15h+8)$ , respectively. Also, we
put two baseline forcers
of weight
andat the positions $(10i+3,5m+15h+2)$ and $(10j+$
3, $5m+15h+5)$ , respectively.

4 A 2-approximation algorithm
for BASBIJNE LocmoN$HF_{h}$$HF_{h,i}$$HF_{h,j}$$BF_{h,i}$$BF_{h,j}$$m$

Our approximabihty result is based on the
ppolynomiaI-time solvability of the following prob$\langle$

$m$

$|$

$|$

.

$1$

lem.

lProblem: VERTICAL BASmINE LOCATIONlInstance: An
teger .

$n\cross n$

pixel grid$P$

and a positive in-$k$

The weight of negative cells

that
Objective: Find
vertical baselines inbaseofoptimalweightanthemonotone feasible region respect to thesebaselines.
$k$

We have the following positive cells in the grids:$\circ 4m$.

$\circ 6m$$m$

cells of weight $2m^{2}+m$ ,cells of weight , and$m$cells of weight 1.

$P$$\ovalbox{\tt\small REJECT}$

roblem HORIZONT BASBImE
ne.
fined analogously.
.

$L\infty ATION$

is de-

127
Theorem 4.1. VERTICAL BASBLINE LOCArION and
HORIZONTAL BASELINE LOCrYON can be solved intime.

1 rmge ofrage of$s’\{$$s$$s’$$O(n^{3})$Theorem 4.2. There is an-time 2- Figure 7: The ranges of vertical base-segments
approximation algorithm for locating baselines and .
to mximize the weight of optimum base-monotone
feasible region.
.
$O(n^{3})$
$k$

$s$

$s’$

$a_{s}(1):$$a_{s}(5)$$a_{s}(.2)a_{s}(3)a_{s}.(4)$5 The base-segment MTWRP$k$. The corresponding
Figure 8: Example of$\ldots,w_{s}(5)=5,1,1,3,3$
weights.
$a_{s}(p)$We extend the results of Chun et al. [2] (Theorem 2.2). We first reduce the two-directionalversion to WEIGHTED INDEPENDENT SET in bipartite
graphs, which can be solve in polynomial time [6].
We next reduce the INDEPENDENT SET in planargraphs to the original problem. Thuis implies theNP-hardness of the original problem, since INDEPENDENF SET is NP-hard for planar graphs [4].
In what follows, we may assume without lossof generality that no base-monotone shape withrespect to a base-segment contains another basesegment properly (in such a case, we can just partition the base-monotone shape). We may also assume that two parallel base-segments may have intersection only at their end-points.

$w_{s}(1),$$w_{s}(p)= \sum_{a_{s}(p-1)<q\mathscr{D}_{s}(p)}w(q,j)$ . See Figure 8. For
each horizontal base-segment , we also define thesequence
analogously.
Now we construct a bipartite graph$(U, V;E)$ . Let $s=(i,])$ be a vertical base-segment.
Assume that is the largest index such thatisdefined. Now all
are defined fromthe definition. If $r=0$ , then this segment is useless and just ignored. Otherwise, we put vertices$1\leq p\leq r$ , with weight $w_{s}(p)$ into $U$ . For
each honizontal base-segment $s’=(i’, j’)$ , we put
vertices $v_{s’}(p’)$ into in the same way. Next wedefine the edge set . Two vertices $u_{s}(p)\in U$
and $v,(p’)\in V$ are adjacent if and only if two
5.1 Two-directional version
base-monotone regions with base-segments andWe first divide each base-segment of length
have nonzero area intersection if they contain
into base-segments of length 1. This refine- $(a_{s}(p)_{J})$ and $(i’,a,(p’))$ , respectively. More prement does not change the optimum value of the $k|$cisely, this can be stated as: $i\leq i’\leq a_{s}(p)$ andbase-segment MWRP. Now we have $O(kn)$ base- $f\leq j\leq a_{s’}(p’)$ . See Figure 9 for example.
segments of length 1. We identify a base-segmentwith $(i,j)$ if is the left or bottom edge of a pixel :Lemna 5.1. An optimum solution of an instanceof the two-directional base-segment MWRP has.
at least $Wlf$ and only the corresponding
weightFor each vertical base-segment $s=(i_{J})$ , we define its range as follows: if there is no vertical basesegment $s’=(i’,j)$ with $i’>i$ , then the range ofis $[i,n]$ ; otherwise the range of is $[i, i’]$ , where is
the smallest index for which such a segment exists.
(see Figure 7). We define the range of a horizontal
base-segment analogously.
$v’(1)v,’(2)v’(3)v’(4)$Let $s=(i,j)$ be a vertical base-segment withrange $[i,i’]$ . Let $a_{s}(0)=i-1$ , and for $p\geq$
1, letbe the minimum index such that ] igure 9: The bipartite graph construction. The
ertices corresponding to the crossing ranges of$a_{s}(p-1)<h\leq i’$ and $\sum_{a_{s}(p-1)<q\leq h}w(q,j)$ is positive. If there is no such index, thenis unde- wo base-segments induce a disjoint union of an
fined. If
is defined for some $p\geq 1$ , then let independent set and a complete bipartite graph.
$s’$$a_{s’}(\cdot)$

$G$

$=$

$a_{s}(r)$$r$$a_{s}(0),$$\ldots,$$a_{s}(r)$$s$$u_{s}(p),$

$V$

$E$

$s$

$s’$

$\ell$

$f$

$i$

$s$

$s$

$k$

$(i_{j})$$\rceil$$s$$a_{s}(p)$$u(1)$

$i’$

$s$

$h$

$v$

$a_{s}(p)$$a_{s}(p)$$\iota f$

$t$

$i$

$u_{j}(2)$$u,(3)$$u_{3}(4)$$u(5)$

128
bipartite graphat least .

$G$

6. no two endpoints of segments have the same
position.

has an independent set of weight$W$

Theorem5.2. The two-directional base-segment We call a visibility representation satisfying the
MWRP can be solved in $O(k^{3}n^{6}\log kn)$ time.
three additional conditions a nice visibility representation. Given a visibility representation of a
5.2 NP-hardness of the base-segment planar graph, we can obtain a nice visibility repMWRP
resentation of the graph in polynomial time by refining each cell of the gnid to an $O(n)\cross O(n)$ subWe now show the following theorem.
grid, slightly extending each horizontal segment,
Theorem 53. The base-segment MWRP is NP- and slightly shifUng each vertical segment.
complete in the strong sense.
$k$

$k$

$k$

The problem is clearly in NP, and thus it suffices to show the NP-hardness. To this end, we reduce the INDEPENDENT
for planar graphs to thebase-segment MWRP. A graph is planar if it canbe drawn in the plane without edge crossings. It
is known that INDEPENDENr SET is NP-hard even forplanar graphs [4].
$S_{E}r$$k$5.2.2 Reduction
Let $(G,s)$ be an instance of INDEPBNDENr SET, whereis a planar graph with vertices and edges.
Note that we do not assume $n=m$ here. We first
construct a nice visibility representation $R=(A,B)$of in polynomial time, where is the set of horizontal segments and is the set of vertical segments. We construct a pixel grid Rom as follows (see Figure 11).
For each vertex $u\in V$ with the corresponding horizontal segment $a_{u}=[x_{1},x_{2}]\cross\{y\}\in A$ ,and set thewe put a vertical base-segmem. For each edge $e=$weight 1 to the cell$\{v,w\}\in E$ with the corresponding vertical segment $b_{u}=\{x\}\cross[y_{1},y_{2}]\in B$ , we put horizontal
base-segments $(x,y_{1})$ and $(x,y_{2}+1)$ and set the, where the y-coordinate
weight to the cell
is not used by any vertical base-segment and. Such a coordinate can be chosen
by the refinement of the grid. Note that the weightof a cell is at most and there is no negative-weight
$G$

$m$

$n$

$A$

$G$

$B$

5.2.1 Nice visibihty representations
Planar graphs have several geometric representations. We use one of them here. A subset of plane1, 2, $\ldots,w\}x(1,2,$
is a $wxh$ grid. A visibility representation ofaplanar graph maps eachvertex of to a horizontal segment with endpoints
in a gnid and each edge of to a vertical segmentwith endpoints in a gnd such that$\ldots,h\}$

$\{$

$G$

$G$

$G$

1. no segments of two distinct vertices intersect,

$P$

$R$

$(x_{1},y)$$(x_{2},y)$$(x,y_{e})$$n$$y_{\ell}$

2. segments of two distinct edges intersect onlyat their endpoints, and3. the segment of an edge
touches the seg$\{u, v\}$ments of and
$u$

$v$

.

Otten and van Wjk [7] showed that every planargraph has a visibility representation. It is known
that arepresentation of a planar graphin an $O(n)\cross O(n)$ grid can be found in linear
time [8, 9]. For the oecent development on visibility representations, see the recent paper by Wangand He [10] and the references therein. For our
purpose, we need the following additional conditions for visibihty representations:$Vi\mathfrak{X}biLty$$\mathcal{Y}1<y_{e}<\mathcal{Y}2$

$n$

cell.

5.2.3 Equivalence
We now show that $(G, s)$ is a yes-instance if
and only if the optmum value of base-segment
MWRP on is at least $mn+s$ . (The proof is omit$k$

$P$

ted.)

5.2.4 The $three4irectional$ version

4. no two vertical segments have the same x- In the reduction above, we may assume withoutcoordinate,loss of generality that the region can be built only
5. no two horizontal segments have the same y- on the right side of each vertical base-segment, on
coordinate, andthe upper sides of some horizontal base-segments,

129
$\}$

$*$

$\mathscr{H}$$\mathscr{M}$.

$\iota$$\backslash _{u}*\mathfrak{X}_{\eta}$$w$$*t^{8}$$\sim\ovalbox{\tt\small REJECT}_{\backslash }^{x_{Y}^{\alpha}}$$\aleph_{b}\searrow_{\aleph}^{e}*$$\alpha$の$t_{\wedge}^{\backslash }\ \S^{\searrow}$$\searrow_{\grave{k}}^{h}\lambda^{X}$$tS_{*}*\mathfrak{X}$$\mathscr{M}$.

$\searrow\backslash *\rangle\searrow_{\searrow\backslash }$$\cross_{\aleph}qu_{\searrow_{\backslash }}^{\eta}k\cross_{\aleph}^{a*}\nwarrow\eta$$f^{-}$$-\mathfrak{X}_{\backslash }^{*_{*}}\searrow\searrow\lambda^{\backslash }$$*$$\underline{\ulcorner}--\tilde{arrow}arrow$$-\infty_{-}\overline{m}$$*_{\backslash }\cross\grave{\backslash \aleph}8\backslash _{\sim}^{8}$$\alpha$$-$$\mathscr{F}\backslash \ovalbox{\tt\small REJECT}_{k^{\backslash }}^{\backslash }$$8^{Y}\mathfrak{X}_{Y}*\S\tilde{\backslash }*_{\backslash }^{h}$$k\backslash *8\mathscr{M}^{\nwarrow^{\sim}}$$\grave{\sim,}\mathfrak{X}_{\nwarrow_{\}}\backslash \backslash ^{n}\backslash \backslash *$.

$\S^{\nwarrow}R_{\backslash }^{\backslash }$$k*K_{\tau}\backslash \nwarrow\grave{\aleph}*^{\searrow^{\sim}}$$r$$\S^{\searrow_{\backslash }^{\eta}}\triangleright k^{\backslash }\mathscr{M}\grave{\S^{t_{v}^{\backslash }}\nwarrow a}_{\aleph}$$k\searrow rs^{\aleph}\backslash K^{\tau}$$-$$\grave{t_{\aleph}^{\backslash }\nwarrow_{1}\infty^{R^{\backslash }}\nwarrow}$

$t$

鐵

$–$

$\iota k\backslash x_{\Im}\nwarrow*_{\backslash }\mathfrak{X}k$,.

$\mathfrak{X}^{\backslash }*$$\grave{\backslash _{\aleph\backslash }\backslash \backslash ^{\backslash }\aleph}*\cross^{k_{*}}$$*$$\lambda$$\sim\infty\infty$.

$\iota$鱒$\grave{al^{\backslash }-}k^{\lambda^{\}}$$-nwarrow^{\searrow_{s}}-\searrow\ltimes\underline{k}*\backslash \backslash ,-$$–\otimes^{s}\underline{\overline{\cdot}}$$\infty$–

Figure 10: Reduction. Each green thick segment is a base-segment. In the right figure $S=\{b,d\}$ . Yellow
cells are taken by the vertical base-segments, and green cells are taken by the horizontal base-segments.
and on the lower sides of the remaining horizontal base-segments. We call this version the three-[5] M. Gibson, D. Han, M. Sonka, and X. Wu.

Maximum weight digital regions decomposable into digital star-shaped regions. In $22nd$
Intemational Symposium on Algorithms andComputation (ISAAC 2011), volume 7074 of
Lecture Notes in Comput. Sci., pages 724733, 2011.

directional base-segment MWRP.
$k$Corollary 5.4. me three-directionalbasesegment MWRP is NP-complete in the strong$k$sense.

[6] D. S. Hochbaum. Efficient bounds for the
stable set, vertex cover and set packing prob-

Referenceslems. Discrete Appl. Math., 6: 243-254, 1983.

[1] T. Asano, D. Z. Chen, N. Katoh, andT. Tokuyama.
Efficient algorithms for
optimization-based image segmentation. Intemat. J. Comput. Geom. Appl., 11: 145-166,[7] R. H. J. M. Otten and J. G. van Wijk. Graphrepresentations in interactive layout design.
In IEEE Intemat. Symp. on Circuits and Sys-

2001.

tems, pages 914-918, 1978.

[2] J. Chun,

R. Kasai, M. Korman, andT. Tokuyama. Algorithms for computing the
maximum weight region decomposable intoelementaly shapes. In 20th Intemational
Symposium on Algorithms and Computation(ISAAC ’09), volume 5878 of Lecture Notes
in Comput. Sci., pages 1166-1174, 2009.

[8] P. Rosenstiehl and R. E. TaIjan.

Rectilinear
planar layouts and bipolar orientations of planar graphs. Discrete Comput. Geom., 1:343353, 1986.

[9] R. Tamassia and I. G. Tollis. A unified ap-

proach to visibility representations of planargraphs. Discrete Comput. Geom., 1:321-341,

1986.
Computersand Intractabihty. A Guide to the Theory of[10] J.-J. Wang and X. He. Compact visibility repNP-Completeness. Freeman, 1979.
resentation of plane graphs. In 28th Intema[4] M. R. Garey, D. S. Johnson, and L. Stocktional Symposium on Theoretical Aspects ofComputer Science (STACS 2011), volume 9meyer. Some simplified NP-complete graphof LIPIcs, pages 141-152, 2011.
problems. Theoret. Comput. Sci., 1:237-267,[3] M. R. Garey and D. S. Johnson.
$\cdot$$[$1976.