With the advent of polygonal maps finding theirway into the navigational software of mobile robots, theVisibility Graph can be used to search for the shortest collision-free path. The nature of the Visibility Graph-based shortestpath algorithms is such that first the entire graph is computedin a relatively time-consuming manner. Then, the graph canbe searched efficiently any number of times for varying startand target state combinations with the A* or the Dijkstraalgorithm. However, real-world environments are typically toodynamic for a map to remain valid for a long time. With thegoal of obtaining the shortest path quickly in an ever changingenvironment, we introduce a rapid path finding algorithm—Minimal Construct—that discovers only a necessary portionof the Visibility Graph around the obstacles that actually getin the way. Collision tests are computed only for lines thatseem heuristically promising. This way, shortest paths can befound much faster than with a state-of-the-art Visibility Graphalgorithm and as our experiments show, even grid-based A*searches are outperformed in most cases with the added benefitof smoother and shorter paths.