EMBEDDING METRIC-SPACES IN THE RECTILINEAR PLANE - A 6-POINT CRITERION

Authors
BANDELT HJ CHEPOI V
Citation
Hj. Bandelt et V. Chepoi, EMBEDDING METRIC-SPACES IN THE RECTILINEAR PLANE - A 6-POINT CRITERION, Discrete & computational geometry, 15(1), 1996, pp. 107-117
Citations number
12
Categorie Soggetti
Computer Sciences, Special Topics","Mathematics, General","Computer Science Theory & Methods",Mathematics
Journal title
Discrete & computational geometry → ACNP
ISSN journal
01795376
Volume
15
Issue
1
Year of publication
1996
Pages
107 - 117
Database
ISI
SICI code
0179-5376(1996)15:1<107:EMITRP>2.0.ZU;2-V
Abstract
We show that a metric space embeds in the rectilinear plane (i.e., is L(1)-embeddable in R(2)) if and only if every subspace with five or si x points does. A simple construction shows that for higher dimensions k of the host rectilinear space the number c(k) of points that need to be tested grows at least quadratically with k, thus disproving a conj ecture of Seth and Jerome Malitz.