Using FastMap to Solve Graph Problems in a Euclidean Space

  • Jiaoyang Li University of Southern California
  • Ariel Felner Ben-Gurion University
  • Sven Koenig University of Southern California
  • T. K. Satish Kumar University of Southern California

Abstract

It is well known that many graph problems, like the Traveling Salesman Problem, are easier to solve in a Euclidean space. This motivates the idea of quickly preprocessing a given graph by embedding it in a Euclidean space to solve graph problems efficiently. In this paper, we study a nearlinear time algorithm, called FastMap, that embeds a given non-negative edge-weighted undirected graph in a Euclidean space and approximately preserves the pairwise shortest path distances between vertices. The Euclidean space can then be used either for heuristic guidance of A* (as suggested previously) or for geometric interpretations that facilitate the application of techniques from analytical geometry. We present a new variant of FastMap and compare it with the original variant theoretically and empirically. We demonstrate its usefulness for solving a path-finding and a multi-agent meeting problem.

Published
2019-07-06