<p>Point-of-Interest (POI) recommendation has witnessed a recent upsurge with the growth of Geographical Information Systems (GIS). The dynamic relationship between geographical utility and user transition patterns is not captured by existing approaches, which usually rely on collaborative filtering or static spatial analysis. In this paper, we propose a novel framework for cold-start POI recommendation that uses Meta-Utility Weighted Voronoi Diagrams (MUW-VD) to redefine spatial decomposition. Our main contribution, MUW-VD, generates a trainable spatial decomposition in which the borders of Voronoi cells dynamically change according to learned meta-utilities, which are indicators of how each POI contributes to stable meta-learning. In contrast with conventional Voronoi diagrams, which only consider geographic distance, MUW-VD ensures that cold-start users are connected to areas with the greatest potential for knowledge transmission by weighting spatial influence based on transition patterns. This spatial intelligence is combined with a temporally aware AutoEncoded GRU component for time-sensitive preference modeling and Meta-Utility Guided Transition Learning, which operates within utility-aware cells. The approach has been tested on three real-world datasets, and the results suggest that our approach outperforms other state-of-the-art methods.</p>