Base 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

The problem of decomposing a pixel grid into base-monotoneregions was first studied in the context of image segmentation. It is known that for a given n × n pixel grid and baselines, one can compute in O(n^3) time a maximum-weight region that can be decomposed into disjoint base-monotone regions [Chun et al. ISAAC 2009]. To complement this fact, we first show the NP-hardness of the problem of optimally locating k baselines in a given pixel grid. Next we present an O(n^3)-time 2-approximation algorithm for this problem. We also study some polynomial-time solvable cases, and variants of the problem.

WALCOM: Algorithms and Computation, 7th International Workshop, WALCOM 2013, Kharagpur, India, February 14-16, 2013. Proceedings

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

Journal

• Lecture Notes in Computer Science

  Lecture Notes in Computer Science 7748 53-64, 2013-02-14

  Springer

Keywords

• pixel grid
• image segmentation
• computational geometry
• base-monotone regions

Details

• CRID: 1050001337538488704
• NII Article ID: 120005850315
• ISSN: 03029743
• Web Site: http://hdl.handle.net/10119/13756
• Text Lang: en
• Article Type: journal article
• Data Source:
  • IRDB
  • CiNii Articles