Simila i iy Sea ch in Semialgeb aic Pa e n Spaces
(Ex ended Abs ac )
Ch is ian Knaue a
aIns i u ¨u In o ma ik, F eie Uni e si ¨a Be lin, Takus aße 9, D-14195 Be lin, Ge many
Abs ac
We desc ibe a gene al echnique o cons uc da a s uc u es o simila i y sea ch in semialgeb aic pa e n spaces.
These spaces cap u e mos known combina ions o geome ic pa e ns (e.g., poin se s, polygons, polygonal cu es)
and geome ic dis ance measu es o hem (e.g. Hausdo -dis ance, a ea o o e lap, F ´eche -dis ance) oge he
wi h hei quo ien s unde a ious ans o ma ion classes (e.g., ansla ions, igid mo ions) and hey p o ide he
i s non- i ial exac sea ch s uc u es in hese se ings.
Key wo ds: Compu a ional geome y, Shape ma ching, Simila i y que ies, Da a s uc u es
1. In oduc ion
Simila i y sea ch is a much-s udied and p ac i-
cally impo an ype o p oblem: Gi en a se D
o npa e ns om a sui able class o alid geo-
me ic pa e ns (e.g., polygonal cu es), p ep ocess
hem in such a way ha we can de e mine quickly
o a que y pa e n Q, which o he np ep ocessed
pa e ns is mos simila o he que y objec ( his
is called a simila i y que y). We assume ha we
ha e an app op ia e dis ance measu e δ(e.g., he
smalles F ´eche dis ance ha can be achie ed un-
de ansla ions) o asses he simila i y o wo pa -
e ns.
Sa is ac o y algo i hmic esul s exis only in he
case ha he pa e ns can be encoded in a Eu-
clidean space, o an L1- o L∞-space such ha
δis he co esponding me ic [9], o in he case
ha hey can be embedded in such spaces wi h
a low dis o ion [7,6]. Then we ha e a ailable he
e y powe ul echniques o Vo onoi decomposi-
ions. Some algo i hms we e o mula ed wi h ‘ an-
age poin s’ o simila de ices [2,3,5,10], bu hen
he e a e no gene al pe o mance bounds: only un-
de addi ional assump ions ha en o ce in some
way ha he dis ance measu e is a me ic ha is
Email add ess: Ch is ian.Knaue @in . u-be lin.de
(Ch is ian Knaue ).
‘simila ’ o a Euclidean me ic i is possible o ob-
ain non i ial bound on he pe o mance o hese
algo i hms [9].
In his pape , we s udy he case whe e he size
o he indi idual pa e ns is small, compa ed o n.
To be mo e p ecise, we assume ha |I|=O(1)
o all I∈ D. In ha case he dis ances δ(Q, I),
can be compu ed in O(1) ime ( o easonable δ).
So he que y can be answe ed in O(n) ime wi h-
ou addi ional s o age and p ep ocessing, bu up
o now he e a e no algo i hms and da a s uc u es
ha allow such que ies wi h a non i ial que y
ime among p ep ocessed pa e n se s. We de-
sc ibe a gene al echnique o cons uc da a s uc-
u es o simila i y que ies o many combina ions
o geome ic pa e ns (e.g., poin se s, polygons,
polygonal cu es) and geome ic dis ance measu es
(e.g. Hausdo -dis ance, a ea o o e lap, F ´eche -
dis ance) oge he wi h hei quo ien s unde a i-
ous ans o ma ion classes (e.g., ansla ions, igid
mo ions). The solu ion achie es sublinea que y
ime wi h quad a ic p ep ocessing ime and s o -
age and p o ides he i s non- i ial sea ch s uc-
u es in hese se ings.
Apa e n space Π = (Ω, δ) o dimension dis
a se o geome ic objec s Ω, whe e each objec
can be desc ibed by exac ly d eal pa ame e s, o-
ge he wi h a dis ance measu e δ ha maps pai s
o objec s o non-nega i e eal numbe s. Usually
20 h EWCG Se ille, Spain (2004)
20 h Eu opean Wo kshop on Compu a ional Geome y
we iden i y Ω wi h Rd, he pa ame e space o Π.
The objec s in Ω a e called pa e ns. In ui i ely,
when δ(P, I) is small, we conside he pa e ns P
and I o be simila . No e ha we do no demand
ha δhas some special p ope ies (like being a
me ic, e c.). As an example conside polygonal
chains in he plane wi h a mos e ices and he
F ´eche -dis ance as a dis ance measu e. Each such
chain can be encoded by a sequence o a mos 2
eal numbe s, he coo dina es o he e ices o he
chain. I a chain has less han e ices we can
simply pad his desc ip ion by epea ing he las
e ex; no e ha his padding does no in e e e
wi h he dis ance unc ion.
A pa e n space Π = (Rd, δ) is called semialge-
b aic, i he se FΠ:= {(P, I, ǫ)∈Rd×Rd×R|
δ(P, I)≤ǫ}is semialgeb aic, i.e., he e is a boolean
o mula Bin sboolean a iables z1, . . . , zs, and
he e a e spolynomials g1,...,gsin (2d+ 1) eal
a iables xP,xI, xǫ(xPand xIa e ac ually se-
quences o d a iables each), such ha
δ(P, I)≤ǫ⇐⇒
B(z1←[g1(xP←P, xI←I, xǫ←ǫ)≥0],
...
zs←[gs(xP←P, xI←I, xǫ←ǫ)≥0])
is ue
(←deno es a iable subs i u ion and [X] is he
u h alue o he p edica e X).
As an example conside he se o all poin se s
in he plane wi h a mos poin s each and he di-
ec ed Hausdo -dis ance as a dis ance measu e.
Recall ha o compac se s P, I ⊆Rd he di-
ec ed Hausdo dis ance om P o I, is de ined as
h(P, I) := maxx∈Pminy∈I||x−y||.
This is a pa e n space o dimension 2 , since
each pa e n Pcan be encoded by a sequence o a
mos 2 eal numbe s, he coo dina es o he poin s
in P. I Phas less han poin s we can simply pad
his desc ip ion by epea ing some poin ; no e ha
his padding does no in e e e wi h he dis ance
unc ion. To see ha i is ac ually a semialgeb aic
pa e n space, no e ha o wo ini e poin se s P,
Iand ǫ > 0 we ha e ha
h(P, I)≤ǫ⇐⇒ ∀p∈P∃i∈I:||p−i||2−ǫ2≤0
⇐⇒ ^
p∈P
∃i∈I:||p−i||2−ǫ2≤0
⇐⇒ ^
p∈P
_
i∈I
||p−i||2−ǫ2≤0.
We will see in Sec ion 3 ha he no ion o a
semialgeb aic pa e n space cap u es mos known
combina ions o geome ic pa e ns (e.g., poin
se s, polygons, polygonal cu es) and geome ic
dis ance measu es (e.g. Hausdo -dis ance, a ea o
o e lap, F ´eche -dis ance) oge he wi h hei quo-
ien s unde a ious ans o ma ion classes.
In his pape , we s udy he p oblem o simila i y
sea ch among pa e ns om a semialgeb aic pa -
e n space whe e he size o he indi idual pa -
e ns is small, compa ed o hei numbe : Gi en a
da a se D ha consis s o npa e ns om a semi-
algeb aic pa e n space Π = (Ω, δ)o dimension
d, whe e dis cons an , p ep ocess Din o a da a
s uc u e o answe he ollowing kind o simila i y
que ies: Fo a que y pa e n Q∈Ω, de e mine
–∆(Q, D) := mina gI∈D δ(Q, I), he se o pa -
e ns in D o which Qhas he smalles possible
dis ance, and
–∆(D, Q) := mina gI∈D δ(I, Q), he se o pa -
e ns in D ha ha e he smalles possible dis ance
o Q.
Since dis cons an , he dis ances δ(Q, I), can be
compu ed in O(1) ime ( o easonable δ). So hese
que ies can be answe ed in O(n+k) ime (whe e k
is he size o he answe ) wi hou addi ional s o -
age and p ep ocessing, bu up o now he e a e
no algo i hms and da a s uc u es ha allow such
que ies wi h a non i ial que y ime among p ep o-
cessed pa e n se s.
We will also conside he decision e sion o
he simila i y que ies, called ǫ-simila i y que ies,
whe e we a e gi en an addi ional pa ame e ǫ > 0,
and we wan o de e mine
– ∆(Q, D, ǫ) := {I∈ D | δ(Q, I)≤ǫ}, he se o
pa e ns in D o which Qhas dis ance a mos
ǫ, and
– ∆(D, Q, ǫ) := {I∈ D | δ(I, Q)≤ǫ}, he se o
pa e ns in D ha ha e dis ance a mos ǫ o Q.
Again he b u e- o ce app oach can answe hese
que ies in O(n+k) ime, bu he e a e no da a
s uc u es ha allow such que ies wi h a non i ial
que y ime among p ep ocessed pa e n se s.
2. Simila i iy que ies in pa e n spaces
In his abs ac we only conside he decision
e sion o he simila i y que ies. We desc ibe a da a
s uc u e ha answe s ∆(Q, D, ǫ)-que ies ( he case
Ma ch 25-26, 2004 Se ille (Spain)
o ∆(D, Q, ǫ)-que ies is comple ely symme ic).
The same echniques apply o simila i y que ies as
well and yield simila esul s. Ou main esul is
he ollowing
Theo em 1 Suppose we a e gi en a se D ha
consis s o npa e ns om a semialgeb aic pa e n
space Πo dimension d=O(1). Then we can build
in O(n2) ime a da a s uc u e o size O(n2) ha
answe s ǫ-simila i y que ies in O(n1−1/(2d−3) +k)
ime, whe e kis he size o he answe .
PROOF. The cons uc ion wo ks in wo s eps.
We i s desc ibe a da a s uc u e ha can be buil
in O(n2d−2) ime (and equi es he same amoun
o space) and can answe a que y in O(log n+k)
ime, whe e kis he size o he answe . Then we
use a simple pa i ioning app oach o yield he de-
si ed esul (in ac we p o e a somewha s onge
adeo ha implies he Theo em).
Since Π = (Ω, δ) is a semialgeb aic pa e n space
o dimension d=O(1), he e is a boolean o mula
Bin s=O(1) boolean a iables z1, . . . , zs, and
he e a e spolynomials g1,...,gsin (2d+ 1) eal
a iables xP,xI, xǫ, such ha
δ(Q, I)≤ǫ⇐⇒
B(z1←[g1(xQ←Q, xI←I, xǫ←ǫ)≥0],
...
z ←[g (xQ←Q, xI←I, xǫ←ǫ)≥0]).
Fo j= 1,...,sand o all I∈ D, we compu e he
(d+ 1)- a ia e polynomials
gj,I(xQ, xǫ) := gj(xQ,xI←I, xǫ).
This is done by subs i u ing I o xIin gjand
he e o e akes ime O(1). The o al ime o com-
pu e all hese polynomials is O(n).
Fo he gj,I we compu e a subdi ision Ξ o Rd+1
wi h he p ope y ha he sign o each gj,I emains
cons an on each cell o he subdi ision. Such a
subdi sion o size O(n2d−3) can be compu ed in
O(n2d−3) ime, along wi h a poin -loca ion da a-
s uc u e L(Ξ) o he subdi ision wi h O(log n)
que y- ime, c. ., [8]; he compu a ion also yields o
each cell χ∈Ξ a poin (Qχ, ǫχ)∈χ.
In a nex s ep we p ocess each cell χ∈Ξ in
u n and compu e a se Dχ⊂ D, which is ini ially
emp y. Fo all I∈ D we do he ollowing: Fi s
compu e o j= 1,...,s he numbe s
γi,I,χ := gj,I(xQ←Qχ, xǫ←ǫχ).
Nex , we compu e he u h- alue
BI,χ := B(z1←[γ1,I,χ ≥0],...,zs←[γs,I,χ ≥0]).
I BI,χ is ue, we ha e ha δ(Qχ, I)≤ǫχand
we add I o Dχ. We augmen he da a-s uc u e
L(Ξ) by s o ing he se Dχ o each cell χ∈Ξ. The
o al ime needed o compu e i is O(n2d−2), and
i needs O(n2d−2) space.
To answe a que y (Q, ǫ)∈Ω×R, we p oceed as
ollows: Using L(Ξ) we loca e he cell χ∈Ξ wi h
(Q, ǫ)∈χin O(log n) ime. Since he sign o he
gj,I’s is cons an on each cell o Ξ, we ha e ha
δ(Qχ, I)≤ǫχi δ(Q, I)≤ǫ, so we can epo Dχ
as he answe o he que y. The o al ime equi ed
is O(log n+k), whe e k=|Dχ|is he size o he
answe .
Now we use a simple pa i ioning app oach o
yield he desi ed esul : We spli Din o g=
Θ(n/m) g oups D1,...,Dg, each o size Θ(m),
whe e 1 ≤m≤nis a sui able pa ame e (see
below). Then we build he a o emen ioned da a-
s uc u e o each Disepa a ely. To answe a que y
(Q, ǫ)∈Ω×R, we que y each da a-s uc u e
sepa a ely and combine he indi idual answe s.
The o al ime needed o compu e all he s uc-
u es is O(gm2d−2) = O(nm2d−3) ( his is also
he o al space equi emen ), and he que y ime
is O(glog n) = O((n/m) log n). Se ing m=
n1/(2d−3) p o es he claimed esul . ✷
3. Mo e semialgeb aic pa e n spaces
In he ollowing we show ha he no ion o a
semialgeb aic pa e n space cap u es many com-
bina ions o geome ic pa e ns (e.g., poin se s,
polygons, polygonal cu es) and geome ic dis-
ance measu es (e.g., Hausdo -dis ance, a ea o
o e lap, F ´eche -dis ance) oge he wi h hei quo-
ien s unde a ious ans o ma ion classes (e.g.,
ansla ions, igid mo ions).
Since he se accep ed by an algeb aic decision
ee is semialgeb aic we ge he ollowing
Lemma 2 Le Πbe a pa e n space. I FΠcan be
decided by an algo i hm in he algeb aic decision
ee model, hen Πis semialgeb aic.
I is s aigh o wa d o e i y ha many o he
algo i hms o deciding he mos p ominen dis-
ance measu es can be implemen ed in he alge-
b aic decision ee model, c. ., [1]. This shows o
example ha polygonal cu es on k e ices in Rd
20 h Eu opean Wo kshop on Compu a ional Geome y
w . he F ´eche -dis ance cons i u e a semialge-
b aic pa e n space.
Le Π = (Rd, δ) be a semialgeb aic pa e n
space, and le :Rd×Rd×R →Rd×Rdbe a unc-
ion. This unc ion induces a new dis ance mea-
su e and hus a new pa e n space Π := (Rd, δ )
as ollows:
δ (P, I) := min
∈R δ( (P, I, )).
We call δ he quo ien o δunde and he num-
be o deg ees o eedom o .
As an example conside again he pa e n space
o all poin se s in he plane wi h a mos poin s
each and he di ec ed Hausdo -dis ance h(,) as a
dis ance measu e. The unc ion (P, I, ) := (P+
, I) has wo deg ees o eedom and we ha e ha
h (P, I) = min ∈R2h(P+ , I) is he smalles di-
ec ed Hausdo dis ance ha a ansla e o Phas
o I.
Theo em 3 I is a ional, hen Π is semialge-
b aic. In ha case a semialgeb aic desc ip ion o
FΠ can e ec il ey be compu ed om such a de-
sc ip ion o FΠ.
PROOF. Fi s , obse e ha
δ (Q, I)≤ǫ⇐⇒ ∃ ∈R :δ( (Q, I, )) ≤ǫ.
Since Π = (Ω, δ) is a semialgeb aic pa e n space
and is a ional, he e is a boolean o mula B
in sboolean a iables z1,...,zs, and he e a e s
polynomials g1,...,gsin (2d+ 1) eal a iables
xP,xI, xǫ, such ha
δ (Q, I)≤ǫ⇐⇒
∃ B(z1←[g1( (xQ←Q, xI←I, x ← ),
xǫ←ǫ)≥0],
...
zs←[gs( (xQ←Q, xI←I, x ← ),
xǫ←ǫ)≥0]
(x is a sequence o new a iables).
In gene al gi( (),) is no a polynomial. Howe e ,
since is a ional, he condi ions ’gi( (),)≥0’ can
be ew i en as equi alen polynomial inequali ies.
This shows ha FΠ is a Ta ski-se , and he e o e
semialgeb aic. Using s anda d quan i ie elimina-
ion echniques [4], a semialgeb aic desc ip ion o
FΠ can e ec il ey be compu ed. ✷
I he dimension do Π is O(1) ( ela i e o n=
|D|), hen he dimension d′o Π is also O(1) (un-
o una ely, in gene al, d′is doubly exponen ial in
d) and a semialgeb aic desc ip ion o FΠ can be
compu ed in O(1) ime.
This shows o example ha polygonal cu es on
k e ices in Rdw . he smalles F ´eche -dis ance
ha can be a ained unde igid mo ions cons i u e
a semialgeb aic pa e n space o dimension O(1) i
k, d =O(1).
Acknowledgmen s. The au ho would like o
hank Pe e B aß o ui ul discussion on he sub-
jec .
Re e ences
[1] H. Al and L. J. Guibas. Disc e e geome ic
shapes: Ma ching, in e pola ion, and app oxima ion.
In J.-R. Sack and J. U u ia, edi o s, Handbook o
Compu a ional Geome y, pages 121–153. Else ie
Science Publishe s B.V. No h-Holland, Ams e dam,
2000.
[2] S. B in. Nea neighbo sea ch in la ge me ic spaces.
In The VLDB Jou nal, pages 574–584, 1995.
[3] K. L. Cla kson. Nea es neighbo que ies in me ic
spaces. In P oc. 29 h Annu. ACM Sympos. Theo y
Compu ., pages 609–617, 1997.
[4] G. E. Collins. Quan i ie elimina ion o eal closed
ields by cylind ical algeb aic decomposi ion. In P oc.
2nd GI Con e ence on Au oma a Theo y and Fo mal
Languages, olume 33 o Lec u e No es Compu . Sci.,
pages 134–183. Sp inge -Ve lag, 1975.
[5] E.Ch´a ez, G. Na a o, R.Baeza-
Ya es, and J.Ma oqu´ın. Sea ching in me ic spaces.
Technical Repo TR/DCC-99-3, Dep . o Compu e
Science, Uni . o Chile, 1999.
[6] P. Indyk. App oxima e nea es neighbo algo i hms o
eche dis ance ia p oduc me ics. In P oceedings
o he eigh een h annual symposium on Compu a ional
geome y, pages 102–106. ACM P ess, 2002.
[7] P. Indyk and M. Fa ach-Col on. App oxima e
nea es neighbo algo i hms o Hausdo me ics ia
embeddings. In P oc. 40 h Annu. IEEE Sympos.
Found. Compu . Sci., pages 171–180, 1999.
[8] V. Kol un. Almos igh uppe bounds o e ical
decomposi ions in ou dimensions. In P oc. 42nd
Annu. IEEE Sympos. Found. Compu . Sci., 2001.
[9] S. A. Nene and S. K. Naya . A simple algo i hm
o nea es neighbo sea ch in high dimensions.
IEEE T ansac ions on Pa e n Analysis and Machine
In elligence, 19:989–1003, 1997.
[10] P. N. Yianilos. Excluded middle an age poin o es s
o nea es neighbo sea ch. Technical epo , NEC
Resea ch Ins i u e, 1999.