Record link: 
http://hdl.handle.net/20.500.12708/203884
-
Title: 
Minimizing Corners in Colored Rectilinear Grids
en
Citation: 
Depian, T., Dobler, A., Kern, C., & Wulms, J. (2024). Minimizing Corners in Colored Rectilinear Grids. In WALCOM: Algorithms and Computation - 18th International Conference and Workshops on Algorithms and Computation, WALCOM 2024, Kanazawa, Japan, March 18–20, 2024, Proceedings (pp. 134–148). Springer, Singapore. https://doi.org/10.1007/978-981-97-0566-5_11
-
Publisher DOI: 
10.1007/978-981-97-0566-5_11
-
Publication Type: 
Inproceedings - Full-Paper Contribution
en
Language: 
English
-
Authors: 
Depian, Thomas 
Dobler, Alexander 
Kern, Christoph 
Wulms, Jules 
-
Organisational Unit: 
E192 - Institut für Logic and Computation 
-
Published in: 
WALCOM: Algorithms and Computation - 18th International Conference and Workshops on Algorithms and Computation, WALCOM 2024, Kanazawa, Japan, March 18–20, 2024, Proceedings 
-
Volume: 
14549
-
Date (published): 
29-Feb-2024
-
Event name: 
18th International Conference and Workshops on Algorithms and Computation, WALCOM 2024) 
en
Event date: 
18-Mar-2024 - 20-Mar-2024
-
Event place: 
Kanazawa, Japan
-
Number of Pages: 
15
-
Publisher: 
Springer, Singapore
-
Peer reviewed: 
Yes
-
Keywords: 
shape complexity; rectilinear polygons; set visualization
en
Abstract: 
Given a rectilinear grid G, in which cells are either assigned a single color, out of k possible colors, or remain white, can we color white grid cells of G to minimize the total number of corners of the resulting colored rectilinear polygons in G? We show how this problem relates to hypergraph visualization, prove that it is NP-hard even for k = 2, and present an exact dynamic programming algorithm. Together with a set of simple kernelization rules, this leads to an FPT-algorithm in the number of colored cells of the input. We additionally provide an XP-algorithm in the solution size, and a polynomial O (OP T)-approximation algorithm.
en
Research Areas: 
Logic and Computation: 100%
-
Science Branch: 
1020 - Informatik: 80%
1010 - Mathematik: 20%
-
Appears in Collections:
Conference Paper

Show full item record

Page view(s)

129
checked on Nov 4, 2024

Google ScholarTM

Check