DO-LEC (Dynamic Obstacle-Aware Largest Empty Circle): Fast and Adaptive LEC Computation for Navigating Dynamic Obstacle Fields

Abstract

Autonomous systems navigating dynamic environments require continuous identification of maximum-clearance safe zones. However, existing Largest Empty Circle (LEC) algorithms assume static obstacle configurations and necessitate complete recomputation when obstacles move. This fundamental limitation prevents their deployment in real-time applications where obstacles continuously change positions. We present DO-LEC (Dynamic Obstacle-Aware Largest Empty Circle), the first practical algorithm to compute geometrically optimal safe zones in environments with moving obstacles while maintaining real-time performance. DO-LEC integrates classical Voronoi-Delaunay geometric principles with adaptive candidate generation and incremental obstacle tracking, achieving efficient updates without full reconstruction. Comprehensive evaluation across diverse problem scales demonstrates that DO-LEC maintains sub-second computation times for large-scale scenarios while exhibiting predictable overhead characteristics essential for safety-critical systems. Unlike approximation-based methods that sacrifice optimality for speed, DO-LEC preserves geometric correctness while achieving practical real-time capability. The algorithm's bounded computational behavior and proven scalability establish it as the first Voronoi-based approach suitable for dynamic environments. This work removes a fundamental barrier to deploying geometrically rigorous clearance reasoning in autonomous robotics, interactive simulations, and adaptive facility planning, enabling applications where continuous spatial optimization amid moving obstacles is essential yet  previously computationally intractable.