1. Base location problems for base-monotone regions
- Author
-
Chun, Jinhee, Horiyama, Takashi, Ito, Takehiro, Kaothanthong, Natsuda, Ono, Hirotaka, Otachi, Yota, Tokuyama, Takeshi, Uehara, Ryuhei, and Uno, Takeaki
- Subjects
pixel grid ,computational geometry ,base-monotone regions ,image segmentation - 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
- Published
- 2013