2024/07/22 by Elfarouk Harb, Harb, Elfarouk, Zhengcheng Huang +3 · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · Engineering · #Computational Geometry (cs.CG) #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Modular Robots and Swarm Intelligence #Robotic Path Planning Algorithms
paper · pdf · doi:10.48550/arxiv.2407.15980
openalex publication_date 2024/07/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We introduce a new balanced separator theorem for unit-disk graphs involving two shortest paths combined with the 1-hop neighbours of those paths and two other vertices. This answers an open problem of Yan, Xiang and Dragan [CGTA '12] and improves their result that requires removing the 3-hop neighborhood of two shortest paths. Our proof uses very different ideas, including Delaunay triangulations and a generalization of the celebrated balanced separator theorem of Lipton and Tarjan [J. Appl. Math. '79] to systems of non-intersecting paths.