| Presentation | 2012-04-27 On the Base-Line Location Problem for the Maximum Weight Region Decomposable into Base-Monotone Shapes Takashi HORIYAMA, Takehiro ITO, Natsuda KAOTHANTHONG, Hirotaka ONO, Yota OTACHI, Takeshi TOKUYAMA, Ryuhei UEHARA, Takeaki UNO, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | We study the problem of decomposing a pixel grid into base-monotone regions so that the sum of the weights of the regions is maximized. It is known that for a given n x n pixel grid with some baselines, one can compute a maximum-weight region which can be decomposed into disjoint base-monotone regions in O(n^3) time. 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. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Approximation algorithm / Base-monotone region / Image segmentation / NP-hardness |
| Paper # | COMP2012-6 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2012/4/20(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | On the Base-Line Location Problem for the Maximum Weight Region Decomposable into Base-Monotone Shapes |
| Sub Title (in English) | |
| Keyword(1) | Approximation algorithm |
| Keyword(2) | Base-monotone region |
| Keyword(3) | Image segmentation |
| Keyword(4) | NP-hardness |
| 1st Author's Name | Takashi HORIYAMA |
| 1st Author's Affiliation | Information Technology Center, Saitama University() |
| 2nd Author's Name | Takehiro ITO |
| 2nd Author's Affiliation | Graduate School of Information Sciences, Tohoku University |
| 3rd Author's Name | Natsuda KAOTHANTHONG |
| 3rd Author's Affiliation | Graduate School of Information Sciences, Tohoku University |
| 4th Author's Name | Hirotaka ONO |
| 4th Author's Affiliation | Department of Economic Engineering, Kyushu University |
| 5th Author's Name | Yota OTACHI |
| 5th Author's Affiliation | School of Information Science, JAIST |
| 6th Author's Name | Takeshi TOKUYAMA |
| 6th Author's Affiliation | Graduate School of Information Sciences, Tohoku University |
| 7th Author's Name | Ryuhei UEHARA |
| 7th Author's Affiliation | School of Information Science, JAIST |
| 8th Author's Name | Takeaki UNO |
| 8th Author's Affiliation | Principles of Informatics Research Division, National Institute of Informatics |
| Date | 2012-04-27 |
| Paper # | COMP2012-6 |
| Volume (vol) | vol.112 |
| Number (no) | 21 |
| Page | pp.pp.- |
| #Pages | 7 |
| Date of Issue | |