An algorithm for realizing Euclidean distance matrices

Jorge Alencar; Tibérius Bonates; Carlile Lavor; Leo Liberti

doi:10.1016/j.endm.2015.07.066

An algorithm for realizing Euclidean distance matrices

Jorge Alencar
, Tibérius Bonates
, Carlile Lavor
, Leo Liberti

Instituto Federal de Educação, Ciência e Tecnologia do Sul de Minas Gerais - IFSULDEMINAS
Federal University of Ceara
University of Campinas (UNICAMP)

Research output: Contribution to journal › Article › peer-review

Abstract

We present an efficient algorithm to find a realization of a (full) n×. n squared Euclidean distance matrix in the smallest possible dimension. Most existing algorithms work in a given dimension: most of these can be transformed to an algorithm to find the minimum dimension, but gain a logarithmic factor of n in their worst-case running time. Our algorithm performs cubically in n (and linearly when the dimension is fixed, which happens in most applications).

Original language	English
Pages (from-to)	397-402
Number of pages	6
Journal	Electronic Notes in Discrete Mathematics
Volume	50
DOIs	https://doi.org/10.1016/j.endm.2015.07.066
Publication status	Published - 1 Dec 2015

Keywords

Distance geometry
EDM
Embedding dimension
Sphere interesection

Access to Document

10.1016/j.endm.2015.07.066

Cite this

@article{d8e422a63eae4f328e3c949bc12054d2,

title = "An algorithm for realizing Euclidean distance matrices",

abstract = "We present an efficient algorithm to find a realization of a (full) n×. n squared Euclidean distance matrix in the smallest possible dimension. Most existing algorithms work in a given dimension: most of these can be transformed to an algorithm to find the minimum dimension, but gain a logarithmic factor of n in their worst-case running time. Our algorithm performs cubically in n (and linearly when the dimension is fixed, which happens in most applications).",

keywords = "Distance geometry, EDM, Embedding dimension, Sphere interesection",

author = "Jorge Alencar and Tib{\'e}rius Bonates and Carlile Lavor and Leo Liberti",

note = "Publisher Copyright: {\textcopyright} 2015 Elsevier B.V.",

year = "2015",

month = dec,

day = "1",

doi = "10.1016/j.endm.2015.07.066",

language = "English",

volume = "50",

pages = "397--402",

journal = "Electronic Notes in Discrete Mathematics",

issn = "1571-0653",

}

TY - JOUR

T1 - An algorithm for realizing Euclidean distance matrices

AU - Alencar, Jorge

AU - Bonates, Tibérius

AU - Lavor, Carlile

AU - Liberti, Leo

PY - 2015/12/1

Y1 - 2015/12/1

N2 - We present an efficient algorithm to find a realization of a (full) n×. n squared Euclidean distance matrix in the smallest possible dimension. Most existing algorithms work in a given dimension: most of these can be transformed to an algorithm to find the minimum dimension, but gain a logarithmic factor of n in their worst-case running time. Our algorithm performs cubically in n (and linearly when the dimension is fixed, which happens in most applications).

AB - We present an efficient algorithm to find a realization of a (full) n×. n squared Euclidean distance matrix in the smallest possible dimension. Most existing algorithms work in a given dimension: most of these can be transformed to an algorithm to find the minimum dimension, but gain a logarithmic factor of n in their worst-case running time. Our algorithm performs cubically in n (and linearly when the dimension is fixed, which happens in most applications).

KW - Distance geometry

KW - EDM

KW - Embedding dimension

KW - Sphere interesection

U2 - 10.1016/j.endm.2015.07.066

DO - 10.1016/j.endm.2015.07.066

M3 - Article

AN - SCOPUS:84953399278

SN - 1571-0653

VL - 50

SP - 397

EP - 402

JO - Electronic Notes in Discrete Mathematics

JF - Electronic Notes in Discrete Mathematics

ER -

An algorithm for realizing Euclidean distance matrices

Abstract

Keywords

Access to Document

Fingerprint

Cite this