The challenge of optimally placing facilities to maximize coverage within road networks is a critical problem with significant implications for urban planning, emergency response, and the development of sustainable infrastructure. For instance, strategically locating fire stations or electric vehicle (EV) charging stations along a road network can greatly enhance public safety and support the adoption of clean transportation technologies. However, determining these optimal placements is computationally challenging, particularly when accounting for factors like road network distances and coverage radius. Traditional methods, such as greedy algorithms, offer a reasonable approximation but are limited by high computational complexity, making them less suitable for large-scale transportation networks. In response, our research introduces two novel algorithms designed to improve both the efficiency and scalability of the k-radius coverage problem. The first algorithm achieves a strong approximation with significantly reduced time complexity, while the second employs a sketch-based approach, offering a nearly linear time complexity relative to the number of edges. Although the second algorithm sacrifices some approximation accuracy, it offers substantial gains in computational speed, making it particularly valuable for large-scale transportation networks. Extensive experiments on large-scale real-world road networks demonstrate the superior performance of our proposed methods compared to existing solutions.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Efficient Algorithms for Approximate k-Radius Coverage Query on Large-Scale Road Networks


    Contributors:
    Li, Xiaocui (author) / He, Dan (author) / Zhang, Xinyu (author)


    Publication date :

    2025-02-01


    Size :

    876616 byte




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English



    Efficient Aerial Coverage Search in Road Networks

    Dille, Michael / Singh, Sanjiv | AIAA | 2013


    Efficient Collective Spatial Keyword Query Processing on Road Networks

    Gao, Yunjun / Zhao, Jingwen / Zheng, Baihua et al. | IEEE | 2016