This paper considers the optimal feedback planning problem of a point robot among polygonal obstacles in . In this problem, the Euclidean distance traveled by the robot is minimized. The approximate optimal feedback plan is computed using a piecewise linear approximation of the cost-to-go function. The approximate cost-to-go function, in turn, satisfies the discrete version of dynamic programming principle defined using a simplicial decomposition of the environment. Adaptations of Dijkstra’s and A∗ algorithms are introduced that solve the nonlinear system of discrete dynamic programming equations. Interpolation methods are carefully designed and analyzed so that they are proven to converge numerically. As a result, the computed feedback plan produces approximately optimal trajectories. The methods are implemented and demonstrated on 2D and 3D examples. As expected, the simplicial A∗ algorithm significantly improves performance over the simplicial Dijkstra’s algorithm.