This paper presents a computational framework of partitioning a dynamical system's free space in a way such that global optimality can be guaranteed by composing control policies over a local region. Unlike traditional triangulation methods, the partition method in this paper takes into account the topological layout, as well as the vehicle dynamics. With this framework, we show that spatial, dynamic behavior governed by optimality has an underlying structure, which reflect the spatio-dynamic dependency. This structure provides a basis for abstraction which is useful for the type of high level planning and reasoning that is needed for autonomous vehicle guidance. In this paper we focuses on a Dubins' vehicle motion model. Such a model is adequate for aircraft operating at a constant speed. Although restrictive, the insights and conclusions about this kind of vehicle can serve as basis for investigating more general systems.