Linear-Space Algorithms for Distance Preserving Embedding

  1. (PDF, 277 KB)
AuthorSearch for: ; Search for: ; Search for: ; Search for: ; Search for: ; Search for: ; Search for:
ConferenceCanadian Conference on Computational Geometry, August 20-22, 2007., Ottawa, Ontario, Canada
AbstractThe distance preserving graph embedding problem is to embed vertices of a given weighted graph into points in 2-dimensional Euclidean space so that for each edge the distance between their corresponding endpoints is as close to the weight of the edge as possible. If the given graph is complete, that is, if distance constraints are given as a full matrix, then principal coordinate analysis can solve it in polynomial time. A serious disadvantage is its quadratic space requirement. In this paper we develop linear-space algorithms for this problem. A key idea is to partition a set of n objects into disjoint subsets (clusters) of size O(pn) such that the minimum inter cluster distance is maximized among all possible such partitions.
Publication date
AffiliationNRC Institute for Information Technology; National Research Council Canada
Peer reviewedNo
NRC number49830
NPARC number8914111
Export citationExport as RIS
Report a correctionReport a correction
Record identifier3bc87f0b-6635-4d88-a0f8-ae2e34ec8886
Record created2009-04-22
Record modified2016-05-09
Bookmark and share
  • Share this page with Facebook (Opens in a new window)
  • Share this page with Twitter (Opens in a new window)
  • Share this page with Google+ (Opens in a new window)
  • Share this page with Delicious (Opens in a new window)