Geome i da a s u u es o mul ihie a hial XML agging o
manus ip s
Je zy W. Ja omzyk
a
;
1
,Neil Mo o e
a
;
1
,
a
Depa men o Compu e Siene, Uni e si y o Ken uky, Lexing on, KY, USA
Abs a
This pap e shows an applia ion o ompu a ional geome y me hods o he p epa a ion o image-based digi al
lib a y edi ions. We p esen a o malism o des ibing non-hie a ahial ma kup o manus ip s in e ms o one-
and wo-dimensional geome y. This o malism allows us o use geome i da a s u u es and algo i hms o p o ess
ma ked-up do umen s. Wi h his app oah we an o e ome many well-known and inhe en ly diÆul p oblems
wi h non-hie a hial ma kup. We p esen algo i hms based on segmen ees and ange-que y s u u es o
p e o ming a numbe o que ies on ma kup s u u e. This applia ion o ompu a ional geome y da a s u u es
o a new domain also p o ides insigh s in o no el ypes o geome i op e a ions and que ies. Some o hese
ehniques a e u en ly being used by esea he s in he Resea h Compu ing o Humani ies p o je , whih aims
o p o due ele oni edi ions o sele ed manus ip s om he B i ish Lib a y.
1. In o du ion
F om a ompu a ional geome y p oin o iew,
an old manus ip , a
olio
(a shee o w i ing ma e-
ial) and he s ip (a ex on he manus ip page)
ha e in e es ing ea u es in one, wo and h ee di-
mensions and all o hem a e imp o an . Spa ial
de o ma ions o he olio an be s udied o es o a-
ion pu p oses in h ee dimensions. Illumina ions,
damages, es o a ions, and paleog aphi ea u es
o indi idual le e s an b e s udied as wo dimen-
sional ob je s. The s ip , a sequene o lines o
ex , an b e iewed as one dimensional as i ollows
isible o in isible ulings ha guide he layou o
he ex [B94℄. In a , onne ing he image iew
o a manus ip wi h i s ans ip is ypially he
 s ask. In his pap e we will disuss his linea
asp e o olia and we will disuss geome i s u-
u es ha supp o i s agging.
Ex ensi e agging o ma kup is an o en ex ui-
a ing ask in he p epa a ion o ele oni edi ions
o manus ip s. The agging p o ess esul s in a
s u u ed des ip ion o he doumen 's on en s,
i s ea u es and a ibu es in a o m ha an b e
Email add esses:
ju eks.uky.edu
(Je zy W.
Ja omzyk),
neils.uky.edu
(Neil Mo o e).
1
This esea h was suppo ed in pa by NSF ITR g an
0219924
used o iew and ee i ely que y he edi ion. The
XML (eX ensible Ma kup Language) is a p e ail-
ing o ma used o des ibing li e a y and a is i
wo k o Digi al Lib a ies. XML les des ib e well-
hie a hial s u u es (e.g., bo ok, olume, se ion,
page, line, wo d and ha a e ) o he do umen
and o ha eason hey an be iewed as oo ed
ees. Al hough i seems na u al ha mos dou-
men s adhe e o suh hie a hies, i is o en no ue
in p a ie. E en wo se, his happ ens in he on ex
o ul u al he i age ha u gen ly equi es p ese -
a ion: old and se e ely damaged manus ip s. An
image o a damaged olio om Al ed he G ea 's
Old English ansla ion o Bo e hius's
Consola ion
o Philosophy
is demons a ed in Figu e 1.
Wo ds an span mo e han one line, damages o
es o a ions an o e lap wo ds and pa s o hem.
A a he simple ase is illus a ed in Figu e 2 whe e
in he on olu ed agging one wo d spans wo lines;
as suh, i is no well- o med XML.
I has been long eognized ha , in spi e o i s
p opula i y, XML sue s om an inabili y o en-
o de elemen s ha a e no in hie a hial ela ion-
ships [RMD93℄. The e a e nume ous app oahes
o add ess his p oblem alled he
onu en hi-
e a hies
p oblem; see, o example, [B95℄. Mos ly
hese app oahes a e one ned wi h agging an-
20 h EWCG Se ille, Spain (2004)
20 h Eu op ean Wo kshop on Compu a ional Geome y
Fig. 1. An image o a damaged manus ip page
Fig. 2. Ma kup ha is no hie a hial
s ip s ( ex -based do umen s). In ou ask a
manus ip o an image o i is he p ima y sou e
o p epa ing an ele oni edi ion and we need
o handle he onu en hie a hies in geome i
on ex o he image. This image-based app oah
is he mos dis inguishing aspe o ou wo k.
A geome i iew o he p oblem allows us o
engage many da a s u u es, in pa iula mul i-
dimensional ones. In his pape , we will o us on
wo o hem: segmen ees and a g id based da a
s u u e de elop ed by O e ma s o ange que ies
(we will use i o line segmen s a he han p oin s,
hough). We will analyze how hese s u u es sup-
p o a a ie y o que ies ha a e essen ial in he
on ex o edi ing and s udying manus ip s.
The e a e se e al on ibu ions o his pap e .
The  s is in applying ompu a ional geome y o
a new a ea. We will p esen a o malism o onu -
en hie a hies ha allows us o onne geome -
i s u u es wi h XML do umen s. Sp eially,
we will disuss a numb e o algo i hms o que ying
he s u u e o a do umen , oge he wi h hei
asymp o i omplexi ies.
2. Deni ions
In his se ion we des ib e a o malism o ep e-
sen ing mul ihie a hial doumen ma kup. This
o malism allows us o onne he s u u e o
ma kup wi h a geome i ep esen a ion; his al-
lows us o use geome i da a s u u es and algo-
i hms o p o ess agged do umen s.
2.1.
Ma kup elemen s
We ep esen a ma kup elemen as a uple
(
N ; A; ; !
) whe e
N
is he elemen name,
A
(a
map om s ings o s ings) he a ibu es, and

and
!
a e in ege s wi h 1



!
. The in e al
o a ma kup elemen
e
, w i en I(
e
), is he losed
in e al [

(
e
)
; !
(
e
)℄

N
.
De ini ion
2.1
Le
e
1
and
e
2
be wo ma kup ele-
men s. We dene he ela ions:
{
e
1

e
2
i
!
(
e
1
)
< 
(
e
2
)
{
e
1

e
2
i

(
e
1
)


(
e
2
)
and
!
(
e
1
)

!
(
e
2
)
and
I(
e
1
)
6
= I(
e
2
)
. In his ase we say ha
e
1
is
a desendan o
e
2
, o equi alen ly ha
e
2
is an
anes o o
e
1
.
We s a e wi hou p o o he ollowing heo ems:
Theo em
2.1
The ela ions

and

eah o m a
s i pa ial o de .
Theo em
2.2
Le
e
1
and
e
2
be wo ma kup ele-
men s. Exa ly one o he ol lowing holds:
e
1

e
2
;
e
2

e
1
;
e
1

e
2
;
e
2

e
1
;
e
1
o e laps
e
2
; o
I(
e
1
) =
I(
e
2
)
.
3. Hie a hies
De ini ion
3.1
Le
E
be a ni e se o ma kup
elemen s.
E
is hie a hial i :
{ The e is an elemen
2
E
, al led he oo , suh
ha , o eah elemen
e
2
E
,
e

o
e
=
{ No wo elemen s o
E
o e lap, and no dis in
elemen s o
E
sha e he same in e al.
Lemma
3.1
Le
E
be a hie a hial se o ma kup
elemen s, and
e
2
E
. Then ei he
e
is he oo and
has no pa en s in
E
, o
e
is no he oo and has
exa ly one pa en in
E
.
Ma h 25-26, 2004 Se ille (Spain)
Theo em
3.1
Le
E
be a hie a hial se o
ma kup elemen s. Le
G
be a g aph on
E
suh ha
he edge
(
e
1
; e
2
)
is in
G
i
e
1
is he pa en o
e
2
.
G
is a ee.
This jus ies ou use o he e m hie a hy".
Beause hild en o he same pa en anno be de-
sendan s o one ano he , by Theo em 2.2 hey an
b e o de ed by

. The ee is he e o e an o de ed
ee.
4. Da a s u u es and que ies
In his se ion we des ib e wo geome i da a
s u u es and apply hem o a numbe o ommon
que ies on do umen s.
A segmen ee [BW80, PS85℄ is a dynami da a
s u u e o ep esen a se o segmen s. Fo inse -
ions and dele ions i is assumed ha he endp oin s
b elong o he se o
n
p oin s known in ad ane.
The unde lying s u u e is a balaned bina y
ee wi h lea es ep esen ing a omi segmen s.
Eah node o esp onds o he union o he a omi
segmen s o o ed in his no des. In e als ha b e-
long o he olle ion ep esen ed in he segmen
ee a e assoia ed wi h no des o he ee and sa -
is y he ollowing p op e y: a no de
s o es
s
i he
union o i s a omi segmen s is on ained in
s
bu
he union o he a omi segmen s assoia ed wi h
he pa en o
do no . Thanks o his p op e y
eah segmen is ep esen ed in a mos
O
(log
n
)
no des.
Inse ions and dele ions an b e p e o med in
O
(log
n
) ime. Also, in he same ime one an oun
he numbe o segmen s in he olle ion ha in-
ludes a gi en que y poin .
While segmen ees a e well-sui ed o some
yp es o que ies, he e a e o he que ies whih seg-
men ees do no p e o m as eÆien ly. We use a
ange- que y s u u e o supp o hese que ies.
We ea a segmen
S
= [
; !
℄ in
U
= [1
; M
℄ as
a poin
p
(
S
)=(
; !
) in
U
2
. We all his ep esen-
a ion o (a olle ion o ) segmen s a
segmen g id
.
Many p op e ies o
S
hen o esp ond o ange
p op e ies o
p
(
S
) in he segmen g id. Fo exam-
ple,
S

T
i and only i
p
(
S
) lies o he lowe igh
o
p
(
T
).
We shall make use o gene al ange que ies o he
o m: nd all poin s lying in he (losed) e angle
b ounded by (
a; b
) and (
; d
). The e exis a numbe
o da a s u u es supp o ing suh que ies in a wo-
dimensional g id. A numbe o hese s u u es a e
des ib ed in [O88℄; wo a e o pa iula in e es
o ou pu p oses.
Theo em
4.1
(O e ma s) We an ep esen
n
poin s in
U
2
(and hus
n
segmen s in
U
) using
O
(
n
log
n
)
spae in suh a way ha ange que ies
ake
O
(
k
+ log log
j
U
j
)
ime, whe e
k
is he numbe
o esul s e u ned by he que y.
This da a s u u e makes use o p e e hash-
ing, and is he e o e slow o build. The e is an al-
e na i e da a s u u e wi h sligh ly wo se que y
ime, bu signian ly be e  ea ion ime:
Theo em
4.2
(O e ma s) We an ep esen
n
poin s in
U
2
using
O
(
n
log
n
)
spae in suh a way
ha ange que ies ake
O

k
+
p
log
j
U
j

ime,
whe e
k
is he numbe o e u ned esul s. This
da a s u u e an be buil in
O
(
n
log
n
)
ime.
Nei he o he ange-que y da a s u u es pe -
mi s eÆien inse ion o dele ion. Fo mo e in o -
ma ion on hese s u u es, see [O88℄.
4.1.
Desendan que ies
A ommon que y on do umen s is o nd all el-
emen s o a e ain yp e ha a e desendan s o a
gi en elemen
e
. Fo example, gi en a
<page>
ele-
men , one may wish o nd all
<damage>
elemen s
on ained wi hin ha elemen , ei he di e ly (as
hild en) o indi e ly. We an p e o m his op e -
a ion by nding all desendan s o
e
and epo ing
only hose o he eques ed yp e.
Reall om Deni ion 2.1 ha he desendan s
o
e
a e hose elemen s whih b egin no ea lie han
e
, end no la e han
e
, and do no b o h b egin and
end a he same p oin as
e
. In e ms o he segmen
g id,
p
(I(
x
)) is a desendan o
e
i I(
x
)
6
= I(
e
)
and
p
(I(
x
)) lies in he e angle b ounded by he
p oin s (

(
e
)
; 
(
e
)) and (
!
(
e
)
; !
(
e
)). Using he da a
s u u e om Theo em 4.2, we an nd all suh
p oin s in
O
(
k
+
p
log
M
) ime, whe e
M
is he
do umen 's maximum ose and
k
is he numbe
o esul s.
4.2.
O e lap que ies
Ano he use ul que y is: gi en an elemen
e
, nd
all elemen s whih o e lap
e
. I
e
1
o e laps
e
2
,
e
1
on ains a leas one o he endp oin s o
e
2
. Con-
e sely, i
e
1
on ains a leas one endp oin o
e
2
,
ei he
e
1
o e laps
e
2
,
e
1
=
e
2
,
e
1

e
2
, o
e
2

e
1
.
This sugges s he ollowing:
Theo em
4.3
Le
D
be a doumen on aining he
elemen
e
. Le
k
be he numbe o elemen s o e -
lapping
e
,
d
he numbe o desendan s o
e
,
a
he
numbe o anes o s o
e
, and
M
he maximum o-
20 h Eu op ean Wo kshop on Compu a ional Geome y
se o
D
. We an nd al l elemen s o e lapping
e
in
O
(
k
+
d
+
a
+ log
M
)
ime.
We  s nd he se s
B
(
e
) and
E
(
e
) o all ele-
men s whose in e als on ain

(
e
) and
!
(
e
), e-
sp e i ely, using s abbing que ies in a segmen ee.
B
(
e
) on ains a mos
k
+
d
+
a
+ 1 elemen s, and
likewise o
E
(
e
). The s abbing que ies an he e-
o e b e p e o med in ime
O
(
k
+
d
+
a
+ log
M
). We
hen i e a e h ough he esul s, ep o ing hose
whih a ually o e lap
e
. Tes ing whe he a gi en
segmen s o e laps
e
equi es ons an ime, so his
s ep do es no in ease he omplexi y.

We an imp o e on his b ound somewha by
making use o ange que ies. I
e
1
o e laps
e
2
,
e
1
on ains
exa ly
one endp oin o
e
2
. In he seg-
men g id, segmen s on aining

(
e
) bu no
!
(
e
)
lie in he e angle
R

b ounded by he p oin s
(1
; 
(
e
)) and (

(
e
)
; !
(
e
)). Likewise, segmen s on-
aining
!
(
e
) bu no

(
e
) lie in he e angle
R
!
b ounded by (

(
e
)
; !
(
e
)) and (
!
(
e
)
; M
), whe e
M
is he maximum ose o he doumen . While
hese e angles on ain all he elemen s whih
o e lap
e
, hey do no on ain
only
suh elemen s.
As wi h he s abbing que ies des ibed ab o e, he
ange que ies also e u n
e
, and may e u n some
anes o s and desendan s o
e
, so we mus emo e
hese om he esul se . I is lea , howe e , ha
he e angles do no on ain any elemen
x
suh
ha
x

e
o
e

x
.
Theo em
4.4
Le
D
be a doumen on aining he
elemen
e
. Le
k
be he numbe o elemen s o e -
lapping
e
,
d
he numbe o desendan s o
e
,
a
he
numbe o anes o s o
e
, and
M
he maximum o-
se o
D
. We an nd al l elemen s o e lapping
e
in
O
(
k
+
d
+
a
+
p
log
M
)
ime.
Eah ange que y e u ns a mos
k
+
d
+
a
+ 1
elemen s, and an he e o e b e p e o med in ime
O
(
k
+
d
+
a
+
p
log
M
). As wi h he s abbing que y,
we hen i e a e h ough he esul s o he ange
que y, ep o ing hose elemen s whih o e lap
e
;
again, his do es no ae he o e all omplexi y
o he o e lap que y.

The unning ime o o e lap que ies an be im-
p o ed s ill u he i we impose addi ional es i-
ions on he endpoin s o elemen s:
Theo em
4.5
Le
D
be a doumen suh ha no
wo elemen s sha e an endpoin in ommon, and le
e
be an elemen in
D
. I
k
is he numbe o elemen s
o e lapping
e
and
M
is he maximum ose o
D
,
we an nd al l elemen s o e lapping
e
in
O
(
k
+
p
log
M
)
ime.
5. Conlusion
We ha e p esen ed a o malism ha onne s
he ealm o ompu a ional geome y o algo i h-
mi p oblems ha we ha e aed in he ma king
up o image-based ele oni edi ions. As exam-
ples o geome i s u u es we ha e disussed seg-
men ees and ange que y s u u es and ha e
applied hem o he well- eognized and inhe en ly
diÆul p oblem o non-hie a hial ma kup. Two-
dimensional asp e s o manus ip ma king, suh
as ma ginalia, paleog aphi ea u es and damages
will in ol e addi ional geome i s u u es.
Aknowledgemen
The au ho s aknowledge a pa ial supp o om he
NSF ARCHway: A hi e u e o Resea h in Compu ing
o Humani ies h ough Resea h, Teahing and Lea ning
p o je . We a e hank ul o Ke in Kie nan, he Bo e hius
P o je and he B i ish Lib a y Boa d o allowing us o
use he image. We also hank ou olleagues om he Re-
sea h Compu ing o Humani ies Lab a he Uni e si y o
Ken uky o many use ul disussions.
Bibliog aphy
[B95℄ Ba na d, D., e al. Hie a hial Eno ding o Tex :
Tehnial p oblem and SGML Solu ions,
Compu e s and
he Humani ies
29/3 (1995) 211-231.
[BW80℄ Ben ley, J. L., and D. Wo o d. An op imal wo s -ase
algo i hm o epo ing in e se ions o e angles,
IEEE
T ans. on Compu e s
C-29 (1980) 571-577.
[B94℄ B own, M. P.
Unde s anding Il lumina ed Manus ip s:
a Guide o Tehnial Te ms
. London: The B i ish Lib a y,
1994.
[KJDP03℄ Kie nan, K., J. W. Ja omzyk, A. Dekh ya , D.
C. Po e , e al. The ARCHway P o je : A hi e u e o
Resea h in Compu ing o Humani ies h ough Resea h,
Teahing, and Lea ning. To b e published in
Li e a y and
Linguis i Compu ing
, 2003.
[O87℄ O e ma s, Ma k H. EÆien da a s u u es o ange
sea hing on a g id,
J. Algo i hms
9 (1988) 254-275.
[PS85℄ P epa a a, F. P. and M. I. Shamos.
Compu a ional
Geome y: an In odu ion
. New Yo k: Sp inge -Ve lag,
1985.
[RMD93℄ Renea , A., E. Mylonas, and D. Du and. Rening
ou No ion o Wha Tex Really Is: The P oblem o O e -
lapping Hie a hies. In
Resea h in Humani ies Compu -
ing
, eds. N. Ide and S. Ho key. Ox o d: Ox o d Uni e is y
P ess, 1993.
[S99℄ Same , H.. Mul idimensional Da a S u u es. In
Al-
go i hms and Theo y o Compu a ion Handbook
, ed. M. J.
A allah. Bo a Ra on: CRC P ess, 1999.
[XML-W3C℄ B ay, T., J. Paoli, C. M. Sp e b e g-MQueen,
and E. Male , eds. Ex ensible Ma kup Language (XML)
1.0, W3C Reommenda ion.
h p://www.w3.o g/TR/2000 /
REC-xml-20001006
. W3 Conso ium, 2000.