TY - JOUR

T1 - Fast geometric approximation techniques and geometric embedding problems

AU - Bern, Marshall W.

AU - Karloff, Howard J.

AU - Raghavan, Prabhakar

AU - Schieber, Baruch

N1 - Funding Information:
by NSF grant CCR 8807534. Watson Research Center.

PY - 1992/12/14

Y1 - 1992/12/14

N2 - Given an undirected n-vertex graph G and a set of n points in Rd, we wish to embed the vertices of G onto the points so as to minimize the total embedded edge length. Important special cases of this geometric embedding problem as those in which G is a binary tree, a cycle, or a star. We give fast approximation algorithms for embedding these graphs on the line and in the plane in several metrics. Our principal techniques are: a notion of "approximate geometric sorting" that can be computed in linear time, and fast approximation schemes for the minimum spanning tree problem in the plane. We expect that these approximation techniques can be applied to many geometric problems besides the embedding problem. We give the example of approximating the convex hull of a set of points in the plane.

AB - Given an undirected n-vertex graph G and a set of n points in Rd, we wish to embed the vertices of G onto the points so as to minimize the total embedded edge length. Important special cases of this geometric embedding problem as those in which G is a binary tree, a cycle, or a star. We give fast approximation algorithms for embedding these graphs on the line and in the plane in several metrics. Our principal techniques are: a notion of "approximate geometric sorting" that can be computed in linear time, and fast approximation schemes for the minimum spanning tree problem in the plane. We expect that these approximation techniques can be applied to many geometric problems besides the embedding problem. We give the example of approximating the convex hull of a set of points in the plane.

UR - http://www.scopus.com/inward/record.url?scp=0026966067&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0026966067&partnerID=8YFLogxK

U2 - 10.1016/0304-3975(92)90252-B

DO - 10.1016/0304-3975(92)90252-B

M3 - Article

AN - SCOPUS:0026966067

VL - 106

SP - 265

EP - 281

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

IS - 2

ER -