Base-object location problems for base-monotone regions
Base-object location problems for base-monotone regions
复制标题
DOI：
10.1016/j.tcs.2013.11.030
复制
发表时间：
2014-10
期刊：
影响因子：
--
通讯作者：
Jinhee Chun;T. Horiyama;Takehiro Ito;Natsuda Kaothanthong;H. Ono;Y. Otachi;T. Tokuyama;Ryuhei Uehara;T. Uno
中科院分区：
文献类型：
--
作者：
Jinhee Chun;T. Horiyama;Takehiro Ito;Natsuda Kaothanthong;H. Ono;Y. Otachi;T. Tokuyama;Ryuhei Uehara;T. Uno
具有底部的基本单调区域是像素网格中的单元的子集，使得如果单元包含在该区域中，则从该单元到基础的最短路径上的单元也包含在该区域中。在图像分割的背景下，首次研究了将像素网格分解为不相交的基单调区域的问题。众所周知，对于给定的像素网格和基线，可以在多项式时间内计算出相对于给定基线可以分解成不相交的基线单调区域的最大权重区域(Chun等人，2012[4])。我们继续这方面的研究，并证明了在给定的n×n像素网格中最优定位k条基线的问题的NP难。然后，我们给出了这个问题的O(N3)-时间2-近似算法。我们还研究了两个相关的问题，k基段问题和四分解问题，并给出了它们的一些复杂性结果。
A base-monotone region with a base is a subset of the cells in a pixel grid such that if a cell is contained in the region then so are the ones on a shortest path from the cell to the base. The problem of decomposing a pixel grid into disjoint base-monotone regions was first studied in the context of image segmentation. It is known that for a given pixel grid and base-lines, one can compute in polynomial time a maximum-weight region that can be decomposed into disjoint base-monotone regions with respect to the given base-lines (Chun et al., 2012 [4]). We continue this line of research and show the NP-hardness of the problem of optimally locating k base-lines in a given n× n pixel grid. We then present an O (n 3)-time 2-approximation algorithm for this problem. We also study two related problems, the k base-segment problem and the quad-decomposition problem, and present some complexity results for them.