Base-object location problems for base-monotone regions

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.

Authors

• Jinhee Chun
• Takashi Horiyama Hokkaido University
• Takehiro Ito
• Natsuda Kaothanthong
• Hirotaka Ono Nagoya University
• Yota Otachi Nagoya University
• Takeshi Tokuyama
• Ryuhei Uehara
• Takeaki Uno

Keywords

• Base-monotone region
• Room-Edge Problem
• Computational complexity
• Image segmentation