An Exact Generalized k-Cell Decomposition
This work provides a more efficient decomposition for visibility planning in robotics and computational geometry, particularly for agents with k-modem vision.
The paper introduces an exact k-cell decomposition for visibility planning in polygonal environments, achieving O(n^4) complexity, a quadratic improvement over the previous O(k^2 n^4) result. The decomposition eliminates redundant partition lines and extends to polygons with holes.
This paper introduces an exact $k$-cell decomposition for visibility planning in polygonal environments for agents equipped with $k$-modems, devices that can see through up to $k$ walls. Unlike prior decompositions that may include redundant partition lines, our proposed method ensures that visibility events (appear, disappear, merge, and split) are guaranteed to occur on every line of the decomposition. By eliminating these redundancies, we achieve an $O(n^4)$ complexity , representing a potentially quadratic improvement over the previous best $O(k^2n^4)$ result. This decomposition explicitly identifies the locations of all critical visibility events and extends to polygons with holes. It has practical applications in tasks such as optimal pursuit-evasion under $k$-visibility and agent counting in invisible regions.