2024/12/11 by Kevin Buchin, Antonia Kalb, Buchin, Kevin +11 · 1 voice
Computer Science · #Computational Geometry (cs.CG) #FOS: Computer and information sciences #cs.CG
paper · pdf · doi:10.48550/arxiv.2412.08165
Given a point set P in a metric space and a real number t ≥ 1, an oriented t-spanner is an oriented graph \overrightarrowG=(P,\overrightarrowE), where for every pair of distinct points p and q in P, the shortest oriented closed walk in \overrightarrowG that contains p and q is at most a factor t longer than the perimeter of the smallest triangle in P containing p and q. The oriented dilation of a graph \overrightarrowG is the minimum t for which \overrightarrowG is an oriented t-spanner. We present the first algorithm that computes, in Euclidean space, a sparse oriented spanner whose oriented dilation is bounded by a constant. More specifically, for any set of n points in ℝd, where d is a constant, we construct an oriented (2+ε)-spanner with O(n) edges in O(n log n) time and O(n) space. Our construction uses the well-separated pair decomposition and an algorithm that computes a (1+ε)-approximation of the minimum-perimeter triangle in P containing two given query points in O(log n) time. While our algorithm is based on first computing a suitable undirected graph and then orienting it, we show that, in general, computing the orientation of an undirected graph that minimises its oriented dilation is NP-hard, even for point sets in the Euclidean plane. We further prove that even if the orientation is already given, computing the oriented dilation is APSP-hard for points in a general metric space. We complement this result with an algorithm that approximates the oriented dilation of a given graph in subcubic time for point sets in ℝd, where d is a constant.