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 $\mathcal{O}(OPT)$-approximation algorithm.
Introduction
In the field of hypergraph visualization, representing sets and their relationships often involves using disjoint polygons on a rectilinear grid. Each grid cell represents a vertex, and polygons of different colors represent distinct hyperedges. A critical factor in the readability of these diagrams is their visual complexity, specifically the number of corners in the polygons. Jagged shapes with many corners are significantly harder for the human eye to process than simpler, smoother forms.
This paper addresses the MinCorner Complexity problem: given a grid where some cells are pre-colored (fixed set memberships) and others are white (empty), how should the white cells be colored to minimize the total number of corners in the resulting polygons?
Complexity and Algorithmic Framework
The authors demonstrate that the decision version of this problem is NP-complete, even when restricted to only two colors ($k=2$). This proof is achieved via a reduction from a variant of 3-SAT (Restricted Planar Monotone 3-Bounded 3-SAT). Despite this inherent difficulty, the problem exhibits structural properties that allow for efficient solutions under specific constraints.
Local Corner Counting
A key insight of the research is that corners are local properties. Specifically, corners occur at the intersection points of $2 \times 2$ grid regions. By formalizing a corner-counting function $\delta_c$, the authors transform the global shape optimization problem into a series of local tiling decisions.
Dynamic Programming and Kernelization
This local property enables a row-by-row dynamic programming (DP) approach. While the state space remains exponential in the number of columns ($n$), it is linear in the number of rows ($m$), making it efficient for grids with few columns.
To handle larger, sparser grids, the authors introduce kernelization rules. They prove that empty rows or columns, as well as consecutive identical rows, can be safely removed or merged without altering the optimal solution's corner count. This "Grid Compression" shows that the problem is Fixed-Parameter Tractable (FPT) relative to the number of colored cells ($r$), as any input can be reduced to a kernel of size $O(r) \times O(r)$.
Key Results
The theoretical analysis yields several algorithmic bounds:
- Exact DP: Runs in $O((k + 1)^{2n}mn)$ time.
- FPT Result: The problem is solvable in time dependent only on the number of colored cells, independent of the total grid size.
- XP Algorithm: If the optimal number of corners $\ell$ is constant, the problem is solvable in $(n(k+1))^{O(\ell)}m$ time.
- Approximation: A polynomial-time $O(OPT)$-approximation is achievable in $O(m^2n)$ time by focusing on identical consecutive rows.
Discussion and Future Directions
While this work provides a robust framework for minimizing corners, several open questions remain. The current model assumes each cell contains at most one color; however, in real-world hypergraphs, a vertex (cell) might belong to multiple sets. Future work could explore optimal subdivision strategies for multi-colored cells.
Additionally, the paper focuses on corner count rather than connectivity. Minimizing corners often reduces the number of polygons, but the algorithm does not explicitly guarantee that each color forms a single connected component. Finally, improving the $O(OPT)$-approximation to a constant-factor approximation would enhance the practical utility of these algorithms for large-scale visualization tasks.
Summary updated