An Exact Generalized k-Cell Decomposition
2026-07-06 • Computational Geometry
Computational Geometry
AI summaryⓘ
The authors developed a new way to break down a polygon into parts based on what an agent with a $k$-modem can see through walls. Their method removes unnecessary dividing lines and ensures every line corresponds to an important change in visibility, like something appearing or disappearing. This makes the process more efficient, scaling better than previous methods. Their approach also works for polygons with holes and can help in problems like tracking or searching when visibility is limited.
visibility planningpolygonal environmentsk-modemscell decompositionvisibility eventscomputational geometrypursuit-evasionagent countingpolygon with holes
Authors
Yeganeh Bahoo, Sajad Saeedi, Roni Sherman
Abstract
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.