Computing the Fréchet distance between piecewise smooth curves
Abstract
We consider the Fréchet distance between two curves which are given as a sequence of m+n curved pieces. If these pieces are sufficiently well-ehaved, we can compute the Fréchet distance in O(mn log(mn)) time. The decision version of the problem can be solved in O(mn) time.
Full text
Compu ing he F ehe Dis ane
b e ween Pieewise Smo o h Cu es
?
G un e Ro e
F eie Uni e si a Be lin, Ins i u u In o ma ik, Takus ae 9, 14195 Be lin, Ge many, o ein . u-be lin.de.
Abs a
We onside he F ehe dis ane be ween wo u es whih a e gi en as a sequene o
m
+
n
u ed piees. I hese
piees a e suÆien ly well-b eha ed, we an ompu e he F ehe dis ane in
O
(
mn
log (
mn
)) ime. The deision
e sion o he p oblem an b e sol ed in
O
(
mn
) ime.
1. In o du ion
The F ehe dis ane is a dis ane measu e b e-
ween u es.
Deni ion 1 (F ehe dis ane)
Le
:
I
= [
l
I
;
I
℄
!
R
2
and
g
:
J
= [
l
J
;
J
℄
!
R
2
be wo plana u es, and le
kk
deno e he Eu-
lidean no m. Then he
F ehe dis ane
Æ
F
(
; g
)
is dened as
Æ
F
(
; g
) := in
: [0
;
1℄
!
I
: [0
;
1℄
!
J
max
2
[0
;
1℄
k
(
(
))
g
(
(
))
k
:
whe e
and
ange o e on inuous and non-
de easing epa ame e iza ions wi h
(0) =
l
I
,
(1) =
I
,
(0) =
l
J
,
(1) =
J
.
In on as o o he ommon dis ane measu es
like he Hausdo dis ane, he F ehe dis ane e-
sp e s he one-dimensional s u u e o he u es
and do esn' jus ea hem as a poin se .
The s udy o he F ehe dis ane om a om-
pu a ional p oin o iew has b een ini ia ed by Al
and Go dau [2℄. The
deision p oblem
is he p ob-
lem o deide, o a gi en
"
, whe he he F ehe
dis ane b e ween wo u es is a mos
"
.
Al and Godau [2℄ ea ed he ase o wo polyg-
onal u es. Fo wo u es o
m
and
n
piees, e-
sp e i ely, hey showed how o sol e he deision
p oblem in
O
(
mn
) ime and he op imiza ion p ob-
?
Pa ially suppo ed by he IST P og amme o he EU
as a Sha ed-os RTD (FET Op en) P o je unde Con-
a No IST-2000-26473 (ECG|Ee i e Compu a ional
Geome y o Cu es and Su aes).
lem in
O
(
mn
log(
mn
)) ime. Some ela ed p ob-
lems ha e also been onside ed, like minimizing
he F ehe dis ane unde ansla ions [3℄, o a
gene alized F ehe dis ane b e ween a u e and
a
g aph
[1℄. In all ases, howe e , he ob je s a e
pieewise linea .
In his pap e , we explo e he F ehe dis ane
b e ween mo e gene al u es. We assume ha eah
inpu u e is gi en as a sequene o smo o h u e
piees ha a e suÆien ly well-b eha ed", suh as
i ula a s, pa ab oli a s, o some lass o spline
u es. Ou algo i hm will p e o m e ain op e a-
ions on hese u es, like in e se ing hem wi h
a i le.
We will show ha he
ombina o ial omplexi y
,
i. e., he numbe o s eps, o sol ing he deision
p oblem is no la ge han o p olygonal pa hs,
O
(
mn
). The omplexi y o he indi idual op e a-
ions ( he
algeb ai omplexi y
) dep ends o ou se
on he na u e o he u es. Unde he s onge as-
sump ion ha he u es onsis o algeb ai piees
whose deg ee is bounded by a ons an , we an
sol e he op imiza ion p oblem in
O
(
mn
log(
mn
)),
hus ma hing he unning ime o he polygonal
ase. The elemen a y op e a ions, howe e , a e al-
geb ai op e a ions o highe deg ee.
We assume ha eah u e is gi en as a sequene
o piees whih a e onne ed a hei endp oin s.
E e y piee is a smo o h u e o lass
C
2
, i. e., he
u a u e is dened e e ywhe e and a ies on in-
uously wi hin a piee. We will no make any as-
sump ions how he u es a e gi en; i is only im-
p o an ha he neessa y geome i op e a ions
20 h EWCG Se ille, Spain (2004)
20 h Eu op ean Wo kshop on Compu a ional Geome y
an b e a ied ou .
We need u es whose u ning angle is bounded
by
. Cu es o la ge b ounding angle mus b e
sub di ided. Fo sol ing he deision p oblem wi h
pa ame e
"
, we sub di ide he u e a all poin s
whe e he u a u e is 1
="
, in o de o ensu e ha
in eah piee o he u e, he u a u e is ei he
uni o mly smalle o bigge han 1
="
.
We ha e omi ed mos p o o s, bu we s a e one
auxilia y lemma in o de o illus a e he elemen-
a y a gumen s on whih he esul s a e based.
Lemma 2
Le
be a smoo h u e o u ning angle
a mos
, and le
by a i le o adius
.
(a)
I he u a u e o
is a mos
1
=
e e y-
whe e, he u e an in e se
a mos wie.
I i in e se s
wie, hen i s endpoin s lie
ou side
o on he bounda y, and he mid-
d le piee be ween he wo in e se ions lies
inside
.
(b)
I he u a u e o
is a leas
1
=
e e y-
whe e, he u e an in e se
a mos wie.
The ull e sion o his pap e is a ailable as a
ehnial ep o [5℄.
2. The F ee Spae Diag am
The main o ol o he algo i hm is he
ee spae
diag am
whih was in o dued in [2℄. I is a wo-
dimensional ep esen a ion o all pai s o p oin s on
he wo u es, oge he wi h he iden ia ion o
hose pai s whih a e lose han
"
.
Deni ion 3
Le
:
I
!
R
2
,
g
:
J
!
R
2
be wo
u es,
I ; J
R
. The se
F
"
(
; g
) :=
(
s;
)
2
I
J
:
k
(
s
)
g
(
)
k
"
g
deno es he
ee spae
o
and
g
. he pa i ion o
I
J
in o he ee spae and i s omplemen is al led
he
ee spae diag am
.
Poin s in
F
"
a e alled
easible
o
ee
, and hey
a e usually d awn in whi e. The o he p oin s a e
alled
o bidden poin s
o
obs ales
, see Figu e 1.
The ollowing simple obse a ion om [2℄ is uial.
Lemma 4
Le
:
I
= [
l
I
;
I
℄
!
R
2
,
g
:
J
=
[
l
J
;
J
℄
!
R
2
be wo u es. Then
Æ
F
(
; g
)
"
i and only i he e exis s a u e wi hin
F
"
(
; g
)
om
(
l
I
; l
J
)
o
(
I
;
J
)
whih is mono one in bo h
oo dina es.
2
As
and
g
onsis o se e al piees, he ee
spae diag am deomp oses na u ally in o a g id o
e angula
el ls
.
ε
g
Fig. 1. Two p olygonal u es and hei ee spae diag am.
The sale o he ee spae diag am is 50% edued wi h
esp e o he u es.
3. C i ial p oin s
We ega ds as
i ial poin s
on he b ounda y o
F
"
hose p oin s whih a e lo al ex ema in he ho -
izon al o e ial di e ion. The e a e eigh lasses
o i ial p oin s, shown in Figu e 2.
W+
N+
S+
E+
N−
E−
S−
W−
Fig. 2. The eigh ypes o i ial p oin s.
N
,
S
,
E
,
W
e e s o he di e ion in whih he p oin is ex eme, and
he sup e s ip ells whe he he a ea in his di e ion is
easible (+) o o bidden (
).
In e ms o he u es
and
g
, hese p oin s o -
esp ond o si ua ions whe e a i le
o adius
"
a ound a poin o one u e is angen o he o he
u e. Fo example, a i ial poin o yp e
W
+
o -
u s in he si ua ion whe e
g
ouhes he i le
o
adius
"
a ound a p oin
x
on
om inside. As
x
p o eeds u he away om
g
, a po ion o
g
b egins
o s ik ou om
.
Ma h 25-26, 2004 Se ille (Spain)
4. The s u u e o a single ell
The ee spae may b e a bi a ily omplia ed
e en inside a ell. Fo example, i
"
is e y small,
F
"
will on ain isola ed islands o ee spae o all
in e se ions b e ween
and
g
. Howe e , we will
show ha he eahable p oin s an b e ompu ed
in a ons an numb e o elemen a y geome i op-
e a ions.
We ha e sub di ided he u es, and onse-
quen ly, he pa ame e in e als
I
and
J
in o
m
and
n
piees, esp e i ely. Co esp ondingly, we u
he e angle
I
J
in o
mn
ells. On he b ound-
a ies o hese ells, we ompu e all p oin s whih a e
eahable
om he lowe le o ne (
l
I
; l
J
) o he
e angle by a pa h in ee spae whih is mono-
one in b o h di e ions. We do his in emen ally
om he lowe le ell o he upp e mos igh ell.
A e ial line in he ee-spae diag am o e-
sp onds o a xed p oin
(
s
) on
. The p oin s in
F
"
on his line o espond o he poin s o
g
whih
lie inside a i le
o adius
"
a ound
(
s
). The
b ounda y o
F
"
o esp onds o he in e se ions o
wi h
g
, and hene we an apply Lemma 2.
Lemma 5
Inside a el l, a e ial o ho izon al
line in e se s he bounda y o
F
"
a mos wie.
A e ial angen line ough a i ial poin o
ype
E
o
W
o a ho izon al angen line ough
a i ial poin o ype
N
o
S
does no oss he
bounda y o
F
"
in any o he poin .
2
Lemma 6
A u e o ming a omponen o he
bounda y o he ee spae inside a el l an on ain
a mos ou i ial poin s.
2
This lemma implies ha he e is a limi ed num-
b e o p ossibili ies o suh a b ounda y, he mos
omplia ed b eing an s-shaped" pa h be ween b e-
ween he le edge and he igh edge o he e -
angle, on aining wo i ial p oin s
S
+
and
N
.
5. P o essing a ell
We a e gi en he eahable p oin s on he le and
b o om edge, and we ompu e he p oin s on he
igh edge and on he op edge whih a e eahable
om he e.
On eah edge o he e angle he e a e a mos
wo in e als o ee p oin s, by Lemma 5. Inside
eah in e al o ee poin s, he e is only a single
in e al o eahable p oin s b eause om e e y ee
p oin , e e y hing whih is o he igh o o he op
in he same ee in e al is eahable di e ly.
We will illus a e how o ompu e he
le mos
eahable p oin in eah ee in e al on he op edge
om a gi en in e al
X
on le edge. O he ases
a e simila .
We a e gi en he lowes eahable p oin
B
in
X
. The uppe end o
X
may b e he upp e le
o ne o he e angle, o i may b e a o bidden
p oin whih belongs o a omp onen
O
o o bidden
p oin s. Simila ly, he le endp oin
F
o
Y
may
b e pa o a omponen o o bidden poin s, whih
we deno e by
O
2
. (
O
and
O
2
a e no neessa ily
die en , see Figu e 3a.)
Lemma 7
The le mos poin
U
in
Y
eahable
om
X
depends only on he p esene and he ela-
i e loa ions o
O
and
O
2
and he ho izon al line
h ough
B
.
PROOF.
We ha e o show ha any o he ob-
s ales" o o bidden p oin s do no play any ole in
his ques ion. We show his by gi ing an algo i hm
o ons u ing
U
in all ases.
I he ho izon al line h ough
B
in e se s
O
o
O
2
, i is lea ha one anno eah
Y
, see o ex-
ample he in e al
X
1
in Figu e 3a o he in e -
al
X
2
in onne ion wi h
Y
2
in Figu e 3b. O he -
wise, we laim ha he desi ed p oin
U
lies di e ly
ab o e he igh mos p oin o
O
o o
O
2
, whihe e
is u he o he igh .
The mono one pa h om
X
o
Y
has o pass
o he igh o
O
and
O
2
. Thus, no poin in
Y
le o
U
is eahable om
X
. To see ha
U
is
eahable, onside s he ase ha
O
exis s, see
he example o he in e al
X
1
in Figu e 3b. Le
A
b e he igh mos p oin o
O
.
A
an lie on he uppe
edge, o i an b e a i ial p oin o yp e
E
+
.
Assume s ha
A
is a i ial p oin o yp e
E
+
. The e ial line
a
h ough
A
lies omple ely
in he ee spae, by Lemma 5, and
O
is he only
obs ale le o
a
. By assump ion, he ho izon al
line
b
om he lowes eahable p oin
B
in
X
do es
no in e se
O
b e o e eahing
a
, and he e a e no
o he obs ales in his ange. Thus,
A
is eahable
om
B
, and he upp e end
A
0
o
a
is he le mos
eahable p oin on he op edge. I i lies in
Y
, we
an ake i as ou p oin
U
, and we a e done. (This is
he ase o he in e als
X
1
and
Y
1
in Figu e 3b.)
I
Y
lies le o
a
, we a e done as well, as no p oin s
in
Y
a e eahable om
X
. So le us deal wi h he
20 h Eu op ean Wo kshop on Compu a ional Geome y
B
O
F
AB
B2
a
A′
A
O
b
O2
FC′
C
(a) (b)
D
Y1Y2Y1Y2
X2
X1
X2
X1
Fig. 3. De e mining he eahable p oin s on he op edge
only emaining ase ha
Y
lies o he igh o
a
,
and
a
is sepa a ed om
Y
by he obs ale
O
2
.
The lowes p oin
D
o
O
2
mus lie ab o e
O
, and
he ho izon al line h ough
D
in e se s
a
, whih
is eahable. The e o e
D
is eahable. F om
D
we
an eah he igh mos p oin
C
o
O
2
, whih is
ei he a i ial poin o yp e
E
+
o he p oin
F
.
In ei he ase, we an indeed eah he poin
C
0
e ially ab o e
C
as he le mos p oin
U
.
The ases when
O
do es no exis , o when he
igh mos poin
A
o
O
lies on he upp e edge, an
b e ea ed simila ly.
2
Will ha e des ib ed ou p oedu e in e ms o
geome i op e a ions in he ee spae diag am,
like nding he igh -mos poin in a omp onen o
o bidden p oin s. By wo king ou wha hese op-
e a ions mean in e ms o he u es
and
g
, we
ob ain he ollowing heo ems.
Theo em 8
Gi en he eahable poin s on he bo -
om edge and he le edge o a el l, he eahable
poin s on he op edge and he igh edge o he el l
an be ompu ed in a ons an numbe o he ol-
lowing ope a ions:
{ In e se ing a i le o adius
"
wi h one o he
u es
{ Finding he s in e se ion o one u e wi h
an ose u e o he o he u e a dis ane
"
.
In bo h ases, we mus be able o nd he pa ame e
alues on he espe i e u es, o esponding o
he poin s ha we ha e ompu ed.
2
Theo em 9
Gi en wo u es onsis ing o
m
and
n
piees, espe i ely, whe e eah piee has a u n-
ing angle a mos
and has u a u e
"
o
"
h oughou , we an deide
O
(
m
+
n
)
spae and in
O
(
mn
)
p imi i e ope a ions o he ype des ibed
in Theo em 8 whe he hei F ehe dis ane is a
mos
"
, o a gi en pa ame e
"
.
2
6. The Minimiza ion P oblem
The minimiza ion p oblem o
ompu ing
he
F ehe dis ane an b e sol ed by Megiddo's pa a-
me i sea h ehnique [4℄, losely ollowing he
app oah o [2℄ o p olygonal u es. The ehnial
de ails a e mo e in ol ed, and we ha e o make
some s onge assump ions on he u es.
Theo em 10
Gi en wo u es onsis ing o
m
and
n
piees, espe i ely, o smoo h algeb ai
u es o xed maximum deg ee we an ompu e
hei F ehe dis ane in
O
(
nm
)
spae and in
O
(
mn
log(
mn
))
algeb ai ope a ions, i.e., deg ee
ompa ison be ween wo eal solu ions o algeb ai
equa ions o bounded deg ee.
2
Re e enes
[1℄ H. Al , A. E a , G. Ro e, and C. Wenk,
Ma hing
plana maps
, Jou nal o Algo i hms
49
(2003), 262{283.
[2℄ H. Al and M. Go dau,
Compu ing he F ehe dis ane
be ween wo polygonal u es
, In e na . J. Compu .
Geom. Appl.
5
(1995), 75{91.
[3℄ H. Al , C. Knaue , and C. Wenk,
Ma hing polygonal
u es wi h espe o he F ehe dis ane
, STACS 2001
(A. Fe ei a and H. Reihel, eds.), Le . No es Comp.
Si., ol. 2010, Sp inge -Ve lag, 2001, pp. 63{74.
[4℄ N. Megiddo,
Applying pa al lel ompu a ion algo i hms
in he design o se ial algo i hms
, J. Asso . Compu .
Mah.
30
(1983), 852{865.
[5℄ G un e Ro e,
Compu ing he ehe dis ane be ween
pieewise smoo h u es
, Teh. Rep o ECG-TR-
241108-01, 2003.