Base-Object Location Problems for Base-Monotone Regions

• Chun, Jinhee

• Horiyama, Takashi

• Ito, Takehiro

• Kaothanthong, Natsuda

• Ono, Hirotaka

• Otachi, Yota

• Tokuyama, Takeshi

• Uehara, Ryuhei

• Uno, Takeaki

Abstract

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 baselines (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 x 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.

identifier:https://dspace.jaist.ac.jp/dspace/handle/10119/13779

Journal

• Theoretical Computer Science

  Theoretical Computer Science 555 71-84, 2014-10-23

  Elsevier

Keywords

• pixel grid
• image segmentation
• polynomial time algorithm
• approximation algorithm

Details

• CRID: 1050282812515206656
• NII Article ID: 120005851303
• ISSN: 03043975
• DOI: 10.1016/j.tcs.2013.11.030
• Web Site: http://hdl.handle.net/10119/13779
• Web Site: https://api.elsevier.com/content/article/PII:S0304397513008748?httpAccept=text/xml
• Web Site: https://api.elsevier.com/content/article/PII:S0304397513008748?httpAccept=text/plain
• Text Lang: en
• Article Type: journal article
• Data Source:
  • IRDB
  • Crossref
  • CiNii Articles
  • KAKEN