Now showing items 1-3 of 3

    • An Efficient Algorithm for Computing High-Quality Paths Amid Polygonal Obstacles 

      Agarwal, P. K.; Fox, Kyle J.; Salzman, O.
      We study a path-planning problem amid a set O of obstacles in R², in which we wish to compute a short path between two points while also maintaining a high clearance from O; the clearance of a point is its distance from a ...
    • Computing the Gromov-Hausdorff Distance for Metric Trees 

      Agarwal, P. K.; Fox, Kyle J.; Nath, A.; Sidiropoulos, A.; Wang, Y.
      The Gromov-Hausdorff (GH) distance is a natural way to measure distance between two metric spaces. We prove that it is NP-hard to approximate the GH distance better than a factor of 3 for geodesic metrics on a pair of ...
    • Holiest Minimum-Cost Paths and Flows in Surface Graphs 

      Erickson, J.; Fox, Kyle J.; Lkhamsuren, L.
      Let G be an edge-weighted directed graph with n vertices embedded on an orientable surface of genus g. We describe a simple deterministic lexicographic perturbation scheme that guarantees uniqueness of minimum-cost flows ...