Introduction Enveloppe injective Algorithme Question

De
Publié par

logo Introduction Enveloppe injective Algorithme Question Plongement isometrique dans le plan rectilineaire en temps optimal O(n2) Nicolas Catusse, Victor Chepoi, Yann Vaxes Universite de la Mediterranee Faculte des Sciences de Luminy

  • x8 x6

  • x1 x2

  • espace metrique

  • rk avec la norme l∞

  • temps polynomial

  • plongement isometrique dans le plan rectilineaire en temps optimal

  • faculte des sciences de luminy


Publié le : mardi 19 juin 2012
Lecture(s) : 55
Source : lirmm.fr
Nombre de pages : 34
Voir plus Voir moins
IntroductioEnvnlepoepniejtceAivorlghmitueeQoitsn
NicolasCatusse, VictorChepoi, Yannax`esV
Faculte´desSciencesdeLuminy
Universite´delaMe´diterrane´e
logo
Plongementisome´triquedansleplanre´ctiline´aire en temps optimalO(n2)
nIdortitcuitevlAogirhtemuQonEnveloppeinjeconties
2
Enveloppe injective
Algorithme
3
logo
1
Introduction
Question
4
Probl` eme ´ Etantdonneunespacem´etrique(X,d),´dcedireaceestsicetesp ´ plongeableisome´triquementdansR2etm´alvaecequril1oul.
Plongement Unespaceme´trique(X,dgeonplstomisleabeuqirte´snadtneme) unespacem´etrique(Y,d0) si il existe une applicationϕ:XY tel qued0(ϕ(x), ϕ(y)) =d(x,y) pour toutx,yX.
logo
nEnveloproductioItnlonPiostueeQhmitroglAevitcejniepiren´eatilinrecpealnalsnedtgnme
ithmeQueiveAlgorumalitnotsoiFnroeemprdul`ob
Proble`me ´ Etantdonne´unespacem´etrique(X,d),tescepaeseticedsre´icd plongeableisome´triquementdansR2aevclam´etriquel1(oul).
logo
x1x2x3x4x5x6x7x8 x10 3 2 4 5 4 7 4 x23 0 3 1 2 3 4 5 x32 3 0 2 3 2 5 2 x44 1 2 0 1 2 3 4 x55 2 3 1 0 3 3 5 x64 3 2 2 3 0 3 2 x77 4 5 3 2 3 0 5 x84 5 2 4 5 2 5 0
peinjectnEnveloporudtcoiItn
rontInEioctduoriteAlguesthmeQpoepvnletcviniejrtelatatdionE
MengeretSch¨onberg(1928):On peut d´cider en temps e polynomial si (X,d)peusno´gdenaˆtteerlpRkavec la metrique Euclidienne. ´ Frechet :´gnolpersnadeoTapectuseriqum´ettˆetepeuRk avec la normel. Bandelt, Chepoi (1998) :ˆtueerteUnespacem´etri que p plonge´dansleplanl1ssi n’importe quel sous espace d’au plus 6pointspeutlˆetre. Edmonds (2008) :nsiceenoimethd´deAlrigoO(n2log2n). Eppstein (2009) :timhdedeAglronoisice´neO(n2).
logo
1
3
2
Enveloppe injective
logo
Introduction
Question
4
Algorithme
IortntcviniejrotiAeglionEductoppenvelstueeQhmnio
onEnuctitrodIntiesQumethrigoAlevitcejnieppolev
Enveloppe injective Pourtoutespacem´etrique(X,d) il existe un plus petit espace injectifT(X) dans lequel on peut plonger (X,d).
logo
Figure1:Enveloppe injective sur 3 et 4 points
D´onnieonti
ItnelopnEnvctioroduQeeutimhntsoijectpeinlgoriveA
Enveloppe
logo
sur
injective
Enveloppe
injective
Figure
2:
points
sur
5
5
points
tiecnjeipploveEnnoitcudortnItionhtemuQseevlAogir
T(X)
l1
m´etrique
la
n in=1(j=
I(xi,xj))
i=1(j=1
=
Avec
logo
Envelop
Enveloppe
injective dans (R2,l1)
trodInnonEevolemuQseittivedansppeinjecolevieppitcunEnogoAlthriecnjveti(R2,l1)
Aveclam´etriquel1T(X) =in=1(jn=1I(xi,xj))
logo
,
l1
)
logo
dans
injective
e
Envelopp
(R
2
loppeinjectiveAlnIrtdocuitnonEevirogemhtseuQnoit
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.