Base location problems for base-monotone regions

Jinhee Chun; Takashi Horiyama; Takehiro Ito; Natsuda Kaothanthong; Hirotaka Ono; Yota Otachi; Takeshi Tokuyama; Ryuhei Uehara; Takeaki Uno

doi:10.1007/978-3-642-36065-7_7

Base location problems for base-monotone regions

Jinhee Chun, Takashi Horiyama, Takehiro Ito, Natsuda Kaothanthong, Hirotaka Ono, Yota Otachi, Takeshi Tokuyama, Ryuhei Uehara, Takeaki Uno

mathematics and information

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

1 Citation (Scopus)

Abstract

The problem of decomposing a pixel grid into base-monotone regions was first studied in the context of image segmentation. It is known that for a given pixel grid and baselines, one can compute in polynomial time a maximum-weight region that can be decomposed into disjoint base-monotone regions [Chun et al. ISAAC 2009]. We continue this line of research and show the NP-hardness of the problem of optimally locating k baselines in a given n ×n pixel grid. We also present an O(n³)-time 2-approximation algorithm for this problem. We then study two related problems, the k base-segment problem and the quad-decomposition problem, and present some complexity results for them.

Original language	English
Title of host publication	WALCOM
Subtitle of host publication	Algorithms and Computation - 7th International Workshop, WALCOM 2013, Proceedings
Pages	53-64
Number of pages	12
DOIs	https://doi.org/10.1007/978-3-642-36065-7_7
Publication status	Published - 2013
Event	7th International Workshop on Algorithms and Computation, WALCOM 2013 - Kharagpur, India Duration: Feb 14 2013 → Feb 16 2013

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	7748 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	7th International Workshop on Algorithms and Computation, WALCOM 2013
Country/Territory	India
City	Kharagpur
Period	2/14/13 → 2/16/13

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-642-36065-7_7

Cite this

Chun, J., Horiyama, T., Ito, T., Kaothanthong, N., Ono, H., Otachi, Y., Tokuyama, T., Uehara, R., & Uno, T. (2013). Base location problems for base-monotone regions. In WALCOM: Algorithms and Computation - 7th International Workshop, WALCOM 2013, Proceedings (pp. 53-64). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7748 LNCS). https://doi.org/10.1007/978-3-642-36065-7_7

Base location problems for base-monotone regions. / Chun, Jinhee; Horiyama, Takashi; Ito, Takehiro et al.
WALCOM: Algorithms and Computation - 7th International Workshop, WALCOM 2013, Proceedings. 2013. p. 53-64 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7748 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Chun, J, Horiyama, T, Ito, T, Kaothanthong, N, Ono, H, Otachi, Y, Tokuyama, T, Uehara, R & Uno, T 2013, Base location problems for base-monotone regions. in WALCOM: Algorithms and Computation - 7th International Workshop, WALCOM 2013, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7748 LNCS, pp. 53-64, 7th International Workshop on Algorithms and Computation, WALCOM 2013, Kharagpur, India, 2/14/13. https://doi.org/10.1007/978-3-642-36065-7_7

Chun J, Horiyama T, Ito T, Kaothanthong N, Ono H, Otachi Y et al. Base location problems for base-monotone regions. In WALCOM: Algorithms and Computation - 7th International Workshop, WALCOM 2013, Proceedings. 2013. p. 53-64. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-36065-7_7

@inproceedings{6ca1f96922164a7f95b677a990df9f85,

title = "Base location problems for base-monotone regions",

abstract = "The problem of decomposing a pixel grid into base-monotone regions was first studied in the context of image segmentation. It is known that for a given pixel grid and baselines, one can compute in polynomial time a maximum-weight region that can be decomposed into disjoint base-monotone regions [Chun et al. ISAAC 2009]. We continue this line of research and show the NP-hardness of the problem of optimally locating k baselines in a given n ×n pixel grid. We also present an O(n3)-time 2-approximation algorithm for this problem. We then study two related problems, the k base-segment problem and the quad-decomposition problem, and present some complexity results for them.",

author = "Jinhee Chun and Takashi Horiyama and Takehiro Ito and Natsuda Kaothanthong and Hirotaka Ono and Yota Otachi and Takeshi Tokuyama and Ryuhei Uehara and Takeaki Uno",

year = "2013",

doi = "10.1007/978-3-642-36065-7_7",

language = "English",

isbn = "9783642360640",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "53--64",

booktitle = "WALCOM",

note = "7th International Workshop on Algorithms and Computation, WALCOM 2013 ; Conference date: 14-02-2013 Through 16-02-2013",

}

TY - GEN

T1 - Base location problems for base-monotone regions

AU - Chun, Jinhee

AU - Horiyama, Takashi

AU - Ito, Takehiro

AU - Kaothanthong, Natsuda

AU - Ono, Hirotaka

AU - Otachi, Yota

AU - Tokuyama, Takeshi

AU - Uehara, Ryuhei

AU - Uno, Takeaki

PY - 2013

Y1 - 2013

N2 - The problem of decomposing a pixel grid into base-monotone regions was first studied in the context of image segmentation. It is known that for a given pixel grid and baselines, one can compute in polynomial time a maximum-weight region that can be decomposed into disjoint base-monotone regions [Chun et al. ISAAC 2009]. We continue this line of research and show the NP-hardness of the problem of optimally locating k baselines in a given n ×n pixel grid. We also present an O(n3)-time 2-approximation algorithm for this problem. We then study two related problems, the k base-segment problem and the quad-decomposition problem, and present some complexity results for them.

AB - The problem of decomposing a pixel grid into base-monotone regions was first studied in the context of image segmentation. It is known that for a given pixel grid and baselines, one can compute in polynomial time a maximum-weight region that can be decomposed into disjoint base-monotone regions [Chun et al. ISAAC 2009]. We continue this line of research and show the NP-hardness of the problem of optimally locating k baselines in a given n ×n pixel grid. We also present an O(n3)-time 2-approximation algorithm for this problem. We then study two related problems, the k base-segment problem and the quad-decomposition problem, and present some complexity results for them.

UR - http://www.scopus.com/inward/record.url?scp=84873812867&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84873812867&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-36065-7_7

DO - 10.1007/978-3-642-36065-7_7

M3 - Conference contribution

AN - SCOPUS:84873812867

SN - 9783642360640

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 53

EP - 64

BT - WALCOM

T2 - 7th International Workshop on Algorithms and Computation, WALCOM 2013

Y2 - 14 February 2013 through 16 February 2013

ER -

Base location problems for base-monotone regions

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this