Abstract: This paper presents a GPU-accelerated approach for improving the approximated construction of Generalized Voronoi Diagrams (GVDs). Previous work has shown how to render a GVD onto the GPU framebuffer, and copy it to the CPU for extraction of a high-quality diagram. We improve upon this technique by performing more computations in parallel on the GPU, and reducing the amount of data transferred to the CPU. We also design a multi-tiled construction technique that overcomes hardware limitations and enables much higher rendering resolutions, thus reducing discretization errors. Next, we extend our approach to create an Explicit Corridor Map navigation mesh, which is an efficient data structure for path planning in modern crowd simulation systems. The new implementation allows much faster construction of GVDs and navigation meshes at virtually infinite resolutions.