2021/06/09 by Shinwoo An, An, Shinwoo, Eunjin Oh +1
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #cs.CG
paper · pdf · doi:10.48550/arxiv.2106.04973
To appear in WADS2021
arxiv created 2021/06/09 · openalex publication_date 2021/06/09 · arxiv updated 2021/06/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let P be a set of n points in the plane where each point p of P is associated with a radius rp>0.The transmission graph G=(P,E) of P is defined as the directed graph such that E contains an edge from p to q if and only if |pq|≤ rp for any two points p and q in P, where |pq| denotes the Euclidean distance between p and q. In this paper, we present a data structure of size O(n5/3) such that for any two points in P, we can check in O(n2/3) time if there is a path in G between the two points. This is the first data structure for answering reachability queries whose performance depends only on n but not on the number of edges.