Hyperconvexity and metric embedding

David Eppstein
University of California, Irvine (UCI)
Information and Computer Science

A metric is hyperconvex if its metric balls satisfy the Helly property: any pairwise intersecting family of balls has a common intersection. Examples of hyperconvex spaces include trees, and vector spaces with the L-infinity norm. We survey results related to hyperconvex spaces and the tight span, an embedding of an arbitrary metric space into a hyperconvex space that is closely related to rectilinear convex hulls. We describe how to use tight spans and hyperconvexity to efficiently find embeddings of distance matrices into the Manhattan plane and into star metrics.

Presentation (PDF File)

Back to Workshop II: Combinatorial Geometry