Abstract
In this article, we consider a combinatorial settlement model on a rectangular grid where at least one side (east, south or west) of each house must be exposed to sunlight without obstructions. We are interested in maximal configurations, where no additional houses can be added. For a fixed $m\times n$ grid we explicitly calculate the lowest number of houses, and give close to optimal bounds on the highest number of houses that a maximal configuration can have. Additionally, we provide an integer programming formulation of the problem and solve it explicitly for small values of $m$ and $n$.
The Sunlight Constraint Problem
The challenge of urban densification often conflicts with the necessity of natural light. This research formalizes this conflict using a discrete mathematical model. On an $m \times n$ rectangular grid, each cell can either be empty or contain a "house." Assuming sunlight originates from the South, a house is considered "blocked" if its neighbors to the East, West, and South are all occupied.
A configuration is defined as permissible if every house has access to sunlight from at least one of these three directions. A configuration is maximal if it is permissible, but the addition of any single house would violate the sunlight rule—either for the new house itself or for an existing neighbor.
The study focuses on two primary metrics:
- $I_{m,n}$: The minimum number of houses in a maximal configuration (the "inefficient" case).
- $E_{m,n}$: The maximum number of houses in a maximal configuration (the "efficient" case).
Methodology
The authors utilize a multi-faceted approach to bound these values:
- Combinatorial Proofs: Using injection mappings and the pigeonhole principle to establish rigorous density limits.
- Integer Programming (IP): Small-scale grids (up to $16 \times 16$) were solved exactly using the IBM ILOG CPLEX optimizer to provide empirical data for theoretical conjectures.
- Recursive Bounds: A recurrence relation $R_{m,n}$ was developed to refine upper bounds for $E_{m,n}$ as more small-scale values become known.
Patterns and Density Bounds
A significant finding is that for large grids, the density of any maximal configuration must fall between 50% and 75%. To prove these bounds, the authors identified specific infinite periodic patterns: Brick, Comb, Rake, and Stripe.
The "Brick" pattern is particularly noteworthy as it achieves the theoretical maximum density of 3/4. In this arrangement, rows are offset such that each empty cell provides light to three adjacent houses, maximizing the utility of open space.
Conversely, the "Rake" and "Stripe" patterns are used to demonstrate the lower bound ($I_{m,n}$), showing that a grid can be "filled" (made maximal) with as few as ~50% occupancy. This highlights the mathematical equivalence of the problem to tiling with $\perp$-tetrominoes (inverted T-shapes).
Key Results and Conclusion
The research provides a closed-form formula for the absolute minimum occupancy $I_{m,n}$, which is approximately $mn/2$. While a general explicit expression for the maximum $E_{m,n}$ remains an open question, the study's recurrence relations and IP benchmarks provide the tightest bounds to date.
This model serves as a foundation for more complex urban planning simulations. Future work may extend these findings to 3D environments where building height is a variable, or incorporate dynamic sunlight paths that track the sun from East to West throughout the day.
Summary updated