%!PS-Adobe-2.0 %%Creator: dvipsk 5.58f Copyright 1986, 1994 Radical Eye Software %%Title: linkages.dvi %%Pages: 18 %%PageOrder: Ascend %%BoundingBox: 0 0 612 792 %%DocumentPaperSizes: Letter %%EndComments %DVIPSCommandLine: dvips linkages %DVIPSParameters: dpi=600, comments removed %DVIPSSource: TeX output 1999.03.19:1423 %%BeginProcSet: tex.pro /TeXDict 250 dict def TeXDict begin /N{def}def /B{bind def}N /S{exch}N /X{S N}B /TR{translate}N /isls false N /vsize 11 72 mul N /hsize 8.5 72 mul N /landplus90{false}def /@rigin{isls{[0 landplus90{1 -1}{-1 1} ifelse 0 0 0]concat}if 72 Resolution div 72 VResolution div neg scale isls{landplus90{VResolution 72 div vsize mul 0 exch}{Resolution -72 div hsize mul 0}ifelse TR}if Resolution VResolution vsize -72 div 1 add mul TR[matrix currentmatrix{dup dup round sub abs 0.00001 lt{round}if} forall round exch round exch]setmatrix}N /@landscape{/isls true N}B /@manualfeed{statusdict /manualfeed true put}B /@copies{/#copies X}B /FMat[1 0 0 -1 0 0]N /FBB[0 0 0 0]N /nn 0 N /IE 0 N /ctr 0 N /df-tail{ /nn 8 dict N nn begin /FontType 3 N /FontMatrix fntrx N /FontBBox FBB N string /base X array /BitMaps X /BuildChar{CharBuilder}N /Encoding IE N end dup{/foo setfont}2 array copy cvx N load 0 nn put /ctr 0 N[}B /df{ /sf 1 N /fntrx FMat N df-tail}B /dfs{div /sf X /fntrx[sf 0 0 sf neg 0 0] N df-tail}B /E{pop nn dup definefont setfont}B /ch-width{ch-data dup length 5 sub get}B /ch-height{ch-data dup length 4 sub get}B /ch-xoff{ 128 ch-data dup length 3 sub get sub}B /ch-yoff{ch-data dup length 2 sub get 127 sub}B /ch-dx{ch-data dup length 1 sub get}B /ch-image{ch-data dup type /stringtype ne{ctr get /ctr ctr 1 add N}if}B /id 0 N /rw 0 N /rc 0 N /gp 0 N /cp 0 N /G 0 N /sf 0 N /CharBuilder{save 3 1 roll S dup /base get 2 index get S /BitMaps get S get /ch-data X pop /ctr 0 N ch-dx 0 ch-xoff ch-yoff ch-height sub ch-xoff ch-width add ch-yoff setcachedevice ch-width ch-height true[1 0 0 -1 -.1 ch-xoff sub ch-yoff .1 sub]{ch-image}imagemask restore}B /D{/cc X dup type /stringtype ne{]} if nn /base get cc ctr put nn /BitMaps get S ctr S sf 1 ne{dup dup length 1 sub dup 2 index S get sf div put}if put /ctr ctr 1 add N}B /I{ cc 1 add D}B /bop{userdict /bop-hook known{bop-hook}if /SI save N @rigin 0 0 moveto /V matrix currentmatrix dup 1 get dup mul exch 0 get dup mul add .99 lt{/QV}{/RV}ifelse load def pop pop}N /eop{SI restore userdict /eop-hook known{eop-hook}if showpage}N /@start{userdict /start-hook known{start-hook}if pop /VResolution X /Resolution X 1000 div /DVImag X /IE 256 array N 0 1 255{IE S 1 string dup 0 3 index put cvn put}for 65781.76 div /vsize X 65781.76 div /hsize X}N /p{show}N /RMat[1 0 0 -1 0 0]N /BDot 260 string N /rulex 0 N /ruley 0 N /v{/ruley X /rulex X V}B /V {}B /RV statusdict begin /product where{pop product dup length 7 ge{0 7 getinterval dup(Display)eq exch 0 4 getinterval(NeXT)eq or}{pop false} ifelse}{false}ifelse end{{gsave TR -.1 .1 TR 1 1 scale rulex ruley false RMat{BDot}imagemask grestore}}{{gsave TR -.1 .1 TR rulex ruley scale 1 1 false RMat{BDot}imagemask grestore}}ifelse B /QV{gsave newpath transform round exch round exch itransform moveto rulex 0 rlineto 0 ruley neg rlineto rulex neg 0 rlineto fill grestore}B /a{moveto}B /delta 0 N /tail {dup /delta X 0 rmoveto}B /M{S p delta add tail}B /b{S p tail}B /c{-4 M} B /d{-3 M}B /e{-2 M}B /f{-1 M}B /g{0 M}B /h{1 M}B /i{2 M}B /j{3 M}B /k{ 4 M}B /w{0 rmoveto}B /l{p -4 w}B /m{p -3 w}B /n{p -2 w}B /o{p -1 w}B /q{ p 1 w}B /r{p 2 w}B /s{p 3 w}B /t{p 4 w}B /x{0 S rmoveto}B /y{3 2 roll p a}B /bos{/SS save N}B /eos{SS restore}B end %%EndProcSet %%BeginProcSet: special.pro TeXDict begin /SDict 200 dict N SDict begin /@SpecialDefaults{/hs 612 N /vs 792 N /ho 0 N /vo 0 N /hsc 1 N /vsc 1 N /ang 0 N /CLIP 0 N /rwiSeen false N /rhiSeen false N /letter{}N /note{}N /a4{}N /legal{}N}B /@scaleunit 100 N /@hscale{@scaleunit div /hsc X}B /@vscale{@scaleunit div /vsc X}B /@hsize{/hs X /CLIP 1 N}B /@vsize{/vs X /CLIP 1 N}B /@clip{ /CLIP 2 N}B /@hoffset{/ho X}B /@voffset{/vo X}B /@angle{/ang X}B /@rwi{ 10 div /rwi X /rwiSeen true N}B /@rhi{10 div /rhi X /rhiSeen true N}B /@llx{/llx X}B /@lly{/lly X}B /@urx{/urx X}B /@ury{/ury X}B /magscale true def end /@MacSetUp{userdict /md known{userdict /md get type /dicttype eq{userdict begin md length 10 add md maxlength ge{/md md dup length 20 add dict copy def}if end md begin /letter{}N /note{}N /legal{} N /od{txpose 1 0 mtx defaultmatrix dtransform S atan/pa X newpath clippath mark{transform{itransform moveto}}{transform{itransform lineto} }{6 -2 roll transform 6 -2 roll transform 6 -2 roll transform{ itransform 6 2 roll itransform 6 2 roll itransform 6 2 roll curveto}}{{ closepath}}pathforall newpath counttomark array astore /gc xdf pop ct 39 0 put 10 fz 0 fs 2 F/|______Courier fnt invertflag{PaintBlack}if}N /txpose{pxs pys scale ppr aload pop por{noflips{pop S neg S TR pop 1 -1 scale}if xflip yflip and{pop S neg S TR 180 rotate 1 -1 scale ppr 3 get ppr 1 get neg sub neg ppr 2 get ppr 0 get neg sub neg TR}if xflip yflip not and{pop S neg S TR pop 180 rotate ppr 3 get ppr 1 get neg sub neg 0 TR}if yflip xflip not and{ppr 1 get neg ppr 0 get neg TR}if}{noflips{TR pop pop 270 rotate 1 -1 scale}if xflip yflip and{TR pop pop 90 rotate 1 -1 scale ppr 3 get ppr 1 get neg sub neg ppr 2 get ppr 0 get neg sub neg TR}if xflip yflip not and{TR pop pop 90 rotate ppr 3 get ppr 1 get neg sub neg 0 TR}if yflip xflip not and{TR pop pop 270 rotate ppr 2 get ppr 0 get neg sub neg 0 S TR}if}ifelse scaleby96{ppr aload pop 4 -1 roll add 2 div 3 1 roll add 2 div 2 copy TR .96 dup scale neg S neg S TR}if}N /cp {pop pop showpage pm restore}N end}if}if}N /normalscale{Resolution 72 div VResolution 72 div neg scale magscale{DVImag dup scale}if 0 setgray} N /psfts{S 65781.76 div N}N /startTexFig{/psf$SavedState save N userdict maxlength dict begin /magscale true def normalscale currentpoint TR /psf$ury psfts /psf$urx psfts /psf$lly psfts /psf$llx psfts /psf$y psfts /psf$x psfts currentpoint /psf$cy X /psf$cx X /psf$sx psf$x psf$urx psf$llx sub div N /psf$sy psf$y psf$ury psf$lly sub div N psf$sx psf$sy scale psf$cx psf$sx div psf$llx sub psf$cy psf$sy div psf$ury sub TR /showpage{}N /erasepage{}N /copypage{}N /p 3 def @MacSetUp}N /doclip{ psf$llx psf$lly psf$urx psf$ury currentpoint 6 2 roll newpath 4 copy 4 2 roll moveto 6 -1 roll S lineto S lineto S lineto closepath clip newpath moveto}N /endTexFig{end psf$SavedState restore}N /@beginspecial{SDict begin /SpecialSave save N gsave normalscale currentpoint TR @SpecialDefaults count /ocount X /dcount countdictstack N}N /@setspecial {CLIP 1 eq{newpath 0 0 moveto hs 0 rlineto 0 vs rlineto hs neg 0 rlineto closepath clip}if ho vo TR hsc vsc scale ang rotate rwiSeen{rwi urx llx sub div rhiSeen{rhi ury lly sub div}{dup}ifelse scale llx neg lly neg TR }{rhiSeen{rhi ury lly sub div dup scale llx neg lly neg TR}if}ifelse CLIP 2 eq{newpath llx lly moveto urx lly lineto urx ury lineto llx ury lineto closepath clip}if /showpage{}N /erasepage{}N /copypage{}N newpath }N /@endspecial{count ocount sub{pop}repeat countdictstack dcount sub{ end}repeat grestore SpecialSave restore end}N /@defspecial{SDict begin} N /@fedspecial{end}B /li{lineto}B /rl{rlineto}B /rc{rcurveto}B /np{ /SaveX currentpoint /SaveY X N 1 setlinecap newpath}N /st{stroke SaveX SaveY moveto}N /fil{fill SaveX SaveY moveto}N /ellipse{/endangle X /startangle X /yrad X /xrad X /savematrix matrix currentmatrix N TR xrad yrad scale 0 0 1 startangle endangle arc savematrix setmatrix}N end %%EndProcSet TeXDict begin 40258431 52099146 1000 600 600 (linkages.dvi) @start /Fa 47 122 df40 DI44 DII49 D52 DI55 DII65 D67 DI70 D III77 DI80 D82 DII97 DIIIII III108 DIIIIIIIIIIIII E /Fb 1 16 df15 D E /Fc 7 63 df 16 DI40 D56 D58 D60 D62 D E /Fd 5 112 df49 DI103 D108 D111 D E /Fe 5 115 df105 DII110 D114 D E /Ff 1 51 df50 D E /Fg 59 123 df11 DI39 DII 44 DII48 DIIIIIII57 DI61 D65 DIIIIIIII76 D83 DI87 D91 D93 D97 DIIIIIIII107 DII III IIIIIIIIII E /Fh 40 122 df46 D48 DIIIIIIIIII65 D67 D73 D76 D78 DII84 D97 D99 DIIIIII107 DIIIII114 DIII119 D121 D E /Fi 24 121 df11 D15 D21 D58 D I61 D97 DIIII104 DI IIIII113 DIII118 D120 D E /Fj 17 112 df1 D40 DI43 D48 DIIIIII61 D100 D103 D108 DI111 D E /Fk 26 121 df0 D2 D6 D15 D17 D20 D24 D50 D54 D57 D65 DII70 D76 D78 D80 D83 DI94 DI102 DI106 D112 D120 D E /Fl 45 122 df15 D21 D39 D58 DIIII65 D67 D71 DI75 DIIIIIII84 D90 D97 DIIII104 DIIIIIIIIIIIIIIIII E /Fm 31 124 df 45 DI48 D50 DIIIII57 D65 D67 DI70 D78 D82 DI97 DI100 DI103 D110 DII114 DIII121 D123 D E /Fn 3 122 df0 D3 D121 D E /Fo 80 125 df1 D5 DI11 DI14 D34 D39 DII43 DIII48 DIIIIIIIIIII61 D63 D65 DIIIIIIIII76 DIIII82 DIIIII91 DII 97 DIIIIIIIIIIIIIIIIIIIIIII IIII E /Fp 34 121 df49 DIII63 D65 D69 DI73 D 76 DI82 D87 D97 DIIIIIIII 107 DIIIII114 DIII119 DI E /Fq 2 81 df78 D80 D E /Fr 1 16 df15 D E /Fs 45 122 df12 D34 D40 DI44 DII48 D58 D61 D63 D65 D67 D69 D71 DII84 D87 D92 D97 DIIIIIIIIIIIIIIIIIIIIIIII E /Ft 7 117 df65 D97 DII114 DII E /Fu 7 122 df0 D3 D14 D17 D48 D112 D121 D E /Fv 45 122 df44 DII48 DIIII56 DI64 DIIII73 D 76 DIIII82 DI85 D97 DIIIII III108 DIIII114 DIIII120 DI E /Fw 17 117 df69 D73 D76 D97 DIIII103 D105 D107 D109 DII114 DII E end %%EndProlog %%BeginSetup %%Feature: *Resolution 600dpi TeXDict begin %%PaperSize: Letter %%EndSetup %%Page: 1 1 1 0 bop 719 987 a Fw(Em)l(b)t(edding)46 b(Link)-7 b(ages)42 b(on)h(an)h(In)l(teger)g(Lattice)943 1240 y Fv(Susan)33 b(Landau)1546 1204 y Fu(\003)874 1399 y Fv(MS)h(UBUR02-313)575 1515 y(Sun)f(Microsystems)g(Lab)s(oratories)937 1631 y(P)-8 b(.O.)33 b(Bo)m(x)g(4002)665 1748 y(Burlington)e(MA)i (01803-0902)661 1864 y(susan.landau@east.sun.com)2384 1240 y(Neil)e(Immerman)3052 1204 y Fu(y)2198 1399 y Fv(Computer)i (Science)g(Dept.)2124 1515 y(Univ)m(ersit)m(y)g(of)f(Massac)m(h)m (usetts)2285 1631 y(Amherst,)h(MA)g(01003)2177 1748 y (immerman@cs.umass.edu)1760 2289 y Ft(Abstract)800 2435 y Fs(This)28 b(pap)r(er)g(answ)n(ers)e(the)j(follo)n(wing)e(question:) 37 b(Giv)n(en)28 b(an)g(\\erector)e(set")676 2534 y(link)-5 b(age,)36 b(a)f(connected)g(set)g(of)g(\014xed-length)g(links,)i(what)e (is)g(the)h(minimal)f Fr(\017)676 2634 y Fs(needed)e(to)h(adjust)g(the) f(edge)h(lengths)f(so)g(that)h(the)g(v)n(ertices)e(of)i(the)f(link)-5 b(age)676 2734 y(can)32 b(b)r(e)h(placed)g(on)g(in)n(teger)f(lattice)h (p)r(oin)n(ts?)52 b(Eac)n(h)32 b(edge)h(length)g(is)f(allo)n(w)n(ed)676 2833 y(to)26 b(c)n(hange)g(b)n(y)h(at)g(most)f Fr(\017)p Fs(.)37 b(Angles)26 b(are)g(not)h(\014xed,)g(but)h(collinearit)n(y)d(m) n(ust)j(b)r(e)676 2933 y(preserv)n(ed)f(\(although)j(the)g(in)n(tro)r (duction)f(of)g(new)h(collinearities)f(is)g(allo)n(w)n(ed\).)676 3033 y(W)-7 b(e)34 b(sho)n(w)f(that)i(the)f(question)g(of)g (determining)g(whether)g(a)g(link)-5 b(age)34 b(can)g(b)r(e)676 3132 y(em)n(b)r(edded)28 b(on)g(the)h(in)n(teger)e(lattice)i(is)f (strongly)f Fq(N)12 b(P)7 b Fs(-complete.)39 b(Indeed,)28 b(w)n(e)676 3232 y(sho)n(w)18 b(that)h(ev)n(en)f(with)i Fr(\017)i Fs(=)h(0)18 b(\(under)h(whic)n(h)g(the)h(problem)e(b)r (ecomes)h(\\Can)f(this)676 3331 y(link)-5 b(age)26 b(b)r(e)i(em)n(b)r (edded?"\),)g(the)g(problem)f(remains)f(strongly)g Fq(N)12 b(P)7 b Fs(-complete.)676 3431 y(Ho)n(w)n(ev)n(er)23 b(for)i(some)g(applications,)g(it)h(is)g(reasonable)d(to)i(assume)g (that)h(lengths)676 3531 y(of)j(the)g(links)g(and)g(the)h(n)n(um)n(b)r (er)f(of)g(\\co-inciden)n(t")e(cycles)i(are)f(b)r(ounded)h(\(t)n(w)n(o) 676 3630 y(cycles)38 b(are)g(co-inciden)n(t)h(if)g(they)h(share)e(an)h (edge\).)71 b(W)-7 b(e)39 b(sho)n(w)g(that)g(under)676 3730 y(these)e(b)r(ounding)g(assumptions,)i(there)e(is)g(a)g(p)r (olynomial)g(time)g(solution)g(to)676 3830 y(the)28 b(problem.)448 4115 y Fp(1)135 b(In)l(tro)t(duction)448 4318 y Fo(In)28 b(la)m(y)m(out)i(on)e(a)h(computer)g(screen,)g(lo)s(cation)f({)h(esp)s (ecially)e(lo)s(cation)h(at)i(an)e(in)m(teger-)448 4431 y(grid)f(p)s(oin)m(t)h({)h(can)f(b)s(e)g(more)g(imp)s(ortan)m(t)g(than) g(getting)h(lengths)f(exactly)h(righ)m(t.)39 b(One)448 4544 y(can)22 b(mo)s(del)e(suc)m(h)g(a)i(situation)e(b)m(y)h(building)c (an)k(\\erector)i(set")f(t)m(yp)s(e)f(link)-5 b(age)21 b(that)g(uses)448 4657 y(straigh)m(t,)27 b(\014xed-length)d(links)e (and)j(join)m(ts.)38 b(Angles)25 b(are)g(free)g(to)g(c)m(hange,)j(but)c (lengths)p 448 4734 1196 4 v 551 4788 a Fn(\003)587 4820 y Fm(Supp)r(orted)g(b)n(y)h(NSF)g(gran)n(ts)h(CCR-9204630)i(and)e(CD)n (A{9753055.)554 4882 y Fn(y)587 4913 y Fm(Supp)r(orted)e(b)n(y)h(NSF)g (gran)n(t)h(CCR-9505446)1920 5162 y Fo(1)p eop %%Page: 2 2 2 1 bop 448 623 a Fo(and)28 b(collinearit)m(y)f(prop)s(erties)g(of)h (the)h(link)-5 b(age)27 b(are)i(\014xed.)40 b(A)28 b(problem)f(in)g (computer-)448 736 y(aided)k(design)g([8)q(])h(raised)g(the)g(question) f(of)h(when)g(a)g(link)-5 b(age)31 b(can)i(b)s(e)e(em)m(b)s(edded)g(on) 448 848 y(an)j(in)m(teger)f(grid)g(\(that)h(is)e(with)h(its)f(v)m (ertices)j(at)f(in)m(teger)g(lattice)f(p)s(oin)m(ts\),)h(or)f(if)g(the) 448 961 y(link)-5 b(age)25 b(could)g(not)h(b)s(e)g(so)g(em)m(b)s (edded,)g(what)g(w)m(as)g(the)g(minimal)d Fl(\017)j Fo(needed)f(to)i (ensure)448 1074 y(that)42 b(the)f(v)m(ertices)h(of)f(the)h(link)-5 b(age)40 b(are)h(em)m(b)s(edded)f(on)h(in)m(teger)h(lattice)f(p)s(oin)m (ts)f(if)448 1187 y(one)d(is)e(allo)m(w)m(ed)h(to)h(shrink)d(or)i (stretc)m(h)h(lengths)f(of)g(the)h(links)d(b)m(y)i Fl(\017)p Fo(.)58 b(Graph)35 b(edges)448 1300 y(are)h(allo)m(w)m(ed)f(to)g(cross) h(and)e(ev)m(en)i(to)g(coincide,)f(but)g(the)g(underlying)d (connectivit)m(y)448 1413 y(prop)s(erties)d(of)i(the)f(graph)g(m)m(ust) g(b)s(e)g(unc)m(hanged)g(under)f(this)g Fl(\017)h Fo(transformation.) 589 1526 y(Supp)s(ose)k(edges)j(are)f(allo)m(w)m(ed)f(to)i(stretc)m(h)f (or)g(shrink)d(b)m(y)j(a)g(giv)m(en)g Fl(\017)p Fo(.)56 b(W)-8 b(e)37 b(sho)m(w)448 1639 y(that)28 b(the)g(question)e(of)i (determining)d(whether)h(a)i(link)-5 b(age)26 b(can)i(b)s(e)f(em)m(b)s (edded)f(on)h(the)448 1752 y(in)m(teger)c(lattice)h(is)d Fk(N)13 b(P)8 b Fo(-complete.)39 b(Indeed,)24 b(w)m(e)f(sho)m(w)g(that) g(ev)m(en)g(with)f Fl(\017)j Fo(=)g(0)e(\(under)448 1865 y(whic)m(h)i(the)h(problem)e(b)s(ecomes)i(\\Can)g(this)e(link)-5 b(age)25 b(b)s(e)g(em)m(b)s(edded?"\),)i(the)f(problem)448 1978 y(remains)36 b Fk(N)13 b(P)7 b Fo(-complete.)60 b(Ho)m(w)m(ev)m(er)39 b(for)d(some)h(applications,)f(it)g(is)g (reasonable)g(to)448 2090 y(assume)29 b(that)h(lengths)f(of)g(the)g (links)e(and)i(the)g(n)m(um)m(b)s(er)f(of)h(\\co-inciden)m(t")h(cycles) g(are)448 2203 y(b)s(ounded)j(\(t)m(w)m(o)j(cycles)f(are)f(co-inciden)m (t)h(if)e(they)i(share)f(an)g(edge\).)54 b(W)-8 b(e)36 b(sho)m(w)e(that)448 2316 y(under)g(these)i(b)s(ounding)d(assumptions,) j(there)f(is)g(a)h(p)s(olynomial)d(time)i(solution)f(to)448 2429 y(the)d(problem.)1034 2547 y 14340424 7170212 9998827 36837785 24339251 44007997 startTexFig 1034 2547 a %%BeginDocument: idraw/neil1.ps /arrowHeight 13 def /arrowWidth 6 def /IdrawDict 52 dict def IdrawDict begin /reencodeISO { dup dup findfont dup length dict begin { 1 index /FID ne { def }{ pop pop } ifelse } forall /Encoding ISOLatin1Encoding def currentdict end definefont } def /ISOLatin1Encoding [ /.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef /.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef /.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef /.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef /space/exclam/quotedbl/numbersign/dollar/percent/ampersand/quoteright /parenleft/parenright/asterisk/plus/comma/minus/period/slash /zero/one/two/three/four/five/six/seven/eight/nine/colon/semicolon /less/equal/greater/question/at/A/B/C/D/E/F/G/H/I/J/K/L/M/N /O/P/Q/R/S/T/U/V/W/X/Y/Z/bracketleft/backslash/bracketright /asciicircum/underscore/quoteleft/a/b/c/d/e/f/g/h/i/j/k/l/m /n/o/p/q/r/s/t/u/v/w/x/y/z/braceleft/bar/braceright/asciitilde /.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef /.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef /.notdef/dotlessi/grave/acute/circumflex/tilde/macron/breve /dotaccent/dieresis/.notdef/ring/cedilla/.notdef/hungarumlaut /ogonek/caron/space/exclamdown/cent/sterling/currency/yen/brokenbar /section/dieresis/copyright/ordfeminine/guillemotleft/logicalnot /hyphen/registered/macron/degree/plusminus/twosuperior/threesuperior /acute/mu/paragraph/periodcentered/cedilla/onesuperior/ordmasculine /guillemotright/onequarter/onehalf/threequarters/questiondown /Agrave/Aacute/Acircumflex/Atilde/Adieresis/Aring/AE/Ccedilla /Egrave/Eacute/Ecircumflex/Edieresis/Igrave/Iacute/Icircumflex /Idieresis/Eth/Ntilde/Ograve/Oacute/Ocircumflex/Otilde/Odieresis /multiply/Oslash/Ugrave/Uacute/Ucircumflex/Udieresis/Yacute /Thorn/germandbls/agrave/aacute/acircumflex/atilde/adieresis /aring/ae/ccedilla/egrave/eacute/ecircumflex/edieresis/igrave /iacute/icircumflex/idieresis/eth/ntilde/ograve/oacute/ocircumflex /otilde/odieresis/divide/oslash/ugrave/uacute/ucircumflex/udieresis /yacute/thorn/ydieresis ] def /Helvetica reencodeISO def /Courier reencodeISO def /none null def /numGraphicParameters 17 def /stringLimit 65535 def /Begin { save numGraphicParameters dict begin } def /End { end restore } def /SetB { dup type /nulltype eq { pop false /brushRightArrow idef false /brushLeftArrow idef true /brushNone idef } { /brushDashOffset idef /brushDashArray idef 0 ne /brushRightArrow idef 0 ne /brushLeftArrow idef /brushWidth idef false /brushNone idef } ifelse } def /SetCFg { /fgblue idef /fggreen idef /fgred idef } def /SetCBg { /bgblue idef /bggreen idef /bgred idef } def /SetF { /printSize idef /printFont idef } def /SetP { dup type /nulltype eq { pop true /patternNone idef } { dup -1 eq { /patternGrayLevel idef /patternString idef } { /patternGrayLevel idef } ifelse false /patternNone idef } ifelse } def /BSpl { 0 begin storexyn newpath n 1 gt { 0 0 0 0 0 0 1 1 true subspline n 2 gt { 0 0 0 0 1 1 2 2 false subspline 1 1 n 3 sub { /i exch def i 1 sub dup i dup i 1 add dup i 2 add dup false subspline } for n 3 sub dup n 2 sub dup n 1 sub dup 2 copy false subspline } if n 2 sub dup n 1 sub dup 2 copy 2 copy false subspline patternNone not brushLeftArrow not brushRightArrow not and and { ifill } if brushNone not { istroke } if 0 0 1 1 leftarrow n 2 sub dup n 1 sub dup rightarrow } if end } dup 0 4 dict put def /Circ { newpath 0 360 arc patternNone not { ifill } if brushNone not { istroke } if } def /CBSpl { 0 begin dup 2 gt { storexyn newpath n 1 sub dup 0 0 1 1 2 2 true subspline 1 1 n 3 sub { /i exch def i 1 sub dup i dup i 1 add dup i 2 add dup false subspline } for n 3 sub dup n 2 sub dup n 1 sub dup 0 0 false subspline n 2 sub dup n 1 sub dup 0 0 1 1 false subspline patternNone not { ifill } if brushNone not { istroke } if } { Poly } ifelse end } dup 0 4 dict put def /Elli { 0 begin newpath 4 2 roll translate scale 0 0 1 0 360 arc patternNone not { ifill } if brushNone not { istroke } if end } dup 0 1 dict put def /Line { 0 begin 2 storexyn newpath x 0 get y 0 get moveto x 1 get y 1 get lineto brushNone not { istroke } if 0 0 1 1 leftarrow 0 0 1 1 rightarrow end } dup 0 4 dict put def /MLine { 0 begin storexyn newpath n 1 gt { x 0 get y 0 get moveto 1 1 n 1 sub { /i exch def x i get y i get lineto } for patternNone not brushLeftArrow not brushRightArrow not and and { ifill } if brushNone not { istroke } if 0 0 1 1 leftarrow n 2 sub dup n 1 sub dup rightarrow } if end } dup 0 4 dict put def /Poly { 3 1 roll newpath moveto -1 add { lineto } repeat closepath patternNone not { ifill } if brushNone not { istroke } if } def /Rect { 0 begin /t exch def /r exch def /b exch def /l exch def newpath l b moveto l t lineto r t lineto r b lineto closepath patternNone not { ifill } if brushNone not { istroke } if end } dup 0 4 dict put def /Text { ishow } def /idef { dup where { pop pop pop } { exch def } ifelse } def /ifill { 0 begin gsave patternGrayLevel -1 ne { fgred bgred fgred sub patternGrayLevel mul add fggreen bggreen fggreen sub patternGrayLevel mul add fgblue bgblue fgblue sub patternGrayLevel mul add setrgbcolor eofill } { eoclip originalCTM setmatrix pathbbox /t exch def /r exch def /b exch def /l exch def /w r l sub ceiling cvi def /h t b sub ceiling cvi def /imageByteWidth w 8 div ceiling cvi def /imageHeight h def bgred bggreen bgblue setrgbcolor eofill fgred fggreen fgblue setrgbcolor w 0 gt h 0 gt and { l b translate w h scale w h true [w 0 0 h neg 0 h] { patternproc } imagemask } if } ifelse grestore end } dup 0 8 dict put def /istroke { gsave brushDashOffset -1 eq { [] 0 setdash 1 setgray } { brushDashArray brushDashOffset setdash fgred fggreen fgblue setrgbcolor } ifelse brushWidth setlinewidth originalCTM setmatrix stroke grestore } def /ishow { 0 begin gsave fgred fggreen fgblue setrgbcolor /fontDict printFont printSize scalefont dup setfont def /descender fontDict begin 0 [FontBBox] 1 get FontMatrix end transform exch pop def /vertoffset 1 printSize sub descender sub def { 0 vertoffset moveto show /vertoffset vertoffset printSize sub def } forall grestore end } dup 0 3 dict put def /patternproc { 0 begin /patternByteLength patternString length def /patternHeight patternByteLength 8 mul sqrt cvi def /patternWidth patternHeight def /patternByteWidth patternWidth 8 idiv def /imageByteMaxLength imageByteWidth imageHeight mul stringLimit patternByteWidth sub min def /imageMaxHeight imageByteMaxLength imageByteWidth idiv patternHeight idiv patternHeight mul patternHeight max def /imageHeight imageHeight imageMaxHeight sub store /imageString imageByteWidth imageMaxHeight mul patternByteWidth add string def 0 1 imageMaxHeight 1 sub { /y exch def /patternRow y patternByteWidth mul patternByteLength mod def /patternRowString patternString patternRow patternByteWidth getinterval def /imageRow y imageByteWidth mul def 0 patternByteWidth imageByteWidth 1 sub { /x exch def imageString imageRow x add patternRowString putinterval } for } for imageString end } dup 0 12 dict put def /min { dup 3 2 roll dup 4 3 roll lt { exch } if pop } def /max { dup 3 2 roll dup 4 3 roll gt { exch } if pop } def /midpoint { 0 begin /y1 exch def /x1 exch def /y0 exch def /x0 exch def x0 x1 add 2 div y0 y1 add 2 div end } dup 0 4 dict put def /thirdpoint { 0 begin /y1 exch def /x1 exch def /y0 exch def /x0 exch def x0 2 mul x1 add 3 div y0 2 mul y1 add 3 div end } dup 0 4 dict put def /subspline { 0 begin /movetoNeeded exch def y exch get /y3 exch def x exch get /x3 exch def y exch get /y2 exch def x exch get /x2 exch def y exch get /y1 exch def x exch get /x1 exch def y exch get /y0 exch def x exch get /x0 exch def x1 y1 x2 y2 thirdpoint /p1y exch def /p1x exch def x2 y2 x1 y1 thirdpoint /p2y exch def /p2x exch def x1 y1 x0 y0 thirdpoint p1x p1y midpoint /p0y exch def /p0x exch def x2 y2 x3 y3 thirdpoint p2x p2y midpoint /p3y exch def /p3x exch def movetoNeeded { p0x p0y moveto } if p1x p1y p2x p2y p3x p3y curveto end } dup 0 17 dict put def /storexyn { /n exch def /y n array def /x n array def n 1 sub -1 0 { /i exch def y i 3 2 roll put x i 3 2 roll put } for } def /SSten { fgred fggreen fgblue setrgbcolor dup true exch 1 0 0 -1 0 6 -1 roll matrix astore } def /FSten { dup 3 -1 roll dup 4 1 roll exch newpath 0 0 moveto dup 0 exch lineto exch dup 3 1 roll exch lineto 0 lineto closepath bgred bggreen bgblue setrgbcolor eofill SSten } def /Rast { exch dup 3 1 roll 1 0 0 -1 0 6 -1 roll matrix astore } def /arrowhead { 0 begin transform originalCTM itransform /taily exch def /tailx exch def transform originalCTM itransform /tipy exch def /tipx exch def /dy tipy taily sub def /dx tipx tailx sub def /angle dx 0 ne dy 0 ne or { dy dx atan } { 90 } ifelse def gsave originalCTM setmatrix tipx tipy translate angle rotate newpath arrowHeight neg arrowWidth 2 div moveto 0 0 lineto arrowHeight neg arrowWidth 2 div neg lineto patternNone not { originalCTM setmatrix /padtip arrowHeight 2 exp 0.25 arrowWidth 2 exp mul add sqrt brushWidth mul arrowWidth div def /padtail brushWidth 2 div def tipx tipy translate angle rotate padtip 0 translate arrowHeight padtip add padtail add arrowHeight div dup scale arrowheadpath ifill } if brushNone not { originalCTM setmatrix tipx tipy translate angle rotate arrowheadpath istroke } if grestore end } dup 0 9 dict put def /arrowheadpath { newpath arrowHeight neg arrowWidth 2 div moveto 0 0 lineto arrowHeight neg arrowWidth 2 div neg lineto } def /leftarrow { 0 begin y exch get /taily exch def x exch get /tailx exch def y exch get /tipy exch def x exch get /tipx exch def brushLeftArrow { tipx tipy tailx taily arrowhead } if end } dup 0 4 dict put def /rightarrow { 0 begin y exch get /tipy exch def x exch get /tipx exch def y exch get /taily exch def x exch get /tailx exch def brushRightArrow { tipx tipy tailx taily arrowhead } if end } dup 0 4 dict put def %I Idraw 10 Grid 8 8 Begin %I b u %I cfg u %I cbg u %I f u %I p u %I t [ 0.619552 0 0 0.619552 0 0 ] concat /originalCTM matrix currentmatrix def Begin %I Elli %I b 65535 0 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 0 SetP %I t [ 1 0 0 1 257 186 ] concat %I 105 874 4 4 Elli End Begin %I Elli %I b 65535 0 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 0 SetP %I t [ 1 0 0 1 467 158 ] concat %I 105 874 4 4 Elli End Begin %I Elli %I b 65535 0 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 0 SetP %I t [ 1 0 0 1 302 55 ] concat %I 105 874 4 4 Elli End Begin %I Line %I b 65535 2 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 0 SetP %I t [ 1 0 0 1 75 185 ] concat %I 204 782 287 874 Line %I 1 End Begin %I Line %I b 65535 2 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 0 SetP %I t [ 1 0 0 1 75 185 ] concat %I 287 875 498 846 Line %I 1 End Begin %I Line %I b 65535 2 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 0 SetP %I t [ 1 0 0 1 75 185 ] concat %I 497 846 332 742 Line %I 1 End Begin %I Line %I b 65535 2 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 0 SetP %I t [ 1 0 0 1 76 183 ] concat %I 332 744 201 784 Line %I 1 End Begin %I Elli %I b 65535 0 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 0 SetP %I t [ 1 0 0 1 259 140 ] concat %I 105 874 4 4 Elli End Begin %I Elli %I b 65535 0 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 0 SetP %I t [ 1 0 0 1 175 96 ] concat %I 105 874 4 4 Elli End Begin %I Elli %I b 65535 0 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 0 SetP %I t [ 1 0 0 1 378 102 ] concat %I 105 874 4 4 Elli End Begin %I Elli %I b 65535 0 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 0 SetP %I t [ 1 0 0 1 366 128 ] concat %I 105 874 4 4 Elli End Begin %I Line %I b 65535 2 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 0 SetP %I t [ 1 0 0 1 75 185 ] concat %I 207 786 289 830 Line %I 1 End Begin %I Line %I b 65535 2 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 0 SetP %I t [ 1 0 0 1 75 185 ] concat %I 289 830 397 816 Line %I 1 End Begin %I Line %I b 65535 2 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 0 SetP %I t [ 1 0 0 1 75 185 ] concat %I 397 816 409 790 Line %I 1 End Begin %I Line %I b 65535 2 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 0 SetP %I t [ 1 0 0 1 75 185 ] concat %I 397 818 287 875 Line %I 1 End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-helvetica-medium-r-*-120-* Helvetica 12 SetF %I t [ 1 0 0 1 583 1036 ] concat %I [ (v) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-helvetica-medium-r-*-120-* Helvetica 12 SetF %I t [ 1 0 0 1 478 1010 ] concat %I [ (v) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-helvetica-medium-r-*-120-* Helvetica 12 SetF %I t [ 1 0 0 1 493 968 ] concat %I [ (v) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-helvetica-medium-r-*-120-* Helvetica 12 SetF %I t [ 1 0 0 1 421 923 ] concat %I [ (v) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-helvetica-medium-r-*-120-* Helvetica 12 SetF %I t [ 1 0 0 1 351 1030 ] concat %I [ (v) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-helvetica-medium-r-*-120-* Helvetica 12 SetF %I t [ 1 0 0 1 250 977 ] concat %I [ (v) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-helvetica-medium-r-*-120-* Helvetica 12 SetF %I t [ 1 0 0 1 336 1074 ] concat %I [ (v) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 425 917 ] concat %I [ (1) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 498 963 ] concat %I [ (2) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 589 1030 ] concat %I [ (3) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 342 1068 ] concat %I [ (4) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 355 1024 ] concat %I [ (6) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 255 970 ] concat %I [ (5) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 483 1002 ] concat %I [ (7) ] Text End End %I eop showpage end %%EndDocument endTexFig 789 3651 a Fo(Figure)f(1:)41 b(A)31 b(Link)-5 b(age)30 b(with)f(Eigh)m(t)h(Links)f(and)h(Sev)m(en)g(V)-8 b(ertices.)589 3863 y(This)26 b(problem)g(has)h(ob)m(vious)g(applications)f(to)i (displa)m(ying)d(and)i(prin)m(ting)e(of)j(dia-)448 3976 y(grams.)39 b(Similarly)-8 b(,)23 b(in)g(fabrication)g(of)h(man)m(y)h (kinds)d(of)j(materials)f(including)c(circuits)448 4089 y(or)28 b(mac)m(hinary)-8 b(,)29 b(it)e(is)g(con)m(v)m(enien)m(t)i(to)g (ha)m(v)m(e)g(certain)f(p)s(oin)m(ts)f(of)h(the)g(design)f(placed)g(on) 448 4202 y(ev)m(enly)g(spaced)f(grid)f(p)s(oin)m(ts.)38 b(Similar)23 b(issues)i(come)j(up)d(with)g(rob)s(ot)h(placemen)m(t)h (and)448 4315 y(assem)m(bly)j(b)m(y)g(rob)s(ot.)589 4428 y(W)-8 b(e)39 b(note)e(that)h(the)f(problem)f(has)h(some)g(ob)m(vious)g (ties)g(to)g(n)m(um)m(b)s(er)f(theory:)55 b(a)448 4541 y(link)-5 b(age)29 b(can)g(b)s(e)g(em)m(b)s(edded)f(only)g(if)g(eac)m (h)i(of)f(its)g(links)e(can)i(b)s(e)g(em)m(b)s(edded,)f(and)h(the)448 4654 y(latter)h(can)h(happ)s(en)d(if)g(and)i(only)f(if)f(eac)m(h)j(of)f (the)g(links)e(has)h(a)i(length)e(whose)g(square)448 4767 y(can)j(b)s(e)f(written)f(as)i(the)f(sum)g(of)g(t)m(w)m(o)i (squares.)44 b(W)-8 b(e)32 b(explore)f(these)h(connections)f(in)448 4880 y(the)g(pap)s(er.)1920 5162 y(2)p eop %%Page: 3 3 3 2 bop 589 623 a Fo(This)20 b(pap)s(er)f(is)h(organized)h(as)g(follo)m (ws:)36 b Fk(x)p Fo(2)21 b(Em)m(b)s(edding)e(Fixed)h(Length)h(Link)-5 b(ages,)448 736 y Fk(x)p Fo(3)31 b(Em)m(b)s(edding)e(Link)-5 b(ages)30 b(with)f(Restrictions,)g(and)h Fk(x)p Fo(4)h(What)g(is)f(the) g(minimal)e Fl(\017)p Fo(?.)448 1022 y Fp(2)135 b(Em)l(b)t(edding)45 b(Fixed)g(Length)g(Link)-7 b(ages)448 1225 y Fo(A)30 b(link)-5 b(age)28 b Fk(L)h Fo(is)g(de\014ned)f(as)h(a)h(connected)g (graph)f(with)f(\014xed-length)h(edges.)41 b(A)29 b(link)448 1338 y(is)i(an)g(edge)h(of)g(\014nite)e(length.)44 b(By)32 b(abuse)f(of)g(notation,)i(the)e(lengths)g(of)h(eac)m(h)g(of)g(the)448 1451 y(links)g(will)g(b)s(e)i(denoted)g(b)m(y)g(the)h(same)f(sym)m(b)s (ol)f(that)i(is)e(used)h(to)h(denote)g(the)f(edge:)448 1564 y Fl(l)475 1578 y Fj(1)515 1564 y Fl(;)15 b(:)g(:)g(:)h(;)f(l)743 1578 y Fi(n)791 1564 y Fo(.)40 b(Links)25 b(m)m(ust)j(b)s(e)e(of)i(p)s (ositiv)m(e)e(length,)i(and)e(eac)m(h)j(link)c Fl(l)2755 1578 y Fi(i)2811 1564 y Fo(has)i(t)m(w)m(o)i(distinct)448 1677 y(endp)s(oin)m(ts,)i Fl(c)929 1691 y Fi(i)990 1677 y Fo(and)h Fl(d)1216 1691 y Fi(i)1244 1677 y Fo(.)46 b(A)32 b(link)e(ma)m(y)j(also)f(con)m(tain)h(lab)s(elled)c(in)m (termediate)j(p)s(oin)m(ts.)448 1789 y(In)g(that)h(case,)h(the)f(v)m (ertex)g(whic)m(h)e(lies)h(within)d(another)k(link)d(is)i(collinear)f (with)g(the)448 1902 y(endp)s(oin)m(ts)38 b(of)h(the)g(link)e(in)g (whic)m(h)h(it)g(lies.)66 b(F)-8 b(or)39 b(example,)i(in)d(Figure)g(1,) k(the)d(link)448 2015 y(\()p Fl(v)527 2029 y Fj(1)567 2015 y Fl(;)15 b(v)651 2029 y Fj(2)691 2015 y Fl(;)g(v)775 2029 y Fj(3)815 2015 y Fo(\))34 b(m)m(ust)f(consist)g(of)h(three)g (collinear)e(p)s(oin)m(ts,)h(and)g(the)h(distances)f(\()p Fl(v)3238 2029 y Fj(1)3278 2015 y Fl(;)15 b(v)3362 2029 y Fj(2)3402 2015 y Fo(\))448 2128 y(and)30 b(\()p Fl(v)704 2142 y Fj(2)744 2128 y Fl(;)15 b(v)828 2142 y Fj(3)868 2128 y Fo(\))31 b(are)f(\014xed.)589 2241 y(An)i(arbitrary)e(n)m(um)m (b)s(er)h(of)h(links)e(ma)m(y)i(connect)h(to)f(a)g(single)f(v)m(ertex.) 46 b(W)-8 b(e)33 b(sa)m(y)g(a)448 2354 y(link)-5 b(age)21 b(can)h(b)s(e)f(em)m(b)s(edded)f(on)i(an)f(in)m(teger)h(lattice)g(if)f (there)h(is)f(a)g(ph)m(ysical)g(realization)448 2467 y(of)27 b(the)g(link)-5 b(age)26 b(that)h(preserv)m(es)g(collinearit)m (y)f(and)g(connectedness)h(prop)s(erties)e(while)448 2580 y(em)m(b)s(edding)39 b(the)i(link)-5 b(age)39 b(on)i(the)f (lattice)h(in)e(suc)m(h)i(a)f(w)m(a)m(y)i(that)f(the)g(v)m(ertices)g (are)448 2693 y(placed)f(on)f(in)m(teger)i(lattice)f(p)s(oin)m(ts.)68 b(\(It)40 b(is)f(no)h(problem)e(if)h(the)h(link)d(also)j(passes)448 2806 y(through)28 b(a)h(lattice)g(p)s(oin)m(t.\))40 b(W)-8 b(e)30 b(sa)m(y)f(a)g(link)-5 b(age)28 b(can)h(b)s(e)f Fl(\017)p Fo(-em)m(b)s(edded)g(on)g(an)h(in)m(teger)448 2919 y(lattice)34 b(if)e(there)h(is)g(another)g(link)-5 b(age)32 b Fk(L)1852 2886 y Fu(0)1909 2919 y Fo(suc)m(h)g(that)i(for)f (eac)m(h)h(link)e Fl(l)2875 2933 y Fi(i)2936 2919 y Fo(in)g Fk(L)h Fo(there)g(is)448 3032 y(a)38 b(link)d Fl(l)746 2999 y Fu(0)744 3056 y Fi(i)809 3032 y Fo(in)h Fk(L)985 2999 y Fu(0)1045 3032 y Fo(where)g Fk(j)p Fl(l)1366 3046 y Fi(i)1419 3032 y Fk(\000)25 b Fl(l)1544 2999 y Fu(0)1542 3056 y Fi(i)1570 3032 y Fk(j)37 b(\024)f Fl(\017)p Fo(,)i(the)g (adjacency)f(matrices)g(of)h Fk(L)e Fo(and)h Fk(L)3256 2999 y Fu(0)3316 3032 y Fo(are)448 3144 y(the)g(same,)h(an)m(y)f (necessarily)e(collinear)g(p)s(oin)m(ts)h(of)g Fk(L)g Fo(are)h(collinear)e(in)g Fk(L)3069 3111 y Fu(0)3128 3144 y Fo(and)h(the)448 3257 y(v)m(ertices)31 b(of)g Fk(L)944 3224 y Fu(0)997 3257 y Fo(lie)e(on)i(in)m(teger)f(lattice)h(p) s(oin)m(ts.)589 3370 y(W)-8 b(e)24 b(are)e(in)m(terested)g(in)e(the)j (problem)d(of)i(giv)m(en)g(a)g(link)-5 b(age)21 b Fk(L)p Fo(,)j(\014nd)c(the)i(minim)m(um)d Fl(\017)448 3483 y Fo(suc)m(h)25 b(that)g Fk(L)f Fo(can)h(b)s(e)g Fl(\017)p Fk(\000)p Fo(em)m(b)s(edded)e(on)h(an)h(in)m(teger)g(lattice)g(in)f(t)m (w)m(o)i(dimensions.)36 b(W)-8 b(e)448 3596 y(will)29 b(allo)m(w)i(links)f(to)i(lie)f(up)s(on)f(one)i(another)f(and)g(to)i (cross.)44 b(In)31 b(the)h(usual)e(w)m(a)m(y)-8 b(,)34 b(the)448 3709 y(size)e(of)f(the)h(problem)d(is)i(the)g(size)h(of)f (the)h(input,)e(\006)15 b(log)h Fl(l)2433 3723 y Fi(i)2461 3709 y Fo(.)44 b(W)-8 b(e)33 b(mak)m(e)f(the)g(follo)m(wing)448 3822 y(observ)-5 b(ation:)448 4034 y Fh(Theorem)34 b(2.1)46 b Fg(A)23 b(linkage)g Fk(L)g Fg(with)i(links)e(of)h(length)f Fl(l)2320 4048 y Fj(1)2360 4034 y Fl(;)15 b(l)2427 4048 y Fj(2)2467 4034 y Fl(;)g(:)g(:)g(:)i(;)e(l)2696 4048 y Fi(n)2766 4034 y Fg(c)-5 b(an)24 b(b)-5 b(e)24 b Fl(\017)p Fg(-emb)-5 b(e)g(dde)g(d)448 4147 y(on)36 b(a)g(two)g(dimensional)h (inte)-5 b(ger)35 b(grid)h(only)g(if)f(for)h(e)-5 b(ach)36 b Fl(i)30 b Fo(=)g(1)p Fl(;)15 b(:)g(:)g(:)i(;)e(n)p Fg(,)35 b(ther)-5 b(e)36 b(is)g(an)448 4260 y(inte)-5 b(ger)34 b Fl(n)805 4274 y Fi(i)865 4260 y Fg(such)g(that)1259 4202 y Fk(p)p 1335 4202 83 4 v 58 x Fl(n)1390 4274 y Fi(i)1444 4260 y Fk(2)25 b Fo([)p Fl(l)1582 4274 y Fi(i)1632 4260 y Fk(\000)20 b Fl(\017;)15 b(l)1827 4274 y Fi(i)1876 4260 y Fo(+)20 b Fl(\017)p Fo(])33 b Fg(and)h Fl(n)2294 4274 y Fi(i)2355 4260 y Fg(is)f(expr)-5 b(essible)34 b(as)g(the)f(sum)h(of)448 4373 y(two)g(squar)-5 b(es.)448 4611 y Fh(Pro)s(of)32 b Fo(Ob)m(vious.)2286 b Ff(2)589 4773 y Fo(In)28 b(the)g(remainder)f(of)h(this)f(section)h(w)m(e)h (limit)d(ourselv)m(es)h(to)i(a)g(simpler)c(problem:)448 4886 y(w)m(e)44 b(consider)f(the)h(problem)e(of)h(em)m(b)s(edding)f (with)h Fl(\017)k Fo(=)g(0.)81 b(W)-8 b(e)44 b(b)s(egin)f(with)f(the) 1920 5162 y(3)p eop %%Page: 4 4 4 3 bop 448 623 a Fo(follo)m(wing)38 b(w)m(ell-kno)m(wn)g(c)m (haracterization)i(of)f(whic)m(h)f(in)m(tegers)h(can)g(b)s(e)g(written) f(as)448 736 y(the)31 b(sum)e(of)i(t)m(w)m(o)h(squares.)448 948 y Fh(Theorem)i(2.2)46 b Fg(\([5)q(],)34 b(p)-5 b(g.)47 b(299\))35 b(A)f(numb)-5 b(er)34 b Fl(n)g Fg(is)g(the)h(sum)f(of)g(two) h(squar)-5 b(es)35 b(if)f(and)448 1061 y(only)e(if)e(al)5 b(l)31 b(prime)g(factors)h(of)f Fl(n)f Fg(of)h(the)g(form)g Fo(4)p Fl(m)16 b Fo(+)g(3)31 b Fg(have)g(even)f(exp)-5 b(onents)32 b(in)f(the)448 1174 y(prime)j(factorization)h(of)d Fl(n)p Fg(.)589 1386 y Fo(W)-8 b(e)33 b(will)d(let)h(the)h(sym)m(b)s (ol)f Fl(p)1570 1400 y Fi(i)1629 1386 y Fo(denote)i(a)f(prime)e (congruen)m(t)i(to)h(1)f(mo)s(d)f(4,)i(and)e Fl(q)3401 1400 y Fi(j)448 1499 y Fo(denote)i(a)f(prime)f(congruen)m(t)h(to)h(3)f (mo)s(d)f(4.)46 b(Let)33 b Fl(r)2221 1513 y Fj(2)2260 1499 y Fo(\()p Fl(n)p Fo(\))f(b)s(e)g(the)g(n)m(um)m(b)s(er)e(of)j (distinct)448 1612 y(represen)m(tations)25 b(of)f Fl(n)g Fo(as)h(the)g(sum)e(of)i(t)m(w)m(o)h(squares;)g(w)m(e)f(coun)m(t)g(t)m (w)m(o)h(represen)m(tations)448 1725 y(\()p Fl(a;)15 b(b)p Fo(\))32 b(and)e(\()p Fl(c;)15 b(d)p Fo(\))32 b(as)e(distinct)f (i\013)h(\()p Fl(a;)15 b(b)p Fo(\))26 b Fk(6)p Fo(=)f(\()p Fl(c;)15 b(d)p Fo(\).)42 b(Then)30 b(w)m(e)h(ha)m(v)m(e:)448 1938 y Fh(Theorem)j(2.3)46 b Fg(\([5)q(],)k(p)-5 b(g.)84 b(242\))48 b(Supp)-5 b(ose)49 b Fl(n)h Fo(=)g(2)2339 1905 y Fi(\013)2389 1938 y Fo(\005)p Fl(p)2503 1896 y Fi(r)2535 1906 y Fe(i)2503 1964 y Fi(i)2566 1938 y Fo(\005)p Fl(q)2678 1887 y Fi(s)2711 1897 y Fe(j)2675 1964 y Fi(j)2747 1938 y Fg(.)84 b(Then)47 b Fl(r)3151 1952 y Fj(2)3190 1938 y Fo(\()p Fl(n)p Fo(\))k(=)448 2051 y(4\005\()p Fl(r)637 2065 y Fi(i)687 2051 y Fo(+)20 b(1\))33 b Fg(if)f(e)-5 b(ach)34 b(of)f(the)g Fl(s)1485 2065 y Fi(j)1553 2051 y Fg(is)g(even,)f(and)h(0)g(otherwise.)589 2263 y Fo(The)d(follo)m (wing)f(is)h(w)m(ell-kno)m(wn)f(information)f(ab)s(out)j(the)f(size)g (of)h Fl(r)2950 2277 y Fj(2)2989 2263 y Fo(\()p Fl(n)p Fo(\):)448 2476 y Fh(Theorem)j(2.4)46 b Fg(\([5)q(],)27 b(p)-5 b(g.)41 b(270\))28 b Fl(r)1662 2490 y Fj(2)1702 2476 y Fo(\()p Fl(n)p Fo(\))d(=)g Fl(O)s Fo(\(\(log)17 b Fl(n)p Fo(\))2313 2443 y Fj(\001)2376 2476 y Fo(\))27 b Fg(is)g(false)g(for)h(every)e(c)-5 b(onstant)448 2589 y Fo(\001)p Fg(.)448 2801 y Fh(Theorem)34 b(2.5)46 b Fg(\([5)q(],)28 b(p)-5 b(g.)41 b(270\))30 b(The)e(maximum)h(or)-5 b(der)30 b(of)e(magnitude)h(for)f Fl(r)3176 2815 y Fj(2)3216 2801 y Fo(\()p Fl(n)p Fo(\))d(=)448 2944 y Fl(O)s Fo(\(2)671 2867 y Fd(log)12 b Fe(n)p 611 2883 249 4 v 611 2924 a Fd(2log)g(log)g Fe(n)874 2944 y Fo(\))p Fg(.)589 3156 y Fo(F)-8 b(or)39 b(simpli\014cation,)d(w)m(e)j(will)c(use)i(the)h (appro)m(ximation)f(that)h Fl(r)2863 3170 y Fj(2)2902 3156 y Fo(\()p Fl(n)p Fo(\))g Fl()g Fo(0.)589 3382 y(The)k(p)s(ossible)e(n)m(um)m(b)s(er)g(of)j (em)m(b)s(eddings)d(implied)f(b)m(y)j(Theorem)g(2.4)h(migh)m(t)e(lead) 448 3495 y(one)f(to)g(susp)s(ect)f(that)h(from)f(a)h(computational)f (viewp)s(oin)m(t,)f(the)i(problem)e(of)h(em)m(b)s(ed-)448 3608 y(ding)35 b(a)i(link)-5 b(age)36 b(in)f(an)h(in)m(teger)h(lattice) g(is)e(hard,)i(and)f(indeed,)h(it)f(is.)58 b(W)-8 b(e)37 b(study)f(a)448 3721 y(simple)29 b(link)-5 b(age)29 b(\014rst.)589 3834 y(The)i(simplest)e(kind)g(of)i(link)-5 b(age)30 b(is)g(one)h(whose)g(underlying)c(graph)k(structure)f(is)448 3946 y(a)h(tree;)g(b)m(y)g(abuse)f(of)g(notation,)h(w)m(e)g(call)f(suc) m(h)g(a)g(link)-5 b(age)30 b(a)h(tree.)41 b(Then)30 b(w)m(e)g(ha)m(v)m (e:)448 4159 y Fh(Lemma)j(2.6)46 b Fg(A)31 b(linkage)h Fk(T)54 b Fg(that)34 b(is)d(a)h(tr)-5 b(e)g(e)33 b(c)-5 b(an)32 b(b)-5 b(e)32 b(emb)-5 b(e)g(dde)g(d)34 b(if)d(and)i(only)g(if) e(e)-5 b(ach)448 4272 y(of)33 b(its)g(links)g(c)-5 b(an)33 b(b)-5 b(e)32 b(emb)-5 b(e)g(dde)g(d.)589 4484 y Fo(An)27 b(em)m(b)s(edding)f(is)g(a)i(function)e(from)h(the)g(v)m(ertices)h(to)h (lattice)e(p)s(oin)m(ts.)39 b(Consider)448 4597 y(t)m(w)m(o)c(em)m(b)s (eddings)c(of)j(the)f(link)-5 b(ages)33 b(that)h(map)f(the)g(ro)s(ot)h (v)m(ertex)g(to)h(the)e(origin;)h(w)m(e)448 4710 y(sa)m(y)d(these)g (are)g(distinct)e(if)g(they)i(are)f(not)h(equal)f(as)h(maps.)40 b(Then)29 b(w)m(e)i(ha)m(v)m(e:)1920 5162 y(4)p eop %%Page: 5 5 5 4 bop 448 623 a Fh(Theorem)34 b(2.7)46 b Fg(Supp)-5 b(ose)34 b(the)e(tr)-5 b(e)g(e)32 b Fk(T)54 b Fg(with)33 b(e)-5 b(dges)32 b Fl(t)2311 637 y Fj(1)2350 623 y Fl(;)15 b(:)g(:)g(:)i(;)e(t)2585 637 y Fi(n)2664 623 y Fg(c)-5 b(an)32 b(b)-5 b(e)32 b(emb)-5 b(e)g(dde)g(d)34 b(on)448 736 y(the)40 b(inte)-5 b(ger)41 b(lattic)-5 b(e,)42 b(and)f(supp)-5 b(ose)41 b Fl(t)1777 703 y Fj(2)1777 760 y Fi(i)1854 736 y Fo(=)d(2)2008 703 y Fi(\013)2053 713 y Fe(i)2085 736 y Fo(\005)2153 750 y Fi(j)2189 736 y Fl(p)2235 684 y Fi(r)2267 694 y Fe(ij)2235 761 y Fi(ij)2326 736 y Fo(\005)2394 751 y Fi(k)2437 736 y Fl(q)2481 693 y Fi(s)2514 705 y Fe(ik)2478 764 y Fi(ik)2617 736 y Fg(with)j Fl(s)2865 751 y Fi(ik)2971 736 y Fg(even)e(for)i(al)5 b(l)448 848 y Fl(ik)t Fg(.)41 b(The)33 b(numb)-5 b(er)33 b(of)f(distinct)h(emb)-5 b(e)g(ddings)33 b(of)g Fk(T)55 b Fg(that)33 b(map)g(the)g(r)-5 b(o)g(ot)34 b(to)f(the)g(origin)448 961 y(e)-5 b(quals)33 b Fo(4)760 928 y Fi(n)808 961 y Fo(\005)876 975 y Fi(i;j)956 961 y Fo(\()p Fl(r)1032 975 y Fi(ij)1113 961 y Fo(+)20 b(1\))p Fg(.)448 1199 y Fh(Pro)s(of)38 b Fo(W)-8 b(e)39 b(b)s(egin)c(b)m(y)i(em)m(b)s(edding)e(the)j(ro)s(ot)f Fl(t)2151 1213 y Fj(1)2227 1199 y Fo(at)h(the)g(origin.)59 b(Ha)m(ving)37 b(decided)448 1312 y(the)29 b(lo)s(cation)e(of)i Fl(c)1087 1326 y Fj(1)1127 1312 y Fo(,)f(there)h(are)f(4\005\()p Fl(r)1749 1326 y Fj(1)p Fi(j)1838 1312 y Fo(+)16 b(1\))29 b(places)f(to)g(lo)s(cate)h Fl(d)2718 1326 y Fj(1)2758 1312 y Fo(.)40 b(The)28 b(em)m(b)s(edding)448 1425 y(of)h(eac)m(h)h Fl(d)800 1439 y Fi(i)856 1425 y Fo(is)e(dep)s(enden)m(t)f(only)h(on)g (the)h(lo)s(cation)f(of)g Fl(c)2344 1439 y Fi(i)2401 1425 y Fo(and)g(the)h(length)f(of)g(the)h(link.)448 1538 y(Th)m(us)38 b(the)i(n)m(um)m(b)s(er)e(of)h(p)s(ossible)e(em)m(b)s (eddings)g(of)i Fl(t)2305 1552 y Fi(i)2372 1538 y Fo(is)f(4\005\()p Fl(r)2661 1552 y Fi(ij)2749 1538 y Fo(+)26 b(1\).)67 b(The)39 b(result)448 1650 y(follo)m(ws)30 b(immediately)-8 b(.)2116 b Ff(2)589 1813 y Fo(This)26 b(result)f(means)i(that)h(c)m (hec)m(king)g(whether)e(a)h(tree)h(can)f(b)s(e)g(em)m(b)s(edded)e(can)j (b)s(e)448 1926 y(done)e(in)e(time)h Fl(O)s Fo(\(\006)p Fl(R)q Fo(\()p Fl(t)1275 1940 y Fi(i)1303 1926 y Fo(\)\),)i(where)e Fl(R)q Fo(\()p Fl(t)1821 1940 y Fi(i)1849 1926 y Fo(\))h(is)f(the)g (time)h(needed)f(to)h(compute)g(whether)448 2039 y Fl(t)481 2053 y Fi(i)536 2039 y Fo(can)i(b)s(e)e(written)g(as)h(the)h(sum)e(of)h (squares.)39 b(A)m(t)28 b(presen)m(t,)g(the)f(fastest)h(algorithm)e(to) 448 2152 y(c)m(hec)m(k)33 b(whether)d(an)h(in)m(teger)g(can)g(b)s(e)f (written)g(as)h(a)g(sum)f(of)h(squares)f(is)g(exp)s(onen)m(tial)448 2265 y(time.)589 2378 y(Indeed)39 b(that)h(problem)e(is)g(lik)m(ely)g (to)i(b)s(e)f(computationally)f(hard.)67 b(In)38 b(the)i(ap-)448 2491 y(p)s(endix,)26 b(w)m(e)i(sho)m(w)f(that)h(if)e(a)i(p)s(ositiv)m (e)e(in)m(teger)i Fl(n)e Fo(has)h(a)h(b)s(ounded)d(n)m(um)m(b)s(er)h (of)i(prime)448 2604 y(factors)42 b(of)f(the)g(form)g(4)p Fl(k)31 b Fo(+)c(1)41 b(and)g(no)g(prime)e(factors)j(of)f(the)g(form)g (4)p Fl(k)31 b Fo(+)c(3,)44 b(the)448 2716 y(problem)30 b(of)h(en)m(umerating)f(the)h(represen)m(tations)g(of)g Fl(n)f Fo(as)h(the)g(sum)f(of)h(t)m(w)m(o)h(squares)448 2829 y(is)d(p)s(olynomial-time)d(equiv)-5 b(alen)m(t)29 b(to)h(factoring)g Fl(n)p Fo(.)40 b(There)29 b(are)g(no)h(kno)m(wn)f (sub)s(exp)s(o-)448 2942 y(nen)m(tial)c(algorithms)g(for)g(factoring)h (general)g(in)m(tegers)f Fl(n)p Fo(.)39 b(But)26 b(em)m(b)s(edding)e(a) i(link)-5 b(age)448 3055 y(is)30 b(computationally)f(exp)s(ensiv)m(e)h (not)g(only)g(for)g(n)m(um)m(b)s(er-theoretic)g(reasons.)589 3168 y(Our)37 b(pro)s(of)g(that)h(the)g(problem)e(is)h Fk(N)13 b(P)7 b(\000)p Fo(complete)38 b(sho)m(ws)g(that)g(the)g (problem)448 3281 y(is)j(strongly)f Fk(N)13 b(P)7 b(\000)p Fo(complete.)74 b(This)39 b(leads)i(us)f(to)i(susp)s(ect)f(that)g(the)h (em)m(b)s(edding)448 3394 y(problem)20 b(is)h(hard)f(computationally)h (b)s(ecause)g(of)h(the)f(complexit)m(y)h(of)f(the)h(in)m(teraction)448 3507 y(of)31 b(cycles)f(of)h(the)g(link)-5 b(age.)589 3620 y(W)d(e)29 b(sho)m(w)e Fk(N)13 b(P)7 b(\000)p Fo(completeness)27 b(b)m(y)g(doing)f(a)i(reduction)e(from)g(3)14 b Fk(\000)g(S)7 b(AT)22 b Fo(.)39 b(Giv)m(en)448 3733 y(a)d(form)m(ula)e Fl(')i Fo(in)e(3-)p Fk(C)5 b(N)13 b(F)c Fo(,)38 b(w)m(e)d(build)e(a)i (link)-5 b(age)35 b(that)g(can)h(b)s(e)f(em)m(b)s(edded)f(with)g(its) 448 3846 y(v)m(ertices)29 b(on)f(in)m(teger)h(lattice)g(p)s(oin)m(ts)e (if)g(and)h(only)f(if)h Fl(')g Fo(is)g(satis\014able.)38 b(The)28 b(in)m(tuition)448 3958 y(underlying)42 b(the)j(follo)m(wing)e (three)h(lemmas)g(is)g(that)h(w)m(e)g(are)g(building)c(a)k(link)-5 b(age)448 4071 y(gadget)43 b(that)g(will)c(c)m(hec)m(k)k(the)e(truth)g (v)-5 b(alue)41 b(of)h(a)g(clause;)47 b(w)m(e)42 b(will)d(then)i(join)g (the)448 4184 y(gadgets)33 b(together)g(to)f(mo)s(del)e(the)h(3)21 b Fk(\000)g(C)5 b(N)13 b(F)40 b Fo(form)m(ula.)j(W)-8 b(e)32 b(conclude)f(this)f(section)448 4297 y(b)m(y)h(sho)m(wing)e (that)i(the)g(problem)d(is)i Fk(N)13 b(P)7 b(\000)p Fo(complete.)589 4410 y(Let)22 b Fl(')g Fo(b)s(e)e(a)i(3)r Fk(\000)r(C)5 b(N)13 b(F)30 b Fo(form)m(ula)20 b Fl(')26 b Fo(=)f Fl(C)1931 4424 y Fj(1)1972 4410 y Fk(^)d Fl(:)15 b(:)g(:)s Fk(^)r Fl(C)2291 4424 y Fi(r)2349 4410 y Fo(where)21 b(eac)m(h)h Fl(C)2863 4424 y Fi(i)2916 4410 y Fo(=)j Fl(l)3039 4424 y Fi(i)p Fj(1)3104 4410 y Fk(_)r Fl(l)3194 4424 y Fi(i)p Fj(2)3259 4410 y Fk(_)r Fl(l)3349 4424 y Fi(i)p Fj(3)3412 4410 y Fo(,)448 4523 y(and)30 b(the)h Fl(l)809 4537 y Fi(ij)869 4523 y Fo('s)g(are)g(literals.)589 4636 y(W)-8 b(e)41 b(b)s(egin)d(b)m(y)h(building)c(a)40 b(gadget)h Fl(G)1965 4650 y Fi(i)2032 4636 y Fo(for)e(eac)m(h)h(clause)f Fl(C)2735 4650 y Fi(i)2804 4636 y Fo(=)g Fl(l)2941 4650 y Fi(i)p Fj(1)3031 4636 y Fk(_)26 b Fl(l)3145 4650 y Fi(i)p Fj(2)3235 4636 y Fk(_)f Fl(l)3348 4650 y Fi(i)p Fj(3)3412 4636 y Fo(.)448 4749 y(The)37 b(gadget)i Fl(G)1014 4763 y Fi(i)1078 4749 y Fo(consists)e(of)g(t)m(w)m(o)i(parts.)61 b(The)36 b(\014rst)h(part,)i(dra)m(wn)d(on)h(the)g(left)g(in)448 4862 y(Figure)i(2,)k(consists)c(of)g(three)h(connected)g(diamonds.)67 b(The)39 b(line)e(from)i Fl(y)3106 4876 y Fi(i)p Fj(0)3209 4862 y Fo(to)h Fl(y)3374 4876 y Fi(i)p Fj(6)1920 5162 y Fo(5)p eop %%Page: 6 6 6 5 bop 293 531 a 26049577 12827443 1776107 35851059 27825684 48678502 startTexFig 293 531 a %%BeginDocument: idraw/gadget1.ps /arrowHeight 13 def /arrowWidth 6 def /IdrawDict 53 dict def IdrawDict begin /reencodeISO { dup dup findfont dup length dict begin { 1 index /FID ne { def }{ pop pop } ifelse } forall /Encoding ISOLatin1Encoding def currentdict end definefont } def /ISOLatin1Encoding [ /.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef /.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef /.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef /.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef /space/exclam/quotedbl/numbersign/dollar/percent/ampersand/quoteright /parenleft/parenright/asterisk/plus/comma/minus/period/slash /zero/one/two/three/four/five/six/seven/eight/nine/colon/semicolon /less/equal/greater/question/at/A/B/C/D/E/F/G/H/I/J/K/L/M/N /O/P/Q/R/S/T/U/V/W/X/Y/Z/bracketleft/backslash/bracketright /asciicircum/underscore/quoteleft/a/b/c/d/e/f/g/h/i/j/k/l/m /n/o/p/q/r/s/t/u/v/w/x/y/z/braceleft/bar/braceright/asciitilde /.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef /.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef /.notdef/dotlessi/grave/acute/circumflex/tilde/macron/breve /dotaccent/dieresis/.notdef/ring/cedilla/.notdef/hungarumlaut /ogonek/caron/space/exclamdown/cent/sterling/currency/yen/brokenbar /section/dieresis/copyright/ordfeminine/guillemotleft/logicalnot /hyphen/registered/macron/degree/plusminus/twosuperior/threesuperior /acute/mu/paragraph/periodcentered/cedilla/onesuperior/ordmasculine /guillemotright/onequarter/onehalf/threequarters/questiondown /Agrave/Aacute/Acircumflex/Atilde/Adieresis/Aring/AE/Ccedilla /Egrave/Eacute/Ecircumflex/Edieresis/Igrave/Iacute/Icircumflex /Idieresis/Eth/Ntilde/Ograve/Oacute/Ocircumflex/Otilde/Odieresis /multiply/Oslash/Ugrave/Uacute/Ucircumflex/Udieresis/Yacute /Thorn/germandbls/agrave/aacute/acircumflex/atilde/adieresis /aring/ae/ccedilla/egrave/eacute/ecircumflex/edieresis/igrave /iacute/icircumflex/idieresis/eth/ntilde/ograve/oacute/ocircumflex /otilde/odieresis/divide/oslash/ugrave/uacute/ucircumflex/udieresis /yacute/thorn/ydieresis ] def /Helvetica reencodeISO def /Courier reencodeISO def /Courier-Bold reencodeISO def /none null def /numGraphicParameters 17 def /stringLimit 65535 def /Begin { save numGraphicParameters dict begin } def /End { end restore } def /SetB { dup type /nulltype eq { pop false /brushRightArrow idef false /brushLeftArrow idef true /brushNone idef } { /brushDashOffset idef /brushDashArray idef 0 ne /brushRightArrow idef 0 ne /brushLeftArrow idef /brushWidth idef false /brushNone idef } ifelse } def /SetCFg { /fgblue idef /fggreen idef /fgred idef } def /SetCBg { /bgblue idef /bggreen idef /bgred idef } def /SetF { /printSize idef /printFont idef } def /SetP { dup type /nulltype eq { pop true /patternNone idef } { dup -1 eq { /patternGrayLevel idef /patternString idef } { /patternGrayLevel idef } ifelse false /patternNone idef } ifelse } def /BSpl { 0 begin storexyn newpath n 1 gt { 0 0 0 0 0 0 1 1 true subspline n 2 gt { 0 0 0 0 1 1 2 2 false subspline 1 1 n 3 sub { /i exch def i 1 sub dup i dup i 1 add dup i 2 add dup false subspline } for n 3 sub dup n 2 sub dup n 1 sub dup 2 copy false subspline } if n 2 sub dup n 1 sub dup 2 copy 2 copy false subspline patternNone not brushLeftArrow not brushRightArrow not and and { ifill } if brushNone not { istroke } if 0 0 1 1 leftarrow n 2 sub dup n 1 sub dup rightarrow } if end } dup 0 4 dict put def /Circ { newpath 0 360 arc patternNone not { ifill } if brushNone not { istroke } if } def /CBSpl { 0 begin dup 2 gt { storexyn newpath n 1 sub dup 0 0 1 1 2 2 true subspline 1 1 n 3 sub { /i exch def i 1 sub dup i dup i 1 add dup i 2 add dup false subspline } for n 3 sub dup n 2 sub dup n 1 sub dup 0 0 false subspline n 2 sub dup n 1 sub dup 0 0 1 1 false subspline patternNone not { ifill } if brushNone not { istroke } if } { Poly } ifelse end } dup 0 4 dict put def /Elli { 0 begin newpath 4 2 roll translate scale 0 0 1 0 360 arc patternNone not { ifill } if brushNone not { istroke } if end } dup 0 1 dict put def /Line { 0 begin 2 storexyn newpath x 0 get y 0 get moveto x 1 get y 1 get lineto brushNone not { istroke } if 0 0 1 1 leftarrow 0 0 1 1 rightarrow end } dup 0 4 dict put def /MLine { 0 begin storexyn newpath n 1 gt { x 0 get y 0 get moveto 1 1 n 1 sub { /i exch def x i get y i get lineto } for patternNone not brushLeftArrow not brushRightArrow not and and { ifill } if brushNone not { istroke } if 0 0 1 1 leftarrow n 2 sub dup n 1 sub dup rightarrow } if end } dup 0 4 dict put def /Poly { 3 1 roll newpath moveto -1 add { lineto } repeat closepath patternNone not { ifill } if brushNone not { istroke } if } def /Rect { 0 begin /t exch def /r exch def /b exch def /l exch def newpath l b moveto l t lineto r t lineto r b lineto closepath patternNone not { ifill } if brushNone not { istroke } if end } dup 0 4 dict put def /Text { ishow } def /idef { dup where { pop pop pop } { exch def } ifelse } def /ifill { 0 begin gsave patternGrayLevel -1 ne { fgred bgred fgred sub patternGrayLevel mul add fggreen bggreen fggreen sub patternGrayLevel mul add fgblue bgblue fgblue sub patternGrayLevel mul add setrgbcolor eofill } { eoclip originalCTM setmatrix pathbbox /t exch def /r exch def /b exch def /l exch def /w r l sub ceiling cvi def /h t b sub ceiling cvi def /imageByteWidth w 8 div ceiling cvi def /imageHeight h def bgred bggreen bgblue setrgbcolor eofill fgred fggreen fgblue setrgbcolor w 0 gt h 0 gt and { l b translate w h scale w h true [w 0 0 h neg 0 h] { patternproc } imagemask } if } ifelse grestore end } dup 0 8 dict put def /istroke { gsave brushDashOffset -1 eq { [] 0 setdash 1 setgray } { brushDashArray brushDashOffset setdash fgred fggreen fgblue setrgbcolor } ifelse brushWidth setlinewidth originalCTM setmatrix stroke grestore } def /ishow { 0 begin gsave fgred fggreen fgblue setrgbcolor /fontDict printFont printSize scalefont dup setfont def /descender fontDict begin 0 [FontBBox] 1 get FontMatrix end transform exch pop def /vertoffset 1 printSize sub descender sub def { 0 vertoffset moveto show /vertoffset vertoffset printSize sub def } forall grestore end } dup 0 3 dict put def /patternproc { 0 begin /patternByteLength patternString length def /patternHeight patternByteLength 8 mul sqrt cvi def /patternWidth patternHeight def /patternByteWidth patternWidth 8 idiv def /imageByteMaxLength imageByteWidth imageHeight mul stringLimit patternByteWidth sub min def /imageMaxHeight imageByteMaxLength imageByteWidth idiv patternHeight idiv patternHeight mul patternHeight max def /imageHeight imageHeight imageMaxHeight sub store /imageString imageByteWidth imageMaxHeight mul patternByteWidth add string def 0 1 imageMaxHeight 1 sub { /y exch def /patternRow y patternByteWidth mul patternByteLength mod def /patternRowString patternString patternRow patternByteWidth getinterval def /imageRow y imageByteWidth mul def 0 patternByteWidth imageByteWidth 1 sub { /x exch def imageString imageRow x add patternRowString putinterval } for } for imageString end } dup 0 12 dict put def /min { dup 3 2 roll dup 4 3 roll lt { exch } if pop } def /max { dup 3 2 roll dup 4 3 roll gt { exch } if pop } def /midpoint { 0 begin /y1 exch def /x1 exch def /y0 exch def /x0 exch def x0 x1 add 2 div y0 y1 add 2 div end } dup 0 4 dict put def /thirdpoint { 0 begin /y1 exch def /x1 exch def /y0 exch def /x0 exch def x0 2 mul x1 add 3 div y0 2 mul y1 add 3 div end } dup 0 4 dict put def /subspline { 0 begin /movetoNeeded exch def y exch get /y3 exch def x exch get /x3 exch def y exch get /y2 exch def x exch get /x2 exch def y exch get /y1 exch def x exch get /x1 exch def y exch get /y0 exch def x exch get /x0 exch def x1 y1 x2 y2 thirdpoint /p1y exch def /p1x exch def x2 y2 x1 y1 thirdpoint /p2y exch def /p2x exch def x1 y1 x0 y0 thirdpoint p1x p1y midpoint /p0y exch def /p0x exch def x2 y2 x3 y3 thirdpoint p2x p2y midpoint /p3y exch def /p3x exch def movetoNeeded { p0x p0y moveto } if p1x p1y p2x p2y p3x p3y curveto end } dup 0 17 dict put def /storexyn { /n exch def /y n array def /x n array def n 1 sub -1 0 { /i exch def y i 3 2 roll put x i 3 2 roll put } for } def /SSten { fgred fggreen fgblue setrgbcolor dup true exch 1 0 0 -1 0 6 -1 roll matrix astore } def /FSten { dup 3 -1 roll dup 4 1 roll exch newpath 0 0 moveto dup 0 exch lineto exch dup 3 1 roll exch lineto 0 lineto closepath bgred bggreen bgblue setrgbcolor eofill SSten } def /Rast { exch dup 3 1 roll 1 0 0 -1 0 6 -1 roll matrix astore } def /arrowhead { 0 begin transform originalCTM itransform /taily exch def /tailx exch def transform originalCTM itransform /tipy exch def /tipx exch def /dy tipy taily sub def /dx tipx tailx sub def /angle dx 0 ne dy 0 ne or { dy dx atan } { 90 } ifelse def gsave originalCTM setmatrix tipx tipy translate angle rotate newpath arrowHeight neg arrowWidth 2 div moveto 0 0 lineto arrowHeight neg arrowWidth 2 div neg lineto patternNone not { originalCTM setmatrix /padtip arrowHeight 2 exp 0.25 arrowWidth 2 exp mul add sqrt brushWidth mul arrowWidth div def /padtail brushWidth 2 div def tipx tipy translate angle rotate padtip 0 translate arrowHeight padtip add padtail add arrowHeight div dup scale arrowheadpath ifill } if brushNone not { originalCTM setmatrix tipx tipy translate angle rotate arrowheadpath istroke } if grestore end } dup 0 9 dict put def /arrowheadpath { newpath arrowHeight neg arrowWidth 2 div moveto 0 0 lineto arrowHeight neg arrowWidth 2 div neg lineto } def /leftarrow { 0 begin y exch get /taily exch def x exch get /tailx exch def y exch get /tipy exch def x exch get /tipx exch def brushLeftArrow { tipx tipy tailx taily arrowhead } if end } dup 0 4 dict put def /rightarrow { 0 begin y exch get /tipy exch def x exch get /tipx exch def y exch get /taily exch def x exch get /tailx exch def brushRightArrow { tipx tipy tailx taily arrowhead } if end } dup 0 4 dict put def %I Idraw 10 Grid 45.7532 45.7532 Begin %I b u %I cfg u %I cbg u %I f u %I p u %I t [ 0.619552 0 0 0.619552 0 0 ] concat /originalCTM matrix currentmatrix def Begin %I Elli %I b 65535 0 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 0 SetP %I t [ 1 0 0 1 3.00001 188 ] concat %I 70 938 3 3 Elli End Begin %I Elli %I b 65535 0 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 0 SetP %I t [ 1 0 0 1 95 188 ] concat %I 70 938 3 3 Elli End Begin %I Poly %I b 65535 0 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 1 SetP %I t [ 1 0 0 1 1.14441e-05 236 ] concat %I 3 74 891 162 891 118 846 3 Poly End Begin %I Poly %I b 65535 0 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 1 SetP %I t [ 1 0 0 1 1.14441e-05 236 ] concat %I 3 74 800 163 800 118 752 3 Poly End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-helvetica-medium-r-*-120-* Helvetica 12 SetF %I t [ 1 0 0 1 179 1148 ] concat %I [ (_) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 59 1129 ] concat %I [ (1) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 291 1151 ] concat %I [ (1) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 291 966 ] concat %I [ (2) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 186 1034 ] concat %I [ (2) ] Text End Begin %I Poly %I b 65535 0 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 1 SetP %I t [ 1 0 0 1 1.14441e-05 236 ] concat %I 3 74 890 118 937 165 890 3 Poly End Begin %I Poly %I b 65535 0 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 1 SetP %I t [ 1 0 0 1 1.14441e-05 236 ] concat %I 3 74 800 119 847 164 800 3 Poly End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-helvetica-medium-r-*-120-* Helvetica 12 SetF %I t [ 1 0 0 1 647 1152 ] concat %I [ (M) ] Text End Begin %I Elli %I b 65535 0 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 0 SetP %I t [ 1 0 0 1 200 212 ] concat %I 70 938 3 3 Elli End Begin %I Elli %I b 65535 2 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 0 SetP %I t [ 1 0 0 1 200 168 ] concat %I 70 938 3 3 Elli End Begin %I Elli %I b 65535 2 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 0 SetP %I t [ 1 0 0 1 201 123 ] concat %I 70 938 3 3 Elli End Begin %I Elli %I b 65535 2 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 0 SetP %I t [ 1 0 0 1 200 77 ] concat %I 70 938 3 3 Elli End Begin %I Elli %I b 65535 2 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 0 SetP %I t [ 1 0 0 1 200 33 ] concat %I 70 938 3 3 Elli End Begin %I Line %I b 65535 2 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 0 0 1 -120 352 ] concat %I 391 796 391 614 Line %I 1 End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-bold-r-*-120-* Courier-Bold 12 SetF %I t [ 1 0 0 1 90 1185 ] concat %I [ (y) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-bold-r-*-120-* Courier-Bold 12 SetF %I t [ 1 0 0 1 91 1089 ] concat %I [ (y) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-bold-r-*-120-* Courier-Bold 12 SetF %I t [ 1 0 0 1 93 998 ] concat %I [ (y) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 103 1179 ] concat %I [ (0) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 101 1082 ] concat %I [ (2) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 104 988 ] concat %I [ (4) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-bold-r-*-120-* Courier-Bold 12 SetF %I t [ 1 0 0 1 98 1057 ] concat %I [ (y) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 109 1051 ] concat %I [ (3) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-helvetica-medium-r-*-120-* Helvetica 12 SetF %I t [ 1 0 0 1 48 1049 ] concat %I [ (_) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 60 1026 ] concat %I [ (2) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-bold-r-*-120-* Courier-Bold 12 SetF %I t [ 1 0 0 1 93 904 ] concat %I [ (y) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 105 894 ] concat %I [ (6) ] Text End Begin %I Line %I b 65535 0 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 0 0 1 -43 372 ] concat %I 163 616 207 570 Line %I 1 End Begin %I Line %I b 65535 0 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 0 0 1 -43 372 ] concat %I 207 570 161 524 Line %I 1 End Begin %I Line %I b 65535 0 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 0 0 1 -43 372 ] concat %I 161 524 117 570 Line %I 1 End Begin %I Line %I b 65535 0 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 0 0 1 -43 372 ] concat %I 117 570 161 619 Line %I 1 End Begin %I Line %I b 65535 0 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 0 0 1 -43 372 ] concat %I 117 570 208 570 Line %I 1 End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 182 944 ] concat %I [ (3) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 63.0001 944 ] concat %I [ (3) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-bold-r-*-120-* Courier-Bold 12 SetF %I t [ 1 0 0 1 169 963 ] concat %I [ (_) ] Text End Begin %I Elli %I b 65535 0 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 0 SetP %I t [ 1 0 0 1 93 3.0002 ] concat %I 70 938 3 3 Elli End Begin %I Elli %I b 65535 0 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 0 SetP %I t [ 1 0 0 1 5.00011 5.0002 ] concat %I 70 938 3 3 Elli End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-bold-r-*-120-* Courier-Bold 12 SetF %I t [ 1 0 0 1 100 959 ] concat %I [ (y) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 112 953 ] concat %I [ (5) ] Text End Begin %I Line %I b 65535 1 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 0 0 1 -43 372 ] concat %I 161 800 162 524 Line %I 1 End Begin %I Elli %I b 65535 0 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 0 SetP %I t [ 1 0 0 1 47.0001 232 ] concat %I 70 938 3 3 Elli End Begin %I Elli %I b 65535 0 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 0 SetP %I t [ 1 0 0 1 48.0001 145 ] concat %I 70 938 3 3 Elli End Begin %I Elli %I b 65535 0 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 0 SetP %I t [ 1 0 0 1 48.0001 52.0002 ] concat %I 70 938 3 3 Elli End Begin %I Elli %I b 65535 0 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 0 SetP %I t [ 1 0 0 1 49.0001 -42 ] concat %I 70 938 3 3 Elli End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 190 1127 ] concat %I [ (1) ] Text End Begin %I Elli %I b 65535 0 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 0 SetP %I t [ 1 0 0 1 92 99.0001 ] concat %I 70 938 3 3 Elli End Begin %I Elli %I b 65535 0 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 0 SetP %I t [ 1 0 0 1 5.00011 99.0001 ] concat %I 70 938 3 3 Elli End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-helvetica-medium-r-*-120-* Helvetica 12 SetF %I t [ 1 0 0 1 177 1042 ] concat %I [ (l) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-helvetica-medium-r-*-120-* Helvetica 12 SetF %I t [ 1 0 0 1 50.0001 1034 ] concat %I [ (l) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-helvetica-medium-r-*-120-* Helvetica 12 SetF %I t [ 1 0 0 1 171 950 ] concat %I [ (l) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-helvetica-medium-r-*-120-* Helvetica 12 SetF %I t [ 1 0 0 1 49.0001 1137 ] concat %I [ (l) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-helvetica-medium-r-*-120-* Helvetica 12 SetF %I t [ 1 0 0 1 53.0001 949 ] concat %I [ (l) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-helvetica-medium-r-*-120-* Helvetica 12 SetF %I t [ 1 0 0 1 181 1134 ] concat %I [ (l) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-helvetica-medium-r-*-120-* Helvetica 12 SetF %I t [ 1 0 0 1 279 975 ] concat %I [ (l) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-helvetica-medium-r-*-120-* Helvetica 12 SetF %I t [ 1 0 0 1 279 1158 ] concat %I [ (l) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 57.0003 944 ] concat %I [ (i) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 175 944 ] concat %I [ (i) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 180 1035 ] concat %I [ (i) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 284 1151 ] concat %I [ (i) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 284 967 ] concat %I [ (i) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 657 1147 ] concat %I [ (i) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 53.0003 1026 ] concat %I [ (i) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 185 1127 ] concat %I [ (i) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 52.0003 1129 ] concat %I [ (i) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-bold-r-*-120-* Courier-Bold 12 SetF %I t [ 1 0 0 1 122 1154 ] concat %I [ (2) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-bold-r-*-120-* Courier-Bold 12 SetF %I t [ 1 0 0 1 128 1122 ] concat %I [ (2) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-bold-r-*-120-* Courier-Bold 12 SetF %I t [ 1 0 0 1 121 1068 ] concat %I [ (2) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-bold-r-*-120-* Courier-Bold 12 SetF %I t [ 1 0 0 1 132 1032 ] concat %I [ (2) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-bold-r-*-120-* Courier-Bold 12 SetF %I t [ 1 0 0 1 122 976 ] concat %I [ (2) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-bold-r-*-120-* Courier-Bold 12 SetF %I t [ 1 0 0 1 135 938 ] concat %I [ (2) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-bold-r-*-120-* Courier-Bold 12 SetF %I t [ 1 0 0 1 260 998 ] concat %I [ (1) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-bold-r-*-120-* Courier-Bold 12 SetF %I t [ 1 0 0 1 258 1042 ] concat %I [ (1) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-bold-r-*-120-* Courier-Bold 12 SetF %I t [ 1 0 0 1 259 1088 ] concat %I [ (1) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-bold-r-*-120-* Courier-Bold 12 SetF %I t [ 1 0 0 1 260 1132 ] concat %I [ (1) ] Text End Begin %I Poly %I b 65535 0 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 1 SetP %I t [ 1 0 0 1 488 240 ] concat %I 3 74 891 162 891 118 846 3 Poly End Begin %I Poly %I b 65535 0 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 1 SetP %I t [ 1 0 0 1 488 240 ] concat %I 3 74 800 163 800 118 752 3 Poly End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-helvetica-medium-r-*-120-* Helvetica 12 SetF %I t [ 1 0 0 1 657 1138 ] concat %I [ (_) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 547 1134 ] concat %I [ (1) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 674 1038 ] concat %I [ (2) ] Text End Begin %I Poly %I b 65535 0 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 1 SetP %I t [ 1 0 0 1 488 240 ] concat %I 3 74 890 118 937 165 890 3 Poly End Begin %I Poly %I b 65535 0 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 1 SetP %I t [ 1 0 0 1 488 240 ] concat %I 3 74 800 119 847 164 800 3 Poly End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-bold-r-*-120-* Courier-Bold 12 SetF %I t [ 1 0 0 1 579 1189 ] concat %I [ (y) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-bold-r-*-120-* Courier-Bold 12 SetF %I t [ 1 0 0 1 579 1093 ] concat %I [ (y) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-bold-r-*-120-* Courier-Bold 12 SetF %I t [ 1 0 0 1 580 1001 ] concat %I [ (y) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 593 1182 ] concat %I [ (0) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 590 1085 ] concat %I [ (2) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 592 992 ] concat %I [ (4) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-bold-r-*-120-* Courier-Bold 12 SetF %I t [ 1 0 0 1 586 1058 ] concat %I [ (y) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 597 1051 ] concat %I [ (3) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-helvetica-medium-r-*-120-* Helvetica 12 SetF %I t [ 1 0 0 1 536 1053 ] concat %I [ (_) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 551 1030 ] concat %I [ (2) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-bold-r-*-120-* Courier-Bold 12 SetF %I t [ 1 0 0 1 583 906 ] concat %I [ (y) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 594 897 ] concat %I [ (6) ] Text End Begin %I Line %I b 65535 0 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 0 0 1 445 376 ] concat %I 163 616 207 570 Line %I 1 End Begin %I Line %I b 65535 0 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 0 0 1 445 376 ] concat %I 207 570 161 524 Line %I 1 End Begin %I Line %I b 65535 0 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 0 0 1 445 376 ] concat %I 161 524 117 570 Line %I 1 End Begin %I Line %I b 65535 0 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 0 0 1 445 376 ] concat %I 117 570 161 619 Line %I 1 End Begin %I Line %I b 65535 0 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 0 0 1 445 376 ] concat %I 117 570 208 570 Line %I 1 End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 669 948 ] concat %I [ (3) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 550 945 ] concat %I [ (3) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-bold-r-*-120-* Courier-Bold 12 SetF %I t [ 1 0 0 1 538 966 ] concat %I [ (_) ] Text End Begin %I Elli %I b 65535 0 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 0 SetP %I t [ 1 0 0 1 581 7.0002 ] concat %I 70 938 3 3 Elli End Begin %I Elli %I b 65535 0 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 0 SetP %I t [ 1 0 0 1 493 9.0002 ] concat %I 70 938 3 3 Elli End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-bold-r-*-120-* Courier-Bold 12 SetF %I t [ 1 0 0 1 589 965 ] concat %I [ (y) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 599 957 ] concat %I [ (5) ] Text End Begin %I Line %I b 65535 1 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 0 0 1 445 376 ] concat %I 161 800 162 524 Line %I 1 End Begin %I Elli %I b 65535 0 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 0 SetP %I t [ 1 0 0 1 535 236 ] concat %I 70 938 3 3 Elli End Begin %I Elli %I b 65535 0 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 0 SetP %I t [ 1 0 0 1 536 149 ] concat %I 70 938 3 3 Elli End Begin %I Elli %I b 65535 0 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 0 SetP %I t [ 1 0 0 1 536 56.0002 ] concat %I 70 938 3 3 Elli End Begin %I Elli %I b 65535 0 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 0 SetP %I t [ 1 0 0 1 537 -38 ] concat %I 70 938 3 3 Elli End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 668 1120 ] concat %I [ (1) ] Text End Begin %I Elli %I b 65535 0 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 0 SetP %I t [ 1 0 0 1 580 103 ] concat %I 70 938 3 3 Elli End Begin %I Elli %I b 65535 0 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 0 SetP %I t [ 1 0 0 1 493 103 ] concat %I 70 938 3 3 Elli End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-helvetica-medium-r-*-120-* Helvetica 12 SetF %I t [ 1 0 0 1 665 1046 ] concat %I [ (l) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-helvetica-medium-r-*-120-* Helvetica 12 SetF %I t [ 1 0 0 1 538 1038 ] concat %I [ (l) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-helvetica-medium-r-*-120-* Helvetica 12 SetF %I t [ 1 0 0 1 659 954 ] concat %I [ (l) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-helvetica-medium-r-*-120-* Helvetica 12 SetF %I t [ 1 0 0 1 537 1141 ] concat %I [ (l) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-helvetica-medium-r-*-120-* Helvetica 12 SetF %I t [ 1 0 0 1 540 951 ] concat %I [ (l) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-helvetica-medium-r-*-120-* Helvetica 12 SetF %I t [ 1 0 0 1 659 1125 ] concat %I [ (l) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 543 946 ] concat %I [ (i) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 662 948 ] concat %I [ (i) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 668 1039 ] concat %I [ (i) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 543 1031 ] concat %I [ (i) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 662 1120 ] concat %I [ (i) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 541 1134 ] concat %I [ (i) ] Text End Begin %I Line %I b 65535 3 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 0 0 1 31.0001 330 ] concat %I 619 799 619 711 Line %I 1 End Begin %I Line %I b 65535 3 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 0 0 1 34.0001 330 ] concat %I 528 801 622 801 Line %I 1 End Begin %I Elli %I b 65535 0 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 0 SetP %I t [ 1 0 0 1 493 193 ] concat %I 70 938 3 3 Elli End Begin %I Elli %I b 65535 0 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 0 SetP %I t [ 1 0 0 1 535 193 ] concat %I 70 938 3 3 Elli End Begin %I Elli %I b 65535 0 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 0 SetP %I t [ 1 0 0 1 580 193 ] concat %I 70 938 3 3 Elli End Begin %I Elli %I b 65535 0 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 0 SetP %I t [ 1 0 0 1 580 147 ] concat %I 70 938 3 3 Elli End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-helvetica-medium-r-*-120-* Helvetica 12 SetF %I t [ 1 0 0 1 281 1071 ] concat %I [ (M) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 292 1064 ] concat %I [ (i) ] Text End Begin %I Elli %I b 65535 0 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 0 SetP %I t [ 1 0 0 1 48.0001 189 ] concat %I 70 938 3 3 Elli End Begin %I Elli %I b 65535 0 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 0 SetP %I t [ 1 0 0 1 49.0001 98 ] concat %I 70 938 3 3 Elli End Begin %I Elli %I b 65535 0 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 0 SetP %I t [ 1 0 0 1 49.0001 3 ] concat %I 70 938 3 3 Elli End Begin %I Elli %I b 65535 0 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 0 SetP %I t [ 1 0 0 1 536 103 ] concat %I 70 938 3 3 Elli End Begin %I Elli %I b 65535 0 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 0 SetP %I t [ 1 0 0 1 537 8 ] concat %I 70 938 3 3 Elli End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-bold-r-*-120-* Courier-Bold 12 SetF %I t [ 1 0 0 1 585 1149 ] concat %I [ (y) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-bold-r-*-120-* Courier-Bold 12 SetF %I t [ 1 0 0 1 97 1144 ] concat %I [ (y) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 597 1144 ] concat %I [ (1) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 109 1139 ] concat %I [ (1) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 96.0003 1082 ] concat %I [ (i) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 103 1052 ] concat %I [ (i) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 98.0003 988 ] concat %I [ (i) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 106 954 ] concat %I [ (i) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 97.0003 895 ] concat %I [ (i) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 103 1140 ] concat %I [ (i) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 96.0003 1180 ] concat %I [ (i) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 592 1143 ] concat %I [ (i) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 584 1085 ] concat %I [ (i) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 591 1051 ] concat %I [ (i) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 585 992 ] concat %I [ (i) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 593 957 ] concat %I [ (i) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 586 1182 ] concat %I [ (i) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 588 898 ] concat %I [ (i) ] Text End End %I eop showpage end %%EndDocument endTexFig 448 2352 a Fo(Figure)35 b(2:)52 b(Gadget)37 b Fl(G)1258 2366 y Fi(i)1285 2352 y Fo(,)g(on)f(the)f(righ)m(t,)i(consists)e(of)h (the)f(com)m(bination)g(of)h(the)g(t)m(w)m(o)448 2465 y(gadgets)c(on)e(the)h(left,)f(where)g(p)s(oin)m(ts)f(with)g(the)i (same)g(lab)s(el)e(are)h(co-inciden)m(t.)448 2740 y(is)38 b(a)i(straigh)m(t)f(line)f(of)h(length)f(6.)68 b(The)38 b(second)h(part)g(of)g(the)h(gadget)g(is)e(a)i(link)-5 b(age)448 2853 y(connecting)45 b Fl(l)944 2867 y Fi(i)p Fj(1)1052 2853 y Fo(with)e Fl(l)1300 2867 y Fi(i)p Fj(2)1363 2853 y Fo(.)83 b(The)43 b(length)h(of)h(the)f(diagonals)g(of)g(the)g (diamonds)f(is)448 2966 y(2.)53 b(The)34 b(link)-5 b(age)34 b(connecting)g Fl(l)1557 2980 y Fi(i)p Fj(1)1655 2966 y Fo(and)g Fl(l)1863 2980 y Fi(i)p Fj(2)1961 2966 y Fo(consists)g(of)g (four)g(line)f(segmen)m(ts)i(of)f(unit)448 3079 y(length.)47 b(Its)32 b(midp)s(oin)m(t)e(is)i(lab)s(elled)e Fl(M)1815 3093 y Fi(i)1843 3079 y Fo(.)47 b(Without)32 b(loss)g(of)g(generalit)m (y)-8 b(,)34 b(the)f(link)-5 b(age)448 3192 y(can)25 b(b)s(e)e(arranged)h(so)g(that)h(the)f(v)m(ertices)h Fl(y)1913 3206 y Fi(ij)1997 3192 y Fo(are)g(on)f(the)g Fl(y)s Fk(\000)p Fo(axis.)38 b(A)24 b(useful)e(in)m(tuition)448 3305 y(is)33 b(that)h(placing)f Fl(l)1087 3319 y Fi(ij)1181 3305 y Fo(on)h(the)g(line)e Fl(x)f Fo(=)g(1)j(is)f(assigning)f Fl(l)2425 3319 y Fi(ij)2519 3305 y Fo(the)i(v)-5 b(alue)33 b(\\true,")j(while)448 3418 y(placing)29 b Fl(l)788 3432 y Fi(ij)879 3418 y Fo(on)i(the)f(line)f Fl(x)c Fo(=)g Fk(\000)p Fo(1)31 b(is)e(assigning)g Fl(l)2162 3432 y Fi(ij)2253 3418 y Fo(the)h(v)-5 b(alue)30 b(\\false.")589 3531 y(This)35 b(link)f(can)j(b)s(e)f(folded)f(in)g(v)-5 b(arious)35 b(w)m(a)m(ys.)60 b(The)36 b(gadget)i(is)d(constructed)i(so) 448 3644 y(that)31 b(if)f Fl(G)801 3658 y Fi(i)858 3644 y Fo(is)g(placed)g(with)f(v)m(ertices)i Fl(y)1814 3658 y Fi(ij)1904 3644 y Fo(on)f(the)h Fl(y)s Fk(\000)p Fo(axis,)e(then)h (the)h(v)m(ertex)g Fl(M)3242 3658 y Fi(i)3301 3644 y Fo(can)448 3756 y(b)s(e)f(on)g(the)h(line)e Fl(x)c Fo(=)g(1)31 b(if)e(and)h(only)f(if)g Fl(l)1845 3770 y Fi(i)p Fj(1)1939 3756 y Fo(or)i Fl(l)2078 3770 y Fi(i)p Fj(2)2172 3756 y Fo(lies)e(on)h(the)h(line)d Fl(x)d Fo(=)g(1.)589 3869 y(Th)m(us)k Fl(G)891 3883 y Fi(i)949 3869 y Fo(is)f(almost)i(an)g(or)g (gate)h(in)d(that)j(its)e(\\output")h Fl(M)2669 3883 y Fi(i)2727 3869 y Fo(can)g(lie)f(on)h(the)g(line)448 3982 y Fl(x)g Fo(=)f(1)34 b(i\013)e(at)i(least)f(one)g(of)h Fl(l)1452 3996 y Fi(i)p Fj(1)1548 3982 y Fo(or)f Fl(l)1689 3996 y Fi(i)p Fj(2)1786 3982 y Fo(lies)e(on)i(the)g(line)f Fl(x)d Fo(=)h(1.)49 b(It)33 b(is)f(con)m(v)m(enien)m(t)i(to)448 4095 y(force)c(the)g(output)f(of)h(this)e(\\or")i(gate)h(to)f(ha)m(v)m (e)h(a)f(\014xed)e Fl(y)s Fk(\000)p Fo(co)s(ordinate.)40 b(W)-8 b(e)31 b(do)e(this)448 4208 y(b)m(y)37 b(extending)e Fl(G)1075 4222 y Fi(i)1139 4208 y Fo(to)i Fl(H)1332 4222 y Fi(i)1396 4208 y Fo(whose)f(output)g Fl(P)2032 4222 y Fi(i)2097 4208 y Fo(has)g(the)h(same)g Fl(x)f Fo(co)s(ordinate)g(as)h Fl(M)3409 4222 y Fi(i)448 4321 y Fo(but)30 b(whose)g Fl(y)s Fk(\000)p Fo(co)s(ordinate)g(is)f(\014xed.)589 4434 y(The)44 b(gadget)i Fl(H)1173 4448 y Fi(i)1245 4434 y Fo(is)d(a)i(com)m(bination)e(of)i Fl(G)2161 4448 y Fi(i)2232 4434 y Fo(with)e(a)i(\\ladder.")82 b(The)43 b(ladder)448 4547 y(connects)29 b(the)g(v)m(ertices)g Fl(y)1342 4561 y Fi(ij)1430 4547 y Fo(with)e(the)h(v)m(ertex)h Fl(M)2150 4561 y Fi(i)2207 4547 y Fo(and)e(a)i(new)f(v)m(ertex)h Fl(P)2971 4561 y Fi(i)3000 4547 y Fo(.)40 b(The)27 b(sides)448 4660 y(of)36 b(the)g(ladder)f(are)h(1,)h(the)f(diagonals)f(are)h (length)2275 4585 y Fk(p)p 2350 4585 46 4 v 2350 4660 a Fo(2)q(.)57 b(If)35 b Fl(H)2650 4674 y Fi(i)2713 4660 y Fo(is)g(placed)g(with)g(the)448 4773 y Fl(y)493 4787 y Fi(ij)586 4773 y Fo(v)m(ertices)f(on)e(the)h Fl(y)s Fk(\000)p Fo(axis,)g(then)f Fl(M)1834 4787 y Fi(i)1896 4773 y Fo(and)g Fl(P)2133 4787 y Fi(i)2194 4773 y Fo(are)h(connected)h (in)d(suc)m(h)i(a)g(w)m(a)m(y)h(as)448 4886 y(to)f(ensure)f(that)h (they)g(ha)m(v)m(e)g(a)g(common)g Fl(x)p Fk(\000)p Fo(v)-5 b(alue.)46 b(Th)m(us)31 b Fl(P)2597 4900 y Fi(i)2658 4886 y Fo(is)g(on)h(the)h(line)e Fl(x)d Fo(=)h(1)1920 5162 y(6)p eop %%Page: 7 7 7 6 bop 1672 531 a 4275815 7104430 7959592 41508290 12235407 48612720 startTexFig 1672 531 a %%BeginDocument: idraw/gadget2.ps /arrowHeight 13 def /arrowWidth 6 def /IdrawDict 53 dict def IdrawDict begin /reencodeISO { dup dup findfont dup length dict begin { 1 index /FID ne { def }{ pop pop } ifelse } forall /Encoding ISOLatin1Encoding def currentdict end definefont } def /ISOLatin1Encoding [ /.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef /.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef /.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef /.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef /space/exclam/quotedbl/numbersign/dollar/percent/ampersand/quoteright /parenleft/parenright/asterisk/plus/comma/minus/period/slash /zero/one/two/three/four/five/six/seven/eight/nine/colon/semicolon /less/equal/greater/question/at/A/B/C/D/E/F/G/H/I/J/K/L/M/N /O/P/Q/R/S/T/U/V/W/X/Y/Z/bracketleft/backslash/bracketright /asciicircum/underscore/quoteleft/a/b/c/d/e/f/g/h/i/j/k/l/m /n/o/p/q/r/s/t/u/v/w/x/y/z/braceleft/bar/braceright/asciitilde /.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef /.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef /.notdef/dotlessi/grave/acute/circumflex/tilde/macron/breve /dotaccent/dieresis/.notdef/ring/cedilla/.notdef/hungarumlaut /ogonek/caron/space/exclamdown/cent/sterling/currency/yen/brokenbar /section/dieresis/copyright/ordfeminine/guillemotleft/logicalnot /hyphen/registered/macron/degree/plusminus/twosuperior/threesuperior /acute/mu/paragraph/periodcentered/cedilla/onesuperior/ordmasculine /guillemotright/onequarter/onehalf/threequarters/questiondown /Agrave/Aacute/Acircumflex/Atilde/Adieresis/Aring/AE/Ccedilla /Egrave/Eacute/Ecircumflex/Edieresis/Igrave/Iacute/Icircumflex /Idieresis/Eth/Ntilde/Ograve/Oacute/Ocircumflex/Otilde/Odieresis /multiply/Oslash/Ugrave/Uacute/Ucircumflex/Udieresis/Yacute /Thorn/germandbls/agrave/aacute/acircumflex/atilde/adieresis /aring/ae/ccedilla/egrave/eacute/ecircumflex/edieresis/igrave /iacute/icircumflex/idieresis/eth/ntilde/ograve/oacute/ocircumflex /otilde/odieresis/divide/oslash/ugrave/uacute/ucircumflex/udieresis /yacute/thorn/ydieresis ] def /Helvetica reencodeISO def /Courier-Bold reencodeISO def /Courier reencodeISO def /none null def /numGraphicParameters 17 def /stringLimit 65535 def /Begin { save numGraphicParameters dict begin } def /End { end restore } def /SetB { dup type /nulltype eq { pop false /brushRightArrow idef false /brushLeftArrow idef true /brushNone idef } { /brushDashOffset idef /brushDashArray idef 0 ne /brushRightArrow idef 0 ne /brushLeftArrow idef /brushWidth idef false /brushNone idef } ifelse } def /SetCFg { /fgblue idef /fggreen idef /fgred idef } def /SetCBg { /bgblue idef /bggreen idef /bgred idef } def /SetF { /printSize idef /printFont idef } def /SetP { dup type /nulltype eq { pop true /patternNone idef } { dup -1 eq { /patternGrayLevel idef /patternString idef } { /patternGrayLevel idef } ifelse false /patternNone idef } ifelse } def /BSpl { 0 begin storexyn newpath n 1 gt { 0 0 0 0 0 0 1 1 true subspline n 2 gt { 0 0 0 0 1 1 2 2 false subspline 1 1 n 3 sub { /i exch def i 1 sub dup i dup i 1 add dup i 2 add dup false subspline } for n 3 sub dup n 2 sub dup n 1 sub dup 2 copy false subspline } if n 2 sub dup n 1 sub dup 2 copy 2 copy false subspline patternNone not brushLeftArrow not brushRightArrow not and and { ifill } if brushNone not { istroke } if 0 0 1 1 leftarrow n 2 sub dup n 1 sub dup rightarrow } if end } dup 0 4 dict put def /Circ { newpath 0 360 arc patternNone not { ifill } if brushNone not { istroke } if } def /CBSpl { 0 begin dup 2 gt { storexyn newpath n 1 sub dup 0 0 1 1 2 2 true subspline 1 1 n 3 sub { /i exch def i 1 sub dup i dup i 1 add dup i 2 add dup false subspline } for n 3 sub dup n 2 sub dup n 1 sub dup 0 0 false subspline n 2 sub dup n 1 sub dup 0 0 1 1 false subspline patternNone not { ifill } if brushNone not { istroke } if } { Poly } ifelse end } dup 0 4 dict put def /Elli { 0 begin newpath 4 2 roll translate scale 0 0 1 0 360 arc patternNone not { ifill } if brushNone not { istroke } if end } dup 0 1 dict put def /Line { 0 begin 2 storexyn newpath x 0 get y 0 get moveto x 1 get y 1 get lineto brushNone not { istroke } if 0 0 1 1 leftarrow 0 0 1 1 rightarrow end } dup 0 4 dict put def /MLine { 0 begin storexyn newpath n 1 gt { x 0 get y 0 get moveto 1 1 n 1 sub { /i exch def x i get y i get lineto } for patternNone not brushLeftArrow not brushRightArrow not and and { ifill } if brushNone not { istroke } if 0 0 1 1 leftarrow n 2 sub dup n 1 sub dup rightarrow } if end } dup 0 4 dict put def /Poly { 3 1 roll newpath moveto -1 add { lineto } repeat closepath patternNone not { ifill } if brushNone not { istroke } if } def /Rect { 0 begin /t exch def /r exch def /b exch def /l exch def newpath l b moveto l t lineto r t lineto r b lineto closepath patternNone not { ifill } if brushNone not { istroke } if end } dup 0 4 dict put def /Text { ishow } def /idef { dup where { pop pop pop } { exch def } ifelse } def /ifill { 0 begin gsave patternGrayLevel -1 ne { fgred bgred fgred sub patternGrayLevel mul add fggreen bggreen fggreen sub patternGrayLevel mul add fgblue bgblue fgblue sub patternGrayLevel mul add setrgbcolor eofill } { eoclip originalCTM setmatrix pathbbox /t exch def /r exch def /b exch def /l exch def /w r l sub ceiling cvi def /h t b sub ceiling cvi def /imageByteWidth w 8 div ceiling cvi def /imageHeight h def bgred bggreen bgblue setrgbcolor eofill fgred fggreen fgblue setrgbcolor w 0 gt h 0 gt and { l b translate w h scale w h true [w 0 0 h neg 0 h] { patternproc } imagemask } if } ifelse grestore end } dup 0 8 dict put def /istroke { gsave brushDashOffset -1 eq { [] 0 setdash 1 setgray } { brushDashArray brushDashOffset setdash fgred fggreen fgblue setrgbcolor } ifelse brushWidth setlinewidth originalCTM setmatrix stroke grestore } def /ishow { 0 begin gsave fgred fggreen fgblue setrgbcolor /fontDict printFont printSize scalefont dup setfont def /descender fontDict begin 0 [FontBBox] 1 get FontMatrix end transform exch pop def /vertoffset 1 printSize sub descender sub def { 0 vertoffset moveto show /vertoffset vertoffset printSize sub def } forall grestore end } dup 0 3 dict put def /patternproc { 0 begin /patternByteLength patternString length def /patternHeight patternByteLength 8 mul sqrt cvi def /patternWidth patternHeight def /patternByteWidth patternWidth 8 idiv def /imageByteMaxLength imageByteWidth imageHeight mul stringLimit patternByteWidth sub min def /imageMaxHeight imageByteMaxLength imageByteWidth idiv patternHeight idiv patternHeight mul patternHeight max def /imageHeight imageHeight imageMaxHeight sub store /imageString imageByteWidth imageMaxHeight mul patternByteWidth add string def 0 1 imageMaxHeight 1 sub { /y exch def /patternRow y patternByteWidth mul patternByteLength mod def /patternRowString patternString patternRow patternByteWidth getinterval def /imageRow y imageByteWidth mul def 0 patternByteWidth imageByteWidth 1 sub { /x exch def imageString imageRow x add patternRowString putinterval } for } for imageString end } dup 0 12 dict put def /min { dup 3 2 roll dup 4 3 roll lt { exch } if pop } def /max { dup 3 2 roll dup 4 3 roll gt { exch } if pop } def /midpoint { 0 begin /y1 exch def /x1 exch def /y0 exch def /x0 exch def x0 x1 add 2 div y0 y1 add 2 div end } dup 0 4 dict put def /thirdpoint { 0 begin /y1 exch def /x1 exch def /y0 exch def /x0 exch def x0 2 mul x1 add 3 div y0 2 mul y1 add 3 div end } dup 0 4 dict put def /subspline { 0 begin /movetoNeeded exch def y exch get /y3 exch def x exch get /x3 exch def y exch get /y2 exch def x exch get /x2 exch def y exch get /y1 exch def x exch get /x1 exch def y exch get /y0 exch def x exch get /x0 exch def x1 y1 x2 y2 thirdpoint /p1y exch def /p1x exch def x2 y2 x1 y1 thirdpoint /p2y exch def /p2x exch def x1 y1 x0 y0 thirdpoint p1x p1y midpoint /p0y exch def /p0x exch def x2 y2 x3 y3 thirdpoint p2x p2y midpoint /p3y exch def /p3x exch def movetoNeeded { p0x p0y moveto } if p1x p1y p2x p2y p3x p3y curveto end } dup 0 17 dict put def /storexyn { /n exch def /y n array def /x n array def n 1 sub -1 0 { /i exch def y i 3 2 roll put x i 3 2 roll put } for } def /SSten { fgred fggreen fgblue setrgbcolor dup true exch 1 0 0 -1 0 6 -1 roll matrix astore } def /FSten { dup 3 -1 roll dup 4 1 roll exch newpath 0 0 moveto dup 0 exch lineto exch dup 3 1 roll exch lineto 0 lineto closepath bgred bggreen bgblue setrgbcolor eofill SSten } def /Rast { exch dup 3 1 roll 1 0 0 -1 0 6 -1 roll matrix astore } def /arrowhead { 0 begin transform originalCTM itransform /taily exch def /tailx exch def transform originalCTM itransform /tipy exch def /tipx exch def /dy tipy taily sub def /dx tipx tailx sub def /angle dx 0 ne dy 0 ne or { dy dx atan } { 90 } ifelse def gsave originalCTM setmatrix tipx tipy translate angle rotate newpath arrowHeight neg arrowWidth 2 div moveto 0 0 lineto arrowHeight neg arrowWidth 2 div neg lineto patternNone not { originalCTM setmatrix /padtip arrowHeight 2 exp 0.25 arrowWidth 2 exp mul add sqrt brushWidth mul arrowWidth div def /padtail brushWidth 2 div def tipx tipy translate angle rotate padtip 0 translate arrowHeight padtip add padtail add arrowHeight div dup scale arrowheadpath ifill } if brushNone not { originalCTM setmatrix tipx tipy translate angle rotate arrowheadpath istroke } if grestore end } dup 0 9 dict put def /arrowheadpath { newpath arrowHeight neg arrowWidth 2 div moveto 0 0 lineto arrowHeight neg arrowWidth 2 div neg lineto } def /leftarrow { 0 begin y exch get /taily exch def x exch get /tailx exch def y exch get /tipy exch def x exch get /tipx exch def brushLeftArrow { tipx tipy tailx taily arrowhead } if end } dup 0 4 dict put def /rightarrow { 0 begin y exch get /tipy exch def x exch get /tipx exch def y exch get /taily exch def x exch get /tailx exch def brushRightArrow { tipx tipy tailx taily arrowhead } if end } dup 0 4 dict put def %I Idraw 10 Grid 45.7532 45.7532 Begin %I b u %I cfg u %I cbg u %I f u %I p u %I t [ 0.619552 0 0 0.619552 0 0 ] concat /originalCTM matrix currentmatrix def Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-helvetica-medium-r-*-120-* Helvetica 12 SetF %I t [ 1 0 0 1 281 1140 ] concat %I [ (P) ] Text End Begin %I Elli %I b 65535 0 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 0 SetP %I t [ 1 0 0 1 154 150 ] concat %I 70 938 3 3 Elli End Begin %I Elli %I b 65535 0 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 0 SetP %I t [ 1 0 0 1 157 104 ] concat %I 70 938 3 3 Elli End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-bold-r-*-120-* Courier-Bold 12 SetF %I t [ 1 0 0 1 199 1136 ] concat %I [ (y) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 213 1182 ] concat %I [ (2) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-helvetica-medium-r-*-120-* Helvetica 12 SetF %I t [ 1 0 0 1 281 1046 ] concat %I [ (M) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 292 1040 ] concat %I [ (i) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 287 1133 ] concat %I [ (i) ] Text End Begin %I Poly %I b 65535 2 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 0 0 1 -28 744 ] concat %I 5 253 433 253 296 299 296 299 388 299 388 5 Poly End Begin %I Elli %I b 65535 0 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 0 SetP %I t [ 1 0 0 1 154 192 ] concat %I 70 938 3 3 Elli End Begin %I Elli %I b 65535 0 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 0 SetP %I t [ 1 0 0 1 155 241 ] concat %I 70 938 3 3 Elli End Begin %I Elli %I b 65535 0 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 0 SetP %I t [ 1 0 0 1 199 104.001 ] concat %I 70 938 3 3 Elli End Begin %I Line %I b 65535 2 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 0 0 1 -28 744 ] concat %I 253 385 299 385 Line %I 1 End Begin %I Line %I b 65535 2 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 0 0 1 -28 744 ] concat %I 253 342 298 342 Line %I 1 End Begin %I Line %I b 65535 2 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 0 0 1 -28 744 ] concat %I 254 384 299 341 Line %I 1 End Begin %I Line %I b 65535 2 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 0 0 1 -28 744 ] concat %I 253 343 299 386 Line %I 1 End Begin %I Line %I b 65535 2 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 0 0 1 -28 744 ] concat %I 255 297 298 341 Line %I 1 End Begin %I Line %I b 65535 2 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 0 0 1 -28 744 ] concat %I 255 340 299 296 Line %I 1 End Begin %I Elli %I b 65535 0 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 0 SetP %I t [ 1 0 0 1 199 149 ] concat %I 70 938 3 3 Elli End Begin %I Elli %I b 65535 0 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 0 SetP %I t [ 1 0 0 1 200 192 ] concat %I 70 938 3 3 Elli End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-bold-r-*-120-* Courier-Bold 12 SetF %I t [ 1 0 0 1 200 1189 ] concat %I [ (y) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 213 1128 ] concat %I [ (3) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-bold-r-*-120-* Courier-Bold 12 SetF %I t [ 1 0 0 1 244 1034 ] concat %I [ (1) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-bold-r-*-120-* Courier-Bold 12 SetF %I t [ 1 0 0 1 276 1067 ] concat %I [ (1) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-bold-r-*-120-* Courier-Bold 12 SetF %I t [ 1 0 0 1 275 1113 ] concat %I [ (1) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-bold-r-*-120-* Courier-Bold 12 SetF %I t [ 1 0 0 1 215 1067 ] concat %I [ (1) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-bold-r-*-120-* Courier-Bold 12 SetF %I t [ 1 0 0 1 213 1113 ] concat %I [ (1) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-bold-r-*-120-* Courier-Bold 12 SetF %I t [ 1 0 0 1 214 1160 ] concat %I [ (1) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 206 1129 ] concat %I [ (i) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 207 1183 ] concat %I [ (i) ] Text End End %I eop showpage end %%EndDocument endTexFig 448 1627 a Fo(Figure)27 b(3:)40 b(Gadget)28 b Fl(H)1233 1641 y Fi(i)1288 1627 y Fo(consists)f(of)h(the)f(ab)s(o)m(v)m(e)i(com)m (bined)d(with)g(Gadget)j Fl(G)3124 1641 y Fi(i)3151 1627 y Fo(,)g(where)448 1740 y(p)s(oin)m(ts)h(with)f(the)h(same)h(lab)s(el)e (coincide.)1205 1857 y 11643372 8551629 12169625 41837199 23812997 50388828 startTexFig 1205 1857 a %%BeginDocument: idraw/gadget3.ps /arrowHeight 13 def /arrowWidth 6 def /IdrawDict 53 dict def IdrawDict begin /reencodeISO { dup dup findfont dup length dict begin { 1 index /FID ne { def }{ pop pop } ifelse } forall /Encoding ISOLatin1Encoding def currentdict end definefont } def /ISOLatin1Encoding [ /.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef /.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef /.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef /.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef /space/exclam/quotedbl/numbersign/dollar/percent/ampersand/quoteright /parenleft/parenright/asterisk/plus/comma/minus/period/slash /zero/one/two/three/four/five/six/seven/eight/nine/colon/semicolon /less/equal/greater/question/at/A/B/C/D/E/F/G/H/I/J/K/L/M/N /O/P/Q/R/S/T/U/V/W/X/Y/Z/bracketleft/backslash/bracketright /asciicircum/underscore/quoteleft/a/b/c/d/e/f/g/h/i/j/k/l/m /n/o/p/q/r/s/t/u/v/w/x/y/z/braceleft/bar/braceright/asciitilde /.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef /.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef /.notdef/dotlessi/grave/acute/circumflex/tilde/macron/breve /dotaccent/dieresis/.notdef/ring/cedilla/.notdef/hungarumlaut /ogonek/caron/space/exclamdown/cent/sterling/currency/yen/brokenbar /section/dieresis/copyright/ordfeminine/guillemotleft/logicalnot /hyphen/registered/macron/degree/plusminus/twosuperior/threesuperior /acute/mu/paragraph/periodcentered/cedilla/onesuperior/ordmasculine /guillemotright/onequarter/onehalf/threequarters/questiondown /Agrave/Aacute/Acircumflex/Atilde/Adieresis/Aring/AE/Ccedilla /Egrave/Eacute/Ecircumflex/Edieresis/Igrave/Iacute/Icircumflex /Idieresis/Eth/Ntilde/Ograve/Oacute/Ocircumflex/Otilde/Odieresis /multiply/Oslash/Ugrave/Uacute/Ucircumflex/Udieresis/Yacute /Thorn/germandbls/agrave/aacute/acircumflex/atilde/adieresis /aring/ae/ccedilla/egrave/eacute/ecircumflex/edieresis/igrave /iacute/icircumflex/idieresis/eth/ntilde/ograve/oacute/ocircumflex /otilde/odieresis/divide/oslash/ugrave/uacute/ucircumflex/udieresis /yacute/thorn/ydieresis ] def /Helvetica reencodeISO def /Courier-Bold reencodeISO def /Courier reencodeISO def /none null def /numGraphicParameters 17 def /stringLimit 65535 def /Begin { save numGraphicParameters dict begin } def /End { end restore } def /SetB { dup type /nulltype eq { pop false /brushRightArrow idef false /brushLeftArrow idef true /brushNone idef } { /brushDashOffset idef /brushDashArray idef 0 ne /brushRightArrow idef 0 ne /brushLeftArrow idef /brushWidth idef false /brushNone idef } ifelse } def /SetCFg { /fgblue idef /fggreen idef /fgred idef } def /SetCBg { /bgblue idef /bggreen idef /bgred idef } def /SetF { /printSize idef /printFont idef } def /SetP { dup type /nulltype eq { pop true /patternNone idef } { dup -1 eq { /patternGrayLevel idef /patternString idef } { /patternGrayLevel idef } ifelse false /patternNone idef } ifelse } def /BSpl { 0 begin storexyn newpath n 1 gt { 0 0 0 0 0 0 1 1 true subspline n 2 gt { 0 0 0 0 1 1 2 2 false subspline 1 1 n 3 sub { /i exch def i 1 sub dup i dup i 1 add dup i 2 add dup false subspline } for n 3 sub dup n 2 sub dup n 1 sub dup 2 copy false subspline } if n 2 sub dup n 1 sub dup 2 copy 2 copy false subspline patternNone not brushLeftArrow not brushRightArrow not and and { ifill } if brushNone not { istroke } if 0 0 1 1 leftarrow n 2 sub dup n 1 sub dup rightarrow } if end } dup 0 4 dict put def /Circ { newpath 0 360 arc patternNone not { ifill } if brushNone not { istroke } if } def /CBSpl { 0 begin dup 2 gt { storexyn newpath n 1 sub dup 0 0 1 1 2 2 true subspline 1 1 n 3 sub { /i exch def i 1 sub dup i dup i 1 add dup i 2 add dup false subspline } for n 3 sub dup n 2 sub dup n 1 sub dup 0 0 false subspline n 2 sub dup n 1 sub dup 0 0 1 1 false subspline patternNone not { ifill } if brushNone not { istroke } if } { Poly } ifelse end } dup 0 4 dict put def /Elli { 0 begin newpath 4 2 roll translate scale 0 0 1 0 360 arc patternNone not { ifill } if brushNone not { istroke } if end } dup 0 1 dict put def /Line { 0 begin 2 storexyn newpath x 0 get y 0 get moveto x 1 get y 1 get lineto brushNone not { istroke } if 0 0 1 1 leftarrow 0 0 1 1 rightarrow end } dup 0 4 dict put def /MLine { 0 begin storexyn newpath n 1 gt { x 0 get y 0 get moveto 1 1 n 1 sub { /i exch def x i get y i get lineto } for patternNone not brushLeftArrow not brushRightArrow not and and { ifill } if brushNone not { istroke } if 0 0 1 1 leftarrow n 2 sub dup n 1 sub dup rightarrow } if end } dup 0 4 dict put def /Poly { 3 1 roll newpath moveto -1 add { lineto } repeat closepath patternNone not { ifill } if brushNone not { istroke } if } def /Rect { 0 begin /t exch def /r exch def /b exch def /l exch def newpath l b moveto l t lineto r t lineto r b lineto closepath patternNone not { ifill } if brushNone not { istroke } if end } dup 0 4 dict put def /Text { ishow } def /idef { dup where { pop pop pop } { exch def } ifelse } def /ifill { 0 begin gsave patternGrayLevel -1 ne { fgred bgred fgred sub patternGrayLevel mul add fggreen bggreen fggreen sub patternGrayLevel mul add fgblue bgblue fgblue sub patternGrayLevel mul add setrgbcolor eofill } { eoclip originalCTM setmatrix pathbbox /t exch def /r exch def /b exch def /l exch def /w r l sub ceiling cvi def /h t b sub ceiling cvi def /imageByteWidth w 8 div ceiling cvi def /imageHeight h def bgred bggreen bgblue setrgbcolor eofill fgred fggreen fgblue setrgbcolor w 0 gt h 0 gt and { l b translate w h scale w h true [w 0 0 h neg 0 h] { patternproc } imagemask } if } ifelse grestore end } dup 0 8 dict put def /istroke { gsave brushDashOffset -1 eq { [] 0 setdash 1 setgray } { brushDashArray brushDashOffset setdash fgred fggreen fgblue setrgbcolor } ifelse brushWidth setlinewidth originalCTM setmatrix stroke grestore } def /ishow { 0 begin gsave fgred fggreen fgblue setrgbcolor /fontDict printFont printSize scalefont dup setfont def /descender fontDict begin 0 [FontBBox] 1 get FontMatrix end transform exch pop def /vertoffset 1 printSize sub descender sub def { 0 vertoffset moveto show /vertoffset vertoffset printSize sub def } forall grestore end } dup 0 3 dict put def /patternproc { 0 begin /patternByteLength patternString length def /patternHeight patternByteLength 8 mul sqrt cvi def /patternWidth patternHeight def /patternByteWidth patternWidth 8 idiv def /imageByteMaxLength imageByteWidth imageHeight mul stringLimit patternByteWidth sub min def /imageMaxHeight imageByteMaxLength imageByteWidth idiv patternHeight idiv patternHeight mul patternHeight max def /imageHeight imageHeight imageMaxHeight sub store /imageString imageByteWidth imageMaxHeight mul patternByteWidth add string def 0 1 imageMaxHeight 1 sub { /y exch def /patternRow y patternByteWidth mul patternByteLength mod def /patternRowString patternString patternRow patternByteWidth getinterval def /imageRow y imageByteWidth mul def 0 patternByteWidth imageByteWidth 1 sub { /x exch def imageString imageRow x add patternRowString putinterval } for } for imageString end } dup 0 12 dict put def /min { dup 3 2 roll dup 4 3 roll lt { exch } if pop } def /max { dup 3 2 roll dup 4 3 roll gt { exch } if pop } def /midpoint { 0 begin /y1 exch def /x1 exch def /y0 exch def /x0 exch def x0 x1 add 2 div y0 y1 add 2 div end } dup 0 4 dict put def /thirdpoint { 0 begin /y1 exch def /x1 exch def /y0 exch def /x0 exch def x0 2 mul x1 add 3 div y0 2 mul y1 add 3 div end } dup 0 4 dict put def /subspline { 0 begin /movetoNeeded exch def y exch get /y3 exch def x exch get /x3 exch def y exch get /y2 exch def x exch get /x2 exch def y exch get /y1 exch def x exch get /x1 exch def y exch get /y0 exch def x exch get /x0 exch def x1 y1 x2 y2 thirdpoint /p1y exch def /p1x exch def x2 y2 x1 y1 thirdpoint /p2y exch def /p2x exch def x1 y1 x0 y0 thirdpoint p1x p1y midpoint /p0y exch def /p0x exch def x2 y2 x3 y3 thirdpoint p2x p2y midpoint /p3y exch def /p3x exch def movetoNeeded { p0x p0y moveto } if p1x p1y p2x p2y p3x p3y curveto end } dup 0 17 dict put def /storexyn { /n exch def /y n array def /x n array def n 1 sub -1 0 { /i exch def y i 3 2 roll put x i 3 2 roll put } for } def /SSten { fgred fggreen fgblue setrgbcolor dup true exch 1 0 0 -1 0 6 -1 roll matrix astore } def /FSten { dup 3 -1 roll dup 4 1 roll exch newpath 0 0 moveto dup 0 exch lineto exch dup 3 1 roll exch lineto 0 lineto closepath bgred bggreen bgblue setrgbcolor eofill SSten } def /Rast { exch dup 3 1 roll 1 0 0 -1 0 6 -1 roll matrix astore } def /arrowhead { 0 begin transform originalCTM itransform /taily exch def /tailx exch def transform originalCTM itransform /tipy exch def /tipx exch def /dy tipy taily sub def /dx tipx tailx sub def /angle dx 0 ne dy 0 ne or { dy dx atan } { 90 } ifelse def gsave originalCTM setmatrix tipx tipy translate angle rotate newpath arrowHeight neg arrowWidth 2 div moveto 0 0 lineto arrowHeight neg arrowWidth 2 div neg lineto patternNone not { originalCTM setmatrix /padtip arrowHeight 2 exp 0.25 arrowWidth 2 exp mul add sqrt brushWidth mul arrowWidth div def /padtail brushWidth 2 div def tipx tipy translate angle rotate padtip 0 translate arrowHeight padtip add padtail add arrowHeight div dup scale arrowheadpath ifill } if brushNone not { originalCTM setmatrix tipx tipy translate angle rotate arrowheadpath istroke } if grestore end } dup 0 9 dict put def /arrowheadpath { newpath arrowHeight neg arrowWidth 2 div moveto 0 0 lineto arrowHeight neg arrowWidth 2 div neg lineto } def /leftarrow { 0 begin y exch get /taily exch def x exch get /tailx exch def y exch get /tipy exch def x exch get /tipx exch def brushLeftArrow { tipx tipy tailx taily arrowhead } if end } dup 0 4 dict put def /rightarrow { 0 begin y exch get /tipy exch def x exch get /tipx exch def y exch get /taily exch def x exch get /tailx exch def brushRightArrow { tipx tipy tailx taily arrowhead } if end } dup 0 4 dict put def %I Idraw 10 Grid 45.7532 45.7532 Begin %I b u %I cfg u %I cbg u %I f u %I p u %I t [ 0.619552 0 0 0.619552 0 0 ] concat /originalCTM matrix currentmatrix def Begin %I Line %I b 65535 0 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 0 0 1 -109 421 ] concat %I 627 710 629 708 Line %I 1 End Begin %I Elli %I b 65535 2 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 0 SetP %I t [ 1 0 0 1 484 283 ] concat %I 70 938 3 3 Elli End Begin %I Elli %I b 65535 2 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 0 SetP %I t [ 1 0 0 1 484 239 ] concat %I 70 938 3 3 Elli End Begin %I Elli %I b 65535 2 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 0 SetP %I t [ 1 0 0 1 485 194 ] concat %I 70 938 3 3 Elli End Begin %I Elli %I b 65535 2 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 0 SetP %I t [ 1 0 0 1 484 148 ] concat %I 70 938 3 3 Elli End Begin %I Elli %I b 65535 2 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 0 SetP %I t [ 1 0 0 1 484 104 ] concat %I 70 938 3 3 Elli End Begin %I Line %I b 65535 2 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 0 0 1 164 423 ] concat %I 391 796 391 614 Line %I 1 End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-helvetica-medium-r-*-120-* Helvetica 12 SetF %I t [ 1 0 0 1 564 1231 ] concat %I [ (P) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-helvetica-medium-r-*-120-* Helvetica 12 SetF %I t [ 1 0 0 1 567 1133 ] concat %I [ (N) ] Text End Begin %I Rect %I b 65535 2 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 0 0 1 -14 663 ] concat %I 398 488 398 489 Rect End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-bold-r-*-120-* Courier-Bold 12 SetF %I t [ 1 0 0 1 303 1168 ] concat %I [ (y) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-helvetica-medium-r-*-120-* Helvetica 12 SetF %I t [ 1 0 0 1 387 1074 ] concat %I [ (N) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 571 1039 ] concat %I [ (3) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-helvetica-medium-r-*-120-* Helvetica 12 SetF %I t [ 1 0 0 1 561 1048 ] concat %I [ (l) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 577 1125 ] concat %I [ (i) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 571 1223 ] concat %I [ (i) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 396 1064 ] concat %I [ (i) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 391 1154 ] concat %I [ (i) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-helvetica-medium-r-*-120-* Helvetica 12 SetF %I t [ 1 0 0 1 381 1158 ] concat %I [ (Q) ] Text End Begin %I Elli %I b 65535 0 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 0 SetP %I t [ 1 0 0 1 258 221 ] concat %I 70 938 3 3 Elli End Begin %I Elli %I b 65535 0 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 0 SetP %I t [ 1 0 0 1 259 177 ] concat %I 70 938 3 3 Elli End Begin %I Elli %I b 65535 0 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 0 SetP %I t [ 1 0 0 1 261 133 ] concat %I 70 938 3 3 Elli End Begin %I Poly %I b 65535 2 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 0 0 1 76 773 ] concat %I 5 253 433 253 296 299 296 299 388 299 388 5 Poly End Begin %I Elli %I b 65535 0 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 0 SetP %I t [ 1 0 0 1 259 270 ] concat %I 70 938 3 3 Elli End Begin %I Elli %I b 65535 0 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 0 SetP %I t [ 1 0 0 1 305 224 ] concat %I 70 938 3 3 Elli End Begin %I Elli %I b 65535 0 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 0 SetP %I t [ 1 0 0 1 304 177 ] concat %I 70 938 3 3 Elli End Begin %I Elli %I b 65535 0 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg %I p 0 SetP %I t [ 1 0 0 1 305 132.001 ] concat %I 70 938 3 3 Elli End Begin %I Line %I b 65535 2 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 0 0 1 76 773 ] concat %I 253 385 299 385 Line %I 1 End Begin %I Line %I b 65535 2 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 0 0 1 76 773 ] concat %I 253 342 298 342 Line %I 1 End Begin %I Line %I b 65535 2 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 0 0 1 76 773 ] concat %I 254 384 299 341 Line %I 1 End Begin %I Line %I b 65535 2 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 0 0 1 74 771 ] concat %I 253 343 299 386 Line %I 1 End Begin %I Line %I b 65535 2 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 0 0 1 73 772 ] concat %I 255 297 298 341 Line %I 1 End Begin %I Line %I b 65535 2 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 0 0 1 76 773 ] concat %I 255 340 299 296 Line %I 1 End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 314 1158 ] concat %I [ (5) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-bold-r-*-120-* Courier-Bold 12 SetF %I t [ 1 0 0 1 305 1212 ] concat %I [ (y) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 318 1205 ] concat %I [ (4) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-bold-r-*-120-* Courier-Bold 12 SetF %I t [ 1 0 0 1 546 1070 ] concat %I [ (1) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-bold-r-*-120-* Courier-Bold 12 SetF %I t [ 1 0 0 1 546 1116 ] concat %I [ (1) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-bold-r-*-120-* Courier-Bold 12 SetF %I t [ 1 0 0 1 546 1160 ] concat %I [ (1) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-bold-r-*-120-* Courier-Bold 12 SetF %I t [ 1 0 0 1 546 1204 ] concat %I [ (1) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-bold-r-*-120-* Courier-Bold 12 SetF %I t [ 1 0 0 1 376 1142 ] concat %I [ (1) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-bold-r-*-120-* Courier-Bold 12 SetF %I t [ 1 0 0 1 376 1101 ] concat %I [ (1) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-bold-r-*-120-* Courier-Bold 12 SetF %I t [ 1 0 0 1 349 1064 ] concat %I [ (1) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-bold-r-*-120-* Courier-Bold 12 SetF %I t [ 1 0 0 1 320 1098 ] concat %I [ (1) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-bold-r-*-120-* Courier-Bold 12 SetF %I t [ 1 0 0 1 320 1188 ] concat %I [ (1) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-bold-r-*-120-* Courier-Bold 12 SetF %I t [ 1 0 0 1 320 1143 ] concat %I [ (1) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 564 1040 ] concat %I [ (i) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 311 1205 ] concat %I [ (i) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-courier-medium-r-*-100-* Courier 10 SetF %I t [ 1 0 0 1 308 1160 ] concat %I [ (i) ] Text End End %I eop showpage end %%EndDocument endTexFig 448 3137 a Fo(Figure)39 b(4:)60 b(Gadget)41 b Fl(K)1279 3151 y Fi(i)1307 3137 y Fo(,)h(consisting)c(of)i(the)g(ab)s(o)m(v)m(e)g (com)m(bined)f(with)f(Gadget)j Fl(H)3384 3151 y Fi(i)3412 3137 y Fo(,)448 3250 y(where)30 b(p)s(oin)m(ts)f(with)h(the)g(same)h (lab)s(el)e(coincide.)448 3525 y(if)h(and)f(only)h(if)f Fl(l)1018 3539 y Fi(i)p Fj(1)1112 3525 y Fo(or)i Fl(l)1251 3539 y Fi(i)p Fj(2)1344 3525 y Fo(ha)m(v)m(e)h(their)d Fl(x)p Fk(\000)p Fo(v)-5 b(alue)30 b(equal)g(to)h(1.)589 3638 y Fl(H)665 3652 y Fi(i)733 3638 y Fo(is)38 b(a)i(true)f(or)h (gate.)70 b(W)-8 b(e)41 b(com)m(bine)e(this)f(with)g(a)i(similar)d (construction)i(to)448 3751 y(build)30 b(a)k(three-w)m(a)m(y)g (or-gate.)51 b(F)-8 b(or)34 b(completeness)f(w)m(e)h(sho)m(w)f(this)f (en)m(tire)g(three-w)m(a)m(y)448 3863 y(or-gate,)f Fl(K)857 3877 y Fi(i)886 3863 y Fo(,)d(in)f(Figure)h(4.)40 b(Note)30 b(that)f(its)e(output)h Fl(Q)2343 3877 y Fi(i)2399 3863 y Fo(has)g(its)g Fl(y)s Fk(\000)p Fo(co)s(ordinate)g(\014xed)448 3976 y(lev)m(el)h(with)f Fl(y)905 3990 y Fi(i)p Fj(5)998 3976 y Fo(and)h(that)h Fl(Q)1442 3990 y Fi(i)1499 3976 y Fo(can)g(b)s(e)e(placed)h(on)h(the)f(line)f Fl(x)d Fo(=)g(1)30 b(i\013)e(at)j(least)e(one)h(of)448 4089 y Fl(l)475 4103 y Fi(i)p Fj(1)539 4089 y Fl(;)15 b(l)606 4103 y Fi(i)p Fj(2)700 4089 y Fo(or)31 b Fl(l)839 4103 y Fi(i)p Fj(3)932 4089 y Fo(lies)f(on)g(the)g(line)f(x=1.)589 4202 y(The)g(gadget)i Fl(K)1144 4216 y Fi(i)1172 4202 y Fl(;)f Fo(is)e(a)h(com)m(bination)g(of)g Fl(H)2086 4216 y Fi(i)2143 4202 y Fo(with)f(another)h(ladder)f(and)h(another)448 4315 y(straigh)m(t)21 b(piece)f(\(similar)e(to)j(the)g(one)f(used)g(in) f Fl(G)2086 4329 y Fi(i)2113 4315 y Fo(\).)38 b(The)20 b(straigh)m(t)g(piece)g(adds)g(another)448 4428 y(sp)s(ecial)34 b(v)m(ertex)i Fl(N)1102 4442 y Fi(i)1131 4428 y Fo(,)g(whic)m(h)e (connects)i Fl(P)1889 4442 y Fi(i)1953 4428 y Fo(and)f Fl(l)2162 4442 y Fi(i)p Fj(3)2225 4428 y Fo(.)55 b(Again)35 b(w)m(e)h(are)g(assuming)d(that)448 4541 y(the)i(gadget)h(is)d (arranged)h(so)g(that)h(the)g Fl(y)1906 4555 y Fi(ij)2000 4541 y Fo(are)g(on)f(the)g Fl(y)s Fk(\000)p Fo(axis.)52 b(Then)33 b Fl(N)3111 4555 y Fi(i)3173 4541 y Fo(can)i(b)s(e)448 4654 y(placed)d(on)h(the)g(line)e Fl(x)e Fo(=)g(1)k(if)e(and)h(only)g (if)g Fl(P)2064 4668 y Fi(i)2125 4654 y Fo(or)h Fl(l)2266 4668 y Fi(i)p Fj(3)2362 4654 y Fo(are.)48 b(Since)31 b Fl(P)2853 4668 y Fi(i)2915 4654 y Fo(is)g(on)i(the)g(line)448 4767 y Fl(x)27 b Fo(=)g(1)32 b(if)e(and)h(only)f(if)g Fl(l)1275 4781 y Fi(i)p Fj(1)1370 4767 y Fo(or)i Fl(l)1510 4781 y Fi(i)p Fj(2)1605 4767 y Fo(are,)g Fl(N)1856 4781 y Fi(i)1915 4767 y Fo(has)f Fl(x)p Fk(\000)p Fo(v)-5 b(alue)31 b(equal)g(to)h(1)g(if)e Fl(C)3016 4781 y Fi(i)3075 4767 y Fo(ev)-5 b(aluates)448 4880 y(to)31 b(\\true.")42 b(The)30 b(ladder)f(in)g Fl(K)1526 4894 y Fi(i)1585 4880 y Fo(ensures)g(that)i Fl(Q)2173 4894 y Fi(i)2231 4880 y Fo(has)f(the)h(same)g Fl(x)p Fk(\000)p Fo(v)-5 b(alue)29 b(as)i Fl(N)3320 4894 y Fi(i)3348 4880 y Fo(.)1920 5162 y(7)p eop %%Page: 8 8 8 7 bop 589 623 a Fo(The)24 b(completed)h(gadget)h Fl(K)1563 637 y Fi(i)1615 623 y Fo(w)m(orks)f(as)g(follo)m(ws:)36 b(without)24 b(loss)g(of)g(generalit)m(y)-8 b(,)27 b(w)m(e)448 736 y(can)32 b(assume)f(that)g Fl(K)1205 750 y Fi(i)1265 736 y Fo(is)f(aligned)g(on)h(the)g(in)m(teger)g(lattice)h(so)f(that)h (the)f Fl(y)3047 750 y Fi(ij)3138 736 y Fo(v)m(ertices)448 848 y(lie)d(on)h(the)f Fl(y)s Fk(\000)p Fo(axis.)40 b(Then)27 b Fl(Q)1493 862 y Fi(i)1550 848 y Fo(lies)g(on)i(the)g(line)e Fl(x)e Fo(=)g(1)k(if)f(and)g(only)g(if)g Fl(l)2966 862 y Fi(i)p Fj(1)3058 848 y Fo(has)g Fl(x)e Fo(=)f(1)448 961 y(or)31 b Fl(l)587 975 y Fi(i)p Fj(2)681 961 y Fo(has)f Fl(x)25 b Fo(=)g(1)31 b(or)f Fl(l)1230 975 y Fi(i)p Fj(3)1324 961 y Fo(has)g Fl(x)25 b Fo(=)g(1.)589 1074 y(W)-8 b(e)38 b(no)m(w)e(are)h(ready)f(to)h(build)c(the)j(link)-5 b(age)35 b Fk(L)p Fo(\()p Fl(')p Fo(\).)59 b(Eac)m(h)37 b(clause)f Fl(C)3036 1088 y Fi(i)3100 1074 y Fo(of)h Fl(')f Fo(has)448 1187 y(a)41 b(corresp)s(onding)d(gadget)k Fl(K)1508 1201 y Fi(i)1536 1187 y Fo(,)h(built)38 b(as)i(describ)s(ed)e(ab)s(o)m(v)m (e.)71 b(W)-8 b(e)41 b(line)e(up)g(all)g(the)448 1300 y(gadgets)34 b Fl(K)856 1314 y Fi(i)917 1300 y Fo(one)e(underneath)f (the)h(other,)i(the)e(top)g(of)h Fl(K)2495 1314 y Fi(i)p Fj(+1)2646 1300 y Fo(connecting)f(with)f(the)448 1413 y(b)s(ottom)40 b(of)g Fl(K)968 1427 y Fi(i)996 1413 y Fo(.)68 b(W)-8 b(e)41 b(need)e(to)h(ensure)f(that)h(all)e(app)s (earances)i(of)f(a)h(literals)e(ha)m(v)m(e)448 1526 y(the)33 b(same)g(truth)e(v)-5 b(alue.)47 b(This)30 b(is)i(done)g(b)m(y)g (connecting)h(app)s(earances)f(of)h(the)g(same)448 1639 y(v)-5 b(ariable)29 b(with)g(a)i(link)d(as)j(follo)m(ws:)39 b(if)29 b(the)i(literal)e Fl(l)2226 1653 y Fi(is)2317 1639 y Fo(is)g(the)h(same)h(as)g(the)f(literal)f Fl(l)3350 1653 y Fi(j)t(t)3412 1639 y Fo(,)448 1752 y(and)34 b(either)f(the)h (literal)f Fl(l)1344 1766 y Fi(is)1438 1752 y Fo(or)h(the)g(literal)f Fl(l)2007 1766 y Fi(j)t(t)2103 1752 y Fo(is)g(not)h(already)f (connected)i(to)g(other)448 1865 y(literals,)g(then)f(w)m(e)h(connect)g (the)g(t)m(w)m(o)h(instances,)f Fl(l)2248 1879 y Fi(is)2309 1865 y Fl(;)15 b(l)2376 1879 y Fi(j)t(t)2439 1865 y Fo(,)36 b(with)d(a)i(link)d(of)j(length)f(of)448 1978 y Fk(j)p Fo(6\()p Fl(j)25 b Fk(\000)18 b Fl(i)p Fo(\))g(+)g(4\()p Fl(t)h Fk(\000)e Fl(s)p Fo(\))p Fk(j)p Fo(.)41 b(This)27 b(length)i(ensures)f(the)i(literals)e Fl(l)2548 1992 y Fi(is)2638 1978 y Fo(and)g Fl(l)2840 1992 y Fi(j)t(t)2932 1978 y Fo(will)e(ha)m(v)m(e)31 b(the)448 2090 y(same)37 b Fl(x)p Fk(\000)p Fo(v)-5 b(alue.)60 b(\(Note)38 b(that)f(if)f(w)m(e)h (w)m(an)m(t)h(to)f(k)m(eep)h(all)e(our)g(lines)f(short,)j(w)m(e)f(ma)m (y)448 2203 y(replace)d(this)e(line)g(b)m(y)h(a)h(system)f(of)h Fk(j)p Fo(6\()p Fl(j)29 b Fk(\000)21 b Fl(i)p Fo(\))i(+)f(4\()p Fl(t)h Fk(\000)f Fl(s)p Fo(\))p Fk(j)33 b Fo(connected,)j(unit-length) 448 2316 y(links.\))589 2429 y(Next)23 b(w)m(e)f(add)e(a)i(link)-5 b(age)21 b(consisting)f(of)i Fl(r)h Fo(links)d(of)h(length)g(6,)j (connecting)d(v)m(ertices)448 2542 y Fl(Q)520 2556 y Fj(1)560 2542 y Fl(;)15 b(:)g(:)g(:)h(;)f(Q)833 2556 y Fi(r)871 2542 y Fo(.)41 b(This)29 b(assures)h(that)h(all)e(the)h (clauses)g(are)h(true)f(sim)m(ultaneously)-8 b(.)589 2655 y(It)34 b(is)f(clear)h(that)h(a)f(satisfying)f(assignmen)m(t)g(of) h(the)g(v)-5 b(ariables)33 b(leads)g(to)i(an)f(em-)448 2768 y(b)s(edding)g(of)j(the)f(link)-5 b(age.)58 b(It)36 b(is)f(also)h(clear)h(that)g Fg(any)g Fo(em)m(b)s(edding)d(of)i(the)h (link)-5 b(age)448 2881 y(can)32 b(b)s(e)e(transformed)h(to)g(one)h (that)g(places)f(the)g Fl(y)2198 2895 y Fi(ij)2289 2881 y Fo(on)g(the)g Fl(y)s Fk(\000)p Fo(axis)g Fg(and)h Fo(the)f Fl(Q)3282 2895 y Fi(i)3341 2881 y Fo(on)448 2994 y(the)f(line)d Fl(x)e Fo(=)g Fk(\000)p Fo(1)k Fg(or)h Fl(x)25 b Fo(=)g(1.)41 b(If)29 b(the)g Fl(Q)1807 3008 y Fi(i)1864 2994 y Fo(are)h(all)e(on)h (the)g(line)e Fl(x)e Fo(=)g(1,)30 b(then)f(the)g Fl(l)3251 3008 y Fi(ij)3341 2994 y Fo(on)448 3107 y(the)j(line)e Fl(x)d Fo(=)f(1)32 b(are)g(assigned)f(to)h(\\true,")h(and)d(w)m(e)i(ha) m(v)m(e)h(a)f(satisfying)e(assignmen)m(t.)448 3220 y(If)j(the)h Fl(Q)774 3234 y Fi(i)835 3220 y Fo(are)g(all)e(on)h(the)h(line)e Fl(x)e Fo(=)g Fk(\000)p Fo(1,)k(assign)f(the)h(literals)d(on)j(the)f (line)f Fl(x)e Fo(=)g Fk(\000)p Fo(1)448 3333 y(the)j(v)-5 b(alue)31 b(\\true,")i(and)f(again)g(w)m(e)g(ha)m(v)m(e)h(a)g (satisfying)d(assignmen)m(t.)46 b(F)-8 b(urthermore,)448 3445 y(the)31 b(reduction)e(w)m(e)i(ha)m(v)m(e)h(presen)m(ted)e(is)f (in)g(p)s(olynomial)f(time.)41 b(More)31 b(formally)-8 b(,)448 3658 y Fh(Lemma)33 b(2.8)46 b Fg(F)-7 b(or)42 b(e)-5 b(ach)42 b Fl(C)1454 3672 y Fi(i)1523 3658 y Fo(=)e Fl(l)1661 3672 y Fi(i)p Fj(1)1751 3658 y Fk(_)26 b Fl(l)1865 3672 y Fi(i)p Fj(2)1955 3658 y Fk(_)f Fl(l)2068 3672 y Fi(i)p Fj(3)2132 3658 y Fg(,)43 b(wher)-5 b(e)42 b(the)f Fl(l)2654 3672 y Fi(ij)2715 3658 y Fg('s)g(ar)-5 b(e)42 b(liter)-5 b(als,)45 b(the)448 3771 y(gadget)35 b Fl(G)803 3785 y Fi(i)865 3771 y Fg(with)g(the)f(vertic)-5 b(es)35 b Fl(y)1592 3785 y Fi(ij)1686 3771 y Fg(on)f(the)h(y-axis)f(c)-5 b(an)35 b(have)g(the)f(vertex)h Fl(M)3125 3785 y Fi(i)3187 3771 y Fg(on)g(the)448 3884 y(line)e Fl(x)25 b Fo(=)g(1)33 b Fg(if)f(and)i(only)f(if)g Fl(l)1454 3898 y Fi(i)p Fj(1)1550 3884 y Fg(or)g Fl(l)1694 3898 y Fi(i)p Fj(2)1790 3884 y Fg(is)g(on)g(the)g(line)f Fl(x)26 b Fo(=)f(1)p Fg(.)448 4096 y Fh(Lemma)33 b(2.9)46 b Fg(With)37 b(c)-5 b(onditions)39 b(as)e(ab)-5 b(ove,)38 b(the)f(gadget)g Fl(H)2584 4110 y Fi(i)2649 4096 y Fg(c)-5 b(an)37 b(b)-5 b(e)37 b(emb)-5 b(e)g(dde)g(d)39 b(on)448 4209 y(the)34 b(inte)-5 b(ger)33 b(lattic)-5 b(e.)45 b Fl(P)1268 4223 y Fi(i)1330 4209 y Fg(c)-5 b(an)33 b(b)-5 b(e)34 b(on)f(the)h(line)f Fl(x)26 b Fo(=)g(1)34 b Fg(if)f(and)h(only)g(if)f Fl(l)2903 4223 y Fi(i)p Fj(1)3000 4209 y Fg(or)h Fl(l)3145 4223 y Fi(i)p Fj(2)3241 4209 y Fg(is)g(on)448 4322 y(the)f(line)g Fl(x)25 b Fo(=)g(1)p Fg(.)448 4560 y Fh(Pro)s(of)33 b Fo(The)f(\014rst)f (statemen)m(t)j(is)d(clear.)46 b(The)31 b(second)h(statemen)m(t)i (follo)m(ws)d(from)h(the)448 4672 y(fact)g(that)f(of)f(necessit)m(y)h Fl(P)1366 4686 y Fi(i)1425 4672 y Fo(and)f Fl(M)1690 4686 y Fi(i)1748 4672 y Fo(ha)m(v)m(e)i(the)e(same)h Fl(x)f Fo(v)-5 b(alue.)715 b Ff(2)1920 5162 y Fo(8)p eop %%Page: 9 9 9 8 bop 448 623 a Fh(Lemma)33 b(2.10)46 b Fg(The)38 b(gadget)h Fl(K)1605 637 y Fi(i)1671 623 y Fg(c)-5 b(an)38 b(b)-5 b(e)38 b(emb)-5 b(e)g(dde)g(d)39 b(on)g(the)f(inte)-5 b(ger)38 b(lattic)-5 b(e.)58 b(The)448 736 y(p)-5 b(oint)35 b Fl(Q)751 750 y Fi(i)812 736 y Fg(c)-5 b(an)34 b(b)-5 b(e)33 b(on)g(the)h(line)f Fl(x)26 b Fo(=)g(1)33 b Fg(if)g(and)h(only)g (if)f Fl(C)2422 750 y Fi(i)2483 736 y Fg(evaluates)h(to)g(true)f (\(wher)-5 b(e)448 848 y(the)33 b(liter)-5 b(als)35 b(in)d Fl(C)1072 862 y Fi(i)1133 848 y Fg(ar)-5 b(e)33 b(assigne)-5 b(d)34 b(true)f(i\013)f(they)h(lie)f(on)i(the)f(line)f Fl(x)25 b Fo(=)g(1)p Fg(\).)589 1061 y Fo(Let)34 b(Link)-5 b(ages)32 b(b)s(e)g(the)h(problem)e(of)i(whether)f(a)h(link)-5 b(age)32 b(can)h(b)s(e)f(em)m(b)s(edded)g(on)448 1174 y(the)f(in)m(teger)g(lattice.)41 b(W)-8 b(e)31 b(ha)m(v)m(e)h(sho)m (wn:)448 1386 y Fh(Theorem)i(2.11)47 b Fg(Linkages)32 b(is)h(str)-5 b(ongly)34 b Fk(N)13 b(P)8 b Fg(-c)-5 b(omplete.)589 1599 y Fo(It)21 b(is)e(in)m(teresting)h(to)h(compare)g(this)e(result)g (with)g(an)h(earlier)f(theorem)i(of)f(Hop)s(croft,)448 1712 y(Joseph)42 b(and)f(Whitesides)g([7].)76 b(Their)40 b(result)h(sho)m(ws)g(the)i(ruler)d(problem)g(|)i(the)448 1825 y(question)35 b(of)i(whether)e(a)h(carp)s(en)m(ter's)g(ruler)e (consisting)h(of)h(a)h(sequence)f(of)g Fl(n)f Fo(links)448 1938 y(of)e(in)m(teger)f(lengths,)g Fl(l)1224 1952 y Fj(1)1264 1938 y Fl(;)15 b(:)g(:)g(:)h(;)f(l)1492 1952 y Fi(n)1540 1938 y Fo(,)32 b(hinged)f(together)j(at)e(the)h(endp)s(oin) m(ts,)e(and)g(allo)m(w)m(ed)448 2051 y(to)42 b(fold)d(so)i(that)g (angles)f(of)h(either)f(0)1798 2018 y Fu(\016)1878 2051 y Fo(or)h(180)2135 2018 y Fu(\016)2216 2051 y Fo(are)g(formed,)i(can)e (b)s(e)f(aligned)f(so)448 2164 y(that)33 b(its)e(length)g(is)g Fl(k)k Fo(|)d(is)f Fk(N)13 b(P)8 b(\000)p Fo(complete.)45 b(The)32 b(pro)s(of)f(is)g(via)g(a)i(reduction)e(from)448 2276 y(the)36 b(P)m(artition)e(problem.)54 b(The)35 b(reduction)f(do)s (es)h(not)h(sho)m(w)f(the)g(ruler)f(problem)f(to)448 2389 y(b)s(e)40 b(strongly)f Fk(N)13 b(P)7 b(\000)p Fo(complete.)70 b(In)39 b(fact,)44 b(it)39 b(is)g(not.)69 b(In)40 b([7],)j(there)d(is)f (a)h(dynamic)448 2502 y(programming)27 b(solution)f(to)j(the)f(problem) e(that)i(giv)m(es)g(a)g(p)s(olynomial-time)d(solution)448 2615 y(if)30 b(the)g(lengths)g(in)f(the)h(ruler)f(problem)g(are)i(p)s (olynomially-b)s(ounded.)589 2728 y(The)37 b(reduction)f(w)m(e)h(ha)m (v)m(e)h(used)e(to)i(pro)m(v)m(e)f(the)g(strong)h Fk(N)13 b(P)7 b(\000)p Fo(completeness)37 b(of)448 2841 y(Link)-5 b(ages)49 b(sho)m(ws)f(that)h(the)g(problem)e(remains)h Fk(N)13 b(P)7 b Fo(-complete)50 b(ev)m(en)f(when)f(the)448 2954 y(lengths)38 b(of)g(all)f(the)h(links)e(are)j(b)s(ounded)d(b)m(y)i (a)g(\014xed)f(constan)m(t.)66 b(The)37 b(complexit)m(y)448 3067 y(arises)e(instead)h(from)f(the)h(in)m(teractions)f(of)h(the)g(p)s (olygons.)56 b(There)35 b(are)i(t)m(w)m(o)g(useful)448 3180 y(restrictions)31 b(that)g(simplify)d(the)k(problem)e (computationally)g(but)h(still)e(include)g(the)448 3293 y(class)38 b(of)f(problems)f(w)m(e)i(are)g(in)m(terested)f(in)f(in)h (practice.)62 b(In)37 b(the)g(next)h(section)g(w)m(e)448 3406 y(consider)30 b(these.)448 3692 y Fp(3)135 b(Em)l(b)t(edding)45 b(Link)-7 b(ages)45 b(with)h(Restrictions)448 3895 y Fo(The)25 b(\014rst)g(restriction)f(is)h(to)h(require)e(that)i(the)g (link)-5 b(age)24 b(b)s(e)h(of)h(b)s(ounded)d(size,)k(that)f(is,)448 4008 y(the)33 b(link)-5 b(age)31 b(m)m(ust)i(lie)e(within)f(an)i Fl(m)21 b Fk(\002)h Fl(m)32 b Fo(in)m(teger)g(grid.)46 b(\(Ob)m(viously)31 b(this)g(implies)448 4121 y(that)41 b(all)f(of)g(the)h(lengths)e Fl(l)1422 4135 y Fi(i)1491 4121 y Fo(m)m(ust)h(b)s(e)g(small.\))69 b(The)40 b(second)g (restriction)g(is)f(com-)448 4234 y(binatorial:)52 b(it)37 b(is)f(that)h(there)g(are)h(only)e(a)h(b)s(ounded)e(n)m(um)m(b)s(er)h (of)h(closed)f(\014gures)h({)448 4347 y(\\p)s(olygons")f({)g(in)f(the)h (link)-5 b(age.)56 b(F)-8 b(or)36 b(man)m(y)g(applications)e(that)i(is) f(a)h(v)m(ery)h(reason-)448 4459 y(able)c(assumption.)48 b(With)33 b(these)h(restrictions,)f(determining)f(whether)g(the)i(link) -5 b(age)448 4572 y(can)34 b(b)s(e)g(em)m(b)s(edded)e(with)h(its)g(v)m (ertices)i(on)e(in)m(teger)i(lattice)f(p)s(oin)m(ts)e(can)j(b)s(e)e (done)g(in)448 4685 y(p)s(olynomial)28 b(time.)589 4798 y(W)-8 b(e)24 b(de\014ne)f(a)g(subgraph,)g Fk(P)30 b Fo(=)23 b Fl(l)1690 4812 y Fj(1)1729 4798 y Fl(;)15 b(:)g(:)g(:)i(l) 1918 4812 y Fi(n)1965 4798 y Fo(,)24 b(of)f(a)h(link)-5 b(age)22 b(to)h(b)s(e)g(a)g(p)s(olygon)f(if)f(the)i(set)448 4911 y(of)g(v)m(ertices)g(in)f Fk(P)30 b Fo(plus)20 b(its)i(induced)f (set)i(of)g(edges)g(form)f(a)h(cycle)g(with)e Fl(c)2886 4925 y Fj(1)2951 4911 y Fo(=)k Fl(d)3094 4925 y Fi(n)3141 4911 y Fo(.)39 b(There)1920 5162 y(9)p eop %%Page: 10 10 10 9 bop 448 623 a Fo(are)33 b(p)s(oten)m(tially)d(exp)s(onen)m(tially) h(man)m(y)h(em)m(b)s(eddings,)e(but)i(the)g(y)m(es-no)h(question)e(of) 448 736 y(whether)f(a)h(p)s(olygon)f(can)h(b)s(e)e(em)m(b)s(edded)h(on) g(an)h Fl(m)20 b Fk(\002)g Fl(m)30 b Fo(grid)f(can)i(b)s(e)f(answ)m (ered)g(in)448 848 y(p)s(olynomial)e(time.)448 1049 y Fh(Theorem)34 b(3.1)46 b Fg(F)-7 b(or)33 b(any)f Fo(\001)25 b Fl(>)g Fo(0)p Fg(,)32 b(we)f(c)-5 b(an)32 b(che)-5 b(ck)32 b(if)f(the)h(p)-5 b(olygon)33 b Fl(l)2845 1063 y Fj(1)2885 1049 y Fl(;)15 b(:)g(:)g(:)h(;)f(l)3113 1063 y Fi(n)3192 1049 y Fg(c)-5 b(an)32 b(b)-5 b(e)448 1162 y(emb)g(e)g(dde)g(d)38 b(in)d(an)i Fl(m)22 b Fk(\002)g Fl(m)35 b Fg(grid)h(in)g(time)g Fl(O)s Fo(\()p Fl(nm)2166 1129 y Fj(4+\001)2318 1162 y Fo(\))p Fg(.)51 b(We)36 b(c)-5 b(an)36 b(c)-5 b(ompute)37 b(whether)448 1275 y(this)g(p)-5 b(olygon)38 b(c)-5 b(an)36 b(b)-5 b(e)36 b(emb)-5 b(e)g(dde)g(d)38 b(starting)f(at)f(a)g(given)f(initial)i(p)-5 b(oint)37 b Fo(\()p Fl(k)s(;)15 b(l)r Fo(\))37 b Fg(in)f(time)448 1388 y Fl(O)s Fo(\()p Fl(nm)690 1355 y Fj(2+\001)843 1388 y Fo(\))p Fg(.)448 1612 y Fh(Pro)s(of)d Fo(Let)g Fl(\025)f Fo(denote)g(the)g(empt)m(y)h(string.)44 b(In)32 b(the)g(algorithm)f(b)s(elo)m(w)g(w)m(e)i(compute)448 1725 y(the)e(follo)m(wing)e(set)i(of)f(matrices,)h(for)f Fl(i)c Fo(=)e(0)p Fl(;)15 b(:)g(:)g(:)j(;)d(n)30 b Fo(for)g(all)f (initial)f(p)s(oin)m(ts)h(\()p Fl(k)s(;)15 b(l)r Fo(\):)810 2033 y Fl(M)908 1989 y Fi(k)r(;l)898 2061 y(l)919 2070 y Fd(1)954 2061 y Fi(:::)o(l)1034 2071 y Fe(i)1064 2033 y Fo(\()p Fl(s;)g(t)p Fo(\))26 b(=)1372 1836 y Fc(8)1372 1911 y(>)1372 1936 y()1372 2110 y(:)1487 1920 y Fo(1)84 b(if)29 b(link)-5 b(age)30 b Fl(l)2032 1934 y Fj(1)2087 1920 y Fl(:)15 b(:)g(:)h(l)2235 1934 y Fi(i)2293 1920 y Fo(can)31 b(b)s(e)f(em)m(b)s(edded)1646 2033 y(starting)g(at)q(\()p Fl(k)s(;)15 b(l)r Fo(\))32 b(and)d(ending)g(at)q(\()p Fl(s;)15 b(t)p Fo(\))1487 2146 y(0)84 b(otherwise)448 2382 y Fh(Algorithm)35 b(3.1:)448 2495 y(Input:)40 b Fo(p)s(olygon)30 b Fk(P)j Fo(=)25 b Fl(l)1335 2509 y Fj(1)1374 2495 y Fl(;)15 b(:)g(:)g(:)i(;)e(l)1603 2509 y Fi(n)1650 2495 y Fo(,)31 b(in)m(teger)g Fl(m)448 2608 y Fh(Output:)40 b Fo(1)31 b(i\013)e Fk(P)38 b Fo(can)31 b(b)s(e)f(em)m(b)s(edded)f(in)g(the)i Fl(m)20 b Fk(\002)f Fl(m)31 b Fo(grid.)559 2786 y(1.)47 b(ans)30 b(:=)g(0)559 2969 y(2.)47 b(for)30 b(all)f(\()p Fl(k)s(;)15 b(l)r(;)g(s;)g(t)p Fo(\))27 b Fk(2)e(f)p Fo(1)p Fl(;)15 b(:)g(:)g(:)i(;)e(m)p Fk(g)31 b Fo(do)f(in)f(parallel)g Fk(f)559 3219 y Fo(3.)347 b Fl(M)1074 3174 y Fi(k)r(;l)1064 3247 y(\025)1158 3219 y Fo(\()p Fl(s;)15 b(t)p Fo(\))26 b(=)1466 3075 y Fc(\()1574 3162 y Fo(1)83 b(if)30 b(\()p Fl(k)s(;)15 b(l)r Fo(\))26 b(=)f(\()p Fl(s;)15 b(t)p Fo(\))1574 3275 y(0)83 b(otherwise)559 3463 y(4.)347 b(for)30 b Fl(i)25 b Fo(=)g(1)p Fl(;)15 b(:)g(:)g(:)i(;)e(n)31 b Fo(do:)559 3763 y(5.)497 b Fl(M)1224 3719 y Fi(k)r(;l)1214 3791 y(l)1235 3800 y Fd(1)1269 3791 y Fi(:::)o(l)1349 3801 y Fe(i)1380 3763 y Fo(\()p Fl(s;)15 b(t)p Fo(\))26 b(=)1688 3566 y Fc(8)1688 3641 y(>)1688 3665 y()1688 3840 y(:)1803 3639 y Fo(1)83 b(if)30 b Fk(9)p Fo(\()p Fl(u;)15 b(v)s Fo(\))31 b(reac)m(hable)g(from)f(\()p Fl(s;)15 b(t)p Fo(\))31 b(via)e Fl(l)3315 3653 y Fi(i)1962 3763 y Fo(suc)m(h)h(that)h Fl(M)2462 3719 y Fi(k)r(;l)2452 3791 y(l)2473 3800 y Fd(1)2508 3791 y Fi(:::)n(l)2587 3801 y Fe(i)p Fn(\000)p Fd(1)2696 3763 y Fo(\()p Fl(u;)15 b(v)s Fo(\))27 b(=)e(1)1803 3887 y(0)83 b(otherwise)559 4090 y(6.)347 b(if)29 b Fl(M)1157 4046 y Fi(k)r(;l)1147 4118 y(l)1168 4127 y Fd(1)1203 4118 y Fi(:::)o(l)1283 4126 y Fe(n)1329 4090 y Fo(\()p Fl(k)s(;)15 b(l)r Fo(\))27 b(=)e(1)30 b(then)h(ans)f(:=)g(1)h Fk(g)559 4274 y Fo(7.)47 b(return\(ans\))589 4452 y(It)21 b(is)f(easy)h(to)g(sho)m(w)f(b)m(y)h(induction)d(on)i Fl(i)h Fo(that)g(Algorithm)e(3.1)j(correctly)f(computes)448 4565 y(the)31 b(matrices)f Fl(M)1067 4521 y Fi(k)r(;l)1057 4593 y(l)1078 4602 y Fd(1)1113 4593 y Fi(:::)o(l)1193 4603 y Fe(i)1223 4565 y Fo(.)41 b(Th)m(us)29 b(the)i(algorithm)e(pro)s (duces)g(the)i(correct)h(answ)m(er.)589 4687 y(The)j(running)d(time)i (is)g Fl(nm)1566 4654 y Fj(4)1639 4687 y Fo(times)h(the)f(time)h(to)g (compute)g(step)g(5)g(for)g(a)g(\014xed)448 4800 y Fl(k)s(;)15 b(l)r(;)g(s;)g(t)p Fo(,)32 b(and)d Fl(i)p Fo(.)41 b(P)m(oin)m(t)31 b(\()p Fl(s;)15 b(t)p Fo(\))30 b(is)g(reac)m(hable)g(from)g(at)h(most)g Fl(r)2596 4814 y Fj(2)2635 4800 y Fo(\()p Fl(l)2699 4767 y Fj(2)2697 4825 y Fi(i)2739 4800 y Fo(\))g(p)s(oin)m(ts)e(\()p Fl(u;)15 b(v)s Fo(\))31 b(via)448 4913 y(link)e Fl(l)655 4927 y Fi(i)683 4913 y Fo(.)41 b(Th)m(us)29 b(the)h(time)h(for)f(this)f (step)h(is)g(b)s(ounded)e(b)m(y)i Fl(O)s Fo(\()p Fl(r)2588 4927 y Fj(2)2628 4913 y Fo(\()p Fl(l)2692 4880 y Fj(2)2690 4937 y Fi(i)2732 4913 y Fo(\)\).)1897 5162 y(10)p eop %%Page: 11 11 11 10 bop 589 623 a Fo(W)-8 b(e)26 b(kno)m(w)f(from)g(Theorem)f(2.5)i (that)f(for)g(su\016cien)m(tly)e(large)i Fl(l)2719 637 y Fi(i)2747 623 y Fo(,)i Fl(r)2840 637 y Fj(2)2879 623 y Fo(\()p Fl(l)2943 590 y Fj(2)2941 647 y Fi(i)2983 623 y Fo(\))e Fl()g Fo(0)p Fg(.)42 b(If)31 b(we)g(must)g(start)i(the)448 848 y(emb)-5 b(e)g(dding)34 b(at)f(a)g(sp)-5 b(e)g(ci\014c)34 b(lattic)-5 b(e)33 b(p)-5 b(oint)34 b(then)f(the)g(running)g(time)g(is)f Fl(O)s Fo(\()p Fl(bm)3110 815 y Fj(2)p Fi(e)p Fj(+\001)3296 848 y Fo(\))448 1086 y Fh(Pro)s(of)d Fo(Start)g(b)m(y)f(building)c(the) 29 b(depth-\014rst)e(searc)m(h)i(tree)g(for)f Fk(B)s Fo(.)39 b(Let)29 b Fl(c)2952 1100 y Fj(1)3020 1086 y Fo(b)s(e)e(the)i(end)448 1199 y(p)s(oin)m(t)h(of)h(the)g(\014rst)f(bac) m(k)m(edge)i(that)f(w)m(e)h(encoun)m(ter.)42 b(Th)m(us,)30 b(the)g(path)h(from)f Fl(c)3185 1213 y Fj(1)3255 1199 y Fo(bac)m(k)448 1312 y(to)j(itself)e(is)g(the)h(\014rst)f(p)s(olygon)g (that)i(w)m(e)f(ha)m(v)m(e)h(encoun)m(tered,)h(call)d(it)g Fk(P)2972 1326 y Fj(1)3012 1312 y Fo(.)45 b(Let)33 b(\()p Fl(k)s(;)15 b(l)r Fo(\))448 1425 y(b)s(e)34 b(a)h(candidate)f(placemen) m(t)g(for)g(v)m(ertex)i Fl(c)1971 1439 y Fj(1)2010 1425 y Fo(.)53 b(By)34 b(Corollary)f(3.3)i(w)m(e)g(can)g(compute)448 1538 y(the)44 b(matrices)g Fl(G)1068 1505 y Fi(k)r(;l)1068 1560 y(c)1099 1570 y Fe(i)1196 1538 y Fo(for)f(all)g(v)m(ertices)h Fl(c)1869 1552 y Fi(i)1942 1538 y Fo(from)f Fk(P)2233 1552 y Fj(1)2273 1538 y Fo(.)81 b(These)43 b(tell)g(us)g(the)h(p)s (ossible)448 1650 y(placemen)m(ts)31 b(of)g Fk(P)1083 1664 y Fj(1)1153 1650 y Fo(when)e(it)h(is)f(started)i(at)g(\()p Fl(k)s(;)15 b(l)r Fo(\).)589 1763 y(No)m(w)24 b(the)f(situation)f(gro)m (ws)h(more)g(complicated.)38 b(W)-8 b(e)24 b(need)e(to)i(c)m(hec)m(k)g (if)e(the)h(p)s(oly-)448 1876 y(gons)k(for)f(whic)m(h)g(w)m(e)h(ha)m(v) m(e)h(computed)e(em)m(b)s(eddings)f(can)i(b)s(e)f(compatibly)f(em)m(b)s (edded)448 1989 y(with)e(the)g(other)h(p)s(olygons)f(of)h(the)f (biconnected)h(comp)s(onen)m(t.)38 b(W)-8 b(e)25 b(can)f(compute)g(the) 448 2102 y(matrices)32 b Fl(G)886 2116 y Fi(i)945 2102 y Fo(for)f(eac)m(h)h(of)g(the)f(other)h(p)s(olygons;)f(the)g(question)g (is)f(ho)m(w)h(to)h(com)m(bine)448 2215 y(them)39 b(to)h(determine)f (if)f(there)h(is)f(a)i(sim)m(ultaneously)d(compatible)h(em)m(b)s (edding)f(for)448 2328 y(the)31 b(link)-5 b(age)29 b(as)i(a)g(whole.)40 b(W)-8 b(e)31 b(mak)m(e)h(sev)m(eral)e(observ)-5 b(ations:)585 2540 y Fk(\017)46 b Fo(Eac)m(h)34 b(new)g(p)s(olygon)f(can)i(b)s(e)e (uniquely)f(iden)m(ti\014ed)g(b)m(y)i(its)f(bac)m(k)i(edge)g(in)e(the) 676 2653 y(depth)c(\014rst)h(tra)m(v)m(ersal.)585 2841 y Fk(\017)46 b Fo(This)28 b(bac)m(k)j(edge)g(closes)g(the)f(section)h (of)g(the)f(tree)h(in)m(to)g(a)f(p)s(olygon.)585 3029 y Fk(\017)46 b Fo(There)26 b(are)g(at)i(most)e Fl(m)1488 2996 y Fj(2)1554 3029 y Fo(lattice)h(p)s(oin)m(ts)e(on)h(whic)m(h)g (the)g(endp)s(oin)m(t)f(of)i(the)f(bac)m(k)676 3142 y(edge)31 b(ma)m(y)g(to)g(lie.)589 3354 y(T)-8 b(o)40 b(c)m(hec)m(k)g(if)d(a)i (new)g(p)s(olygon,)h Fk(P)1798 3368 y Fi(j)1834 3354 y Fo(,)h(has)e(a)g(compatible)f(em)m(b)s(edding)f(with)g(the)448 3467 y(link)-5 b(age,)26 b(w)m(e)f(consider)f(all)g(p)s(ossible)f(p)s (ositions)g(of)i(the)h(end)e(p)s(oin)m(t)g(of)h(its)g(bac)m(k)m(edge)i Fl(c)3375 3481 y Fi(j)3412 3467 y Fo(,)448 3580 y(and)d(c)m(hec)m(k)i (whether)d(an)m(y)i(lead)f(to)h(an)f(em)m(b)s(edding.)37 b(\(In)24 b(practice,)i(w)m(e)e(simply)e(record)448 3693 y(the)33 b(curren)m(t)f(p)s(osition)e(of)i Fl(c)1417 3707 y Fi(j)1486 3693 y Fo(and)g(bac)m(ktrac)m(k)i(to)f(c)m(hec)m(k)h (that)f(there)f(is)f(a)i(consisten)m(t)448 3806 y(p)s(ositioning)42 b(of)i(the)h(endp)s(oin)m(ts)d(of)j(all)e(lo)m(w)m(er-n)m(um)m(b)s (ered)g(bac)m(k)m(edges.)85 b(The)44 b(v)-5 b(ast)448 3919 y(ma)5 b(jorit)m(y)37 b(of)h(the)f Fl(m)1180 3886 y Fj(2\()p Fi(e)p Fu(\000)p Fj(1\))1434 3919 y Fo(conceiv)-5 b(able)37 b(placemen)m(ts)g(of)g(all)f(these)h(endp)s(oin)m(ts)f(will) 448 4032 y(b)s(e)28 b(eliminated)f(without)h(bac)m(ktrac)m(king)h(v)m (ery)g(deeply)-8 b(.)40 b(Th)m(us)27 b(the)i Fl(m)2857 3999 y Fj(2\()p Fi(e)p Fu(\000)p Fj(1\))3103 4032 y Fo(factor)g(in)448 4144 y(the)c(w)m(orst)h(case)g(upp)s(er)d(b)s(ound)f(is)i(a)i (signi\014can)m(t)d(o)m(v)m(er-estimate)28 b(of)d(the)g(true)g(running) 448 4257 y(time.\))589 4370 y(Th)m(us)c(what)g(w)m(e)g(do)h(is)e(tra)m (v)m(el)i(the)f(dfs)g(tree,)j(computing)c(all)g(p)s(ossible)f(em)m(b)s (eddings)448 4483 y(of)32 b(eac)m(h)h(of)f(the)g(asso)s(ciated)g(bac)m (k-edge)h(endp)s(oin)m(ts.)43 b(There)31 b(are)h Fl(e)g Fo(of)g(them.)44 b(Hence)448 4596 y(w)m(e)31 b(ha)m(v)m(e)h(a)f (running)c(time)j(of)h Fl(O)s Fo(\()p Fl(bm)1743 4563 y Fj(2+2)p Fi(e)p Fj(+\001)2019 4596 y Fo(\))g(steps.)1061 b Ff(2)589 4759 y Fo(W)-8 b(e)36 b(no)m(w)f(\014nish)d(the)i(algorithm) g(to)h(decide)f(whether)f(a)i(general)g(link)-5 b(age,)35 b Fk(L)p Fo(,)g(is)448 4872 y(em)m(b)s(eddable.)j(W)-8 b(e)28 b(tra)m(v)m(erse)g(a)f(depth-\014rst)e(searc)m(h)i(tree)g(of)g Fk(L)f Fo(in)f(p)s(ostorder)h(fashion,)1897 5162 y(13)p eop %%Page: 14 14 14 13 bop 448 623 a Fo(computing)36 b(the)h(p)s(ossible)d(em)m(b)s (eddings)h(of)i(eac)m(h)h(biconnected)f(comp)s(onen)m(t)g(as)g(w)m(e) 448 736 y(go.)42 b(The)30 b(general)g(link)-5 b(age)30 b(algorithm)f(follo)m(ws)h(from)f(Theorem)i(3.5.)448 948 y Fh(Theorem)j(3.6)46 b Fg(Supp)-5 b(ose)28 b(a)e(linkage)g Fk(L)g Fg(has)h Fl(n)f Fg(links)g(and)h(e)-5 b(ach)27 b(bic)-5 b(onne)g(cte)g(d)27 b(c)-5 b(omp)g(o-)448 1061 y(nent)26 b(has)h(at)f(most)g Fl(e)g Fg(b)-5 b(ack)26 b(e)-5 b(dges)26 b(in)f(the)h(depth-\014rst)h(se)-5 b(ar)g(ch)27 b(tr)-5 b(e)g(e)27 b(of)e Fk(L)p Fg(.)40 b(The)25 b(pr)-5 b(oblem)448 1174 y(of)32 b(emb)-5 b(e)g(dding)33 b Fk(L)e Fg(on)h(an)g Fl(m)18 b Fk(\002)g Fl(m)31 b Fg(inte)-5 b(ger)32 b(lattic)-5 b(e)33 b(is)e(c)-5 b(omputable)34 b(in)d Fl(O)s Fo(\()p Fl(nm)3126 1141 y Fj(2)p Fi(e)p Fj(+2+\001)3402 1174 y Fo(\))448 1287 y Fg(steps,)j(for)f(any)g Fo(\001)25 b Fl(>)g Fo(0)p Fg(.)448 1524 y Fh(Pro)s(of)32 b Fo(This)c(is)i(no)m(w)g(straigh)m(tforw)m(ard)g(using)f(Theorem)h (3.5.)589 1637 y(First,)f(compute)g(the)g(depth-\014rst)f(searc)m(h)i (tree)f(of)g Fk(L)g Fo(including)c(its)j(biconnected)448 1750 y(comp)s(onen)m(ts.)60 b(Second,)39 b(w)m(e)e(tra)m(v)m(erse)h (the)f(tree)g(from)g(lea)m(v)m(es)h(to)f(ro)s(ot,)i(computing)448 1863 y(the)31 b(matrix)448 2110 y Fl(A)516 2124 y Fi(v)557 2110 y Fo(\()p Fl(i;)15 b(j)5 b Fo(\))28 b(=)864 1966 y Fc(\()972 2053 y Fo(1)84 b(if)29 b(the)h(tree)i(ro)s(oted)e(at)h Fl(v)j Fo(ma)m(y)d(b)s(e)f(em)m(b)s(edded)f(at)i(p)s(osition)d(\()p Fl(i;)15 b(j)5 b Fo(\))972 2166 y(0)84 b Fl(other)s(w)r(ise)589 2374 y Fo(When)28 b(the)g(matrices)g Fl(A)1436 2388 y Fi(v)1505 2374 y Fo(for)g(all)e(the)i(v)m(ertices)h Fl(v)i Fo(b)s(elo)m(w)c(a)h(biconnected)g(comp)s(o-)448 2487 y(nen)m(t)g Fl(C)35 b Fo(ha)m(v)m(e)29 b(b)s(een)e(computed,)h(w)m(e)h (compute)f(the)g(p)s(ossible)d(p)s(ositions)h(for)i(the)g(ro)s(ot)448 2600 y(of)j Fl(C)36 b Fo(using)29 b(Theorem)h(3.5.)42 b(In)29 b(this)h(w)m(a)m(y)-8 b(,)31 b(w)m(e)g(pro)s(ceed)f(up)f(the)i (tree.)41 b(The)30 b(required)448 2713 y(time)36 b(is)g Fl(O)s Fo(\()p Fl(bm)985 2680 y Fj(2)p Fi(e)p Fj(+2+\001)1261 2713 y Fo(\))g(for)g(eac)m(h)i(biconnected)e(comp)s(onen)m(t)g(of)h (size)f Fl(b)p Fo(.)59 b(Th)m(us)35 b(the)448 2826 y(total)c(is)f Fl(O)s Fo(\()p Fl(nm)999 2793 y Fj(2)p Fi(e)p Fj(+2+\001)1275 2826 y Fo(\))g(as)h(claimed.)1588 b Ff(2)589 2989 y Fo(Up)23 b(to)h(no)m(w)f(w)m(e)h(ha)m(v)m(e)g(ignored)e(the)h(issue)f(of)i (links)c(that)k(con)m(tain)f(v)m(ertices)h(in)e(their)448 3102 y(in)m(terior.)38 b(A)24 b(sligh)m(t)g(mo)s(di\014cation)e(of)j (the)f(ab)s(o)m(v)m(e)h(algorithms)f(handles)e(this)h(problem.)448 3215 y(Let)k Fl(l)634 3229 y Fi(i)689 3215 y Fo(b)s(e)f(a)h(link)d (with)i(endp)s(oin)m(ts)e Fl(c)j Fo(and)f Fl(d)h Fo(and)f(in)m(ternal)f (p)s(oin)m(ts)h Fl(a)2806 3229 y Fj(1)2845 3215 y Fl(;)15 b(:)g(:)g(:)i(;)e(a)3095 3230 y Fi(k)3138 3215 y Fo(.)39 b(When)448 3328 y(w)m(e)32 b(tra)m(v)m(el)g(from)e Fl(c)i Fo(to)f Fl(a)1284 3342 y Fj(1)1355 3328 y Fo(along)g(the)g (depth-\014rst)f(searc)m(h)h(tree,)i(w)m(e)e(w)m(ould)f(normally)448 3440 y(establish)d(the)i(arra)m(y)f Fl(G)1283 3454 y Fi(a)1320 3463 y Fd(1)1387 3440 y Fo(indicating)f(p)s(ossible)e (placemen)m(ts)k(of)g(the)f(v)m(ertex)i Fl(a)3193 3454 y Fj(1)3260 3440 y Fo(with)448 3553 y(resp)s(ect)40 b(to)g Fl(G)961 3567 y Fi(c)995 3553 y Fo(.)68 b(Instead)39 b(w)m(e)h(w)m(an)m(t)g(to)h(establish)c Fl(G)2368 3567 y Fi(a)2405 3576 y Fd(1)2444 3553 y Fl(;)15 b(:)g(:)g(:)i(;)e(G)2718 3567 y Fi(a)2755 3579 y Fe(k)2797 3553 y Fo(,)42 b Fl(G)2936 3568 y Fi(d)2976 3553 y Fo(,)g(indicating)448 3666 y(p)s(ossible)f (placemen)m(ts)i(of)g(the)g(en)m(tire)f(link.)76 b(This)41 b(amoun)m(ts)i(to)h(\014nding)c(p)s(ossible)448 3779 y(p)s(oin)m(ts)28 b(for)h Fl(d)h Fo(and)e(also)h(c)m(hec)m(king)h(that) g(the)f Fl(a)2055 3793 y Fi(i)2084 3779 y Fo('s)g(land)f(on)h(allo)m(w) m(able)f(lattice)i(p)s(oin)m(ts.)448 3892 y(This)f(mo)s(di\014cation)g (do)s(es)h(not)g(a\013ect)i(the)f(running)c(time)k(of)f(the)h (algorithm.)589 4005 y(These)g(results)e(can)h(b)s(e)g(extended)g(to)i (higher)d(dimensions,)f(noting)h(that:)448 4218 y Fh(Theorem)34 b(3.7)46 b Fg(\([5)q(],)38 b(pp.)58 b(310-311\))40 b(A)n(n)d(inte)-5 b(ger)38 b Fl(n)f Fg(c)-5 b(an)38 b(b)-5 b(e)38 b(written)h(as)f(the)g (sum)448 4330 y(of)33 b(thr)-5 b(e)g(e)34 b(squar)-5 b(es)33 b(if)g(and)g(only)h(if)e Fl(n)25 b Fk(6)p Fo(=)g(4)1868 4297 y Fi(\013)1918 4330 y Fo(\(8)p Fl(m)c Fo(+)f(7\))p Fg(.)448 4543 y Fh(Theorem)34 b(3.8)46 b Fg(\([5)q(],)39 b(p)-5 b(g.)58 b(369.\))h(Every)37 b(inte)-5 b(ger)38 b(c)-5 b(an)39 b(b)-5 b(e)37 b(written)i(as)f(the)h(sum)f(of)448 4656 y(four)33 b(squar)-5 b(es.)1897 5162 y Fo(14)p eop %%Page: 15 15 15 14 bop 448 623 a Fp(4)135 b(What)45 b(is)g(the)h(Minimal)f Fb(\017)p Fp(?)448 826 y Fo(W)-8 b(e)37 b(b)s(egin)c(with)h(trees)i(in) e(t)m(w)m(o)j(dimensions.)52 b(By)36 b(Theorem)e(2.1)j(and)d(Lemma)i (2.6,)448 939 y(a)f(tree)h Fl(T)47 b Fo(is)34 b(em)m(b)s(eddable)g (whenev)m(er)g(eac)m(h)i(of)f(its)f(links)f(is)h(the)h(square)f(ro)s (ot)h(of)g(an)448 1051 y(in)m(teger)e(that)g(can)f(b)s(e)f(written)h (as)g(the)g(sum)g(of)g(t)m(w)m(o)h(squares.)46 b(Clearly)31 b(eac)m(h)i(link)d(is)448 1164 y(no)38 b(more)f(than)g(1)p Fl(=)p Fo(2)i(a)m(w)m(a)m(y)g(from)e(an)g(in)m(teger,)i(i.e.,)h(the)d (square)g(ro)s(ot)h(of)f(a)h(p)s(erfect)448 1277 y(square.)49 b(Can)33 b(it)g(b)s(e)g(as)g(m)m(uc)m(h)g(as)h(1)p Fl(=)p Fo(2)g(a)m(w)m(a)m(y)h(from)e(the)h(square)f(ro)s(ot)g(of)h(an)f(in)m (teger)448 1390 y(that)d(can)g(b)s(e)e(written)h(as)g(sum)f(of)i(t)m(w) m(o)g(squares?)40 b(Can)29 b(it)f(b)s(e)h(the)g(case)i(that)f(there)f (is)448 1503 y(an)g(in)m(teger)h Fl(m)f Fo(suc)m(h)g(that)h(there)g (are)f(no)g(in)m(tegers)h(b)s(et)m(w)m(een)g Fl(m)2655 1470 y Fj(2)2723 1503 y Fo(and)f(\()p Fl(m)18 b Fo(+)g(1\))3201 1470 y Fj(2)3270 1503 y Fo(that)448 1616 y(can)31 b(b)s(e)f(written)f (as)i(the)f(sum)g(of)g(t)m(w)m(o)i(squares?)448 1825 y Fh(Theorem)i(4.1)46 b Fg(\(Bamb)-5 b(ah)29 b(and)e(Chow)5 b(la,)29 b([2]\))d(L)-5 b(et)27 b Fl(s)2327 1839 y Fi(i)2381 1825 y Fg(b)-5 b(e)26 b(the)h Fl(i)2662 1792 y Fi(th)2759 1825 y Fg(inte)-5 b(ger)26 b(which)h(c)-5 b(an)448 1954 y(b)g(e)33 b(expr)-5 b(esse)g(d)34 b(as)f(the)g(sum)g(of)g(two)h(squar) -5 b(es.)42 b(Then)33 b Fl(s)2329 1968 y Fi(n)p Fj(+1)2486 1954 y Fk(\000)20 b Fl(s)2620 1968 y Fi(n)2692 1954 y Fo(=)25 b Fl(O)s Fo(\()p Fl(s)2938 1906 y Fj(1)p Fi(=)p Fj(4)2938 1965 y Fi(n)3048 1954 y Fo(\))p Fg(.)589 2163 y Fo(This)k(theorem)i(will)d(answ)m(er)i(the)g(case)i(for)e(em)m(b)s (edding)f(trees.)448 2373 y Fh(Theorem)34 b(4.2)46 b Fg(L)-5 b(et)36 b Fk(T)22 b Fo(=)30 b Fl(t)1437 2387 y Fj(1)1491 2373 y Fl(:)15 b(:)g(:)h(t)1645 2387 y Fi(n)1727 2373 y Fg(b)-5 b(e)35 b(a)g(tr)-5 b(e)g(e.)50 b(Then)36 b(the)f(minimal)h Fl(\017)f Fg(such)g(that)h Fk(T)448 2486 y Fg(c)-5 b(an)42 b(b)-5 b(e)41 b Fl(\017)p Fg(-emb)-5 b(e)g(dde)g(d)42 b(in)f(the)h(inte)-5 b(ger)41 b(lattic)-5 b(e)42 b(c)-5 b(an)42 b(b)-5 b(e)40 b(determine)-5 b(d)43 b(in)e Fl(O)s Fo(\(\()p Fl(t)3155 2500 y Fj(1)3195 2486 y Fo(\))3230 2453 y Fj(3)p Fi(=)p Fj(4)3366 2486 y Fo(+)448 2598 y Fl(:)15 b(:)g(:)22 b Fo(+)d(\()p Fl(t)733 2612 y Fi(n)781 2598 y Fo(\))816 2565 y Fj(3)p Fi(=)p Fj(4)926 2598 y Fo(\))33 b Fg(steps.)448 2832 y Fh(Pro)s(of)c Fo(By)e(Theorem)g(2.1,)j(it)d(su\016ces)g(to)h(consider)f(eac)m(h)h (link)d(separately)-8 b(.)41 b(Supp)s(ose)448 2945 y(link)29 b Fl(t)i Fo(cannot)h(b)s(e)f(em)m(b)s(edded.)42 b(This)29 b(means)i Fl(t)2103 2912 y Fj(2)2173 2945 y Fo(cannot)h(b)s(e)f (expressed)f(as)i(the)f(sum)448 3058 y(of)g(t)m(w)m(o)h(squares.)589 3171 y(Let)i Fl(t)788 3138 y Fu(0)844 3171 y Fo(b)s(e)f(the)g(in)m (teger)g(closest)h(to)g Fl(t)1872 3138 y Fj(2)1911 3171 y Fo(;)h(w)m(e)e(ha)m(v)m(e)h Fk(j)p Fl(t)2377 3138 y Fu(0)2423 3171 y Fk(\000)22 b Fl(t)2549 3138 y Fj(2)2588 3171 y Fk(j)30 b(\024)f Fo(1)p Fl(=)p Fo(2)p Fl(:)35 b Fo(By)e(Theorem)448 3284 y(4.1,)j(there)e(is)f(an)h(in)m(teger)g Fl(r)j Fo(suc)m(h)c(that)h Fk(j)p Fl(r)26 b Fk(\000)c Fl(t)2093 3251 y Fu(0)2116 3284 y Fk(j)31 b Fl(