(original) (raw)

%!PS-Adobe-2.0 %%Creator: dvipsk 5.58a Copyright 1986, 1994 Radical Eye Software %%Title: stoc.dvi %%Pages: 10 %%PageOrder: Ascend %%BoundingBox: 0 0 612 792 %%DocumentFonts: Times-Bold Times-Roman Times-Italic Courier %%DocumentPaperSizes: Letter %%EndComments %DVIPSCommandLine: dvips -o -o stoc.ps stoc.dvi %DVIPSParameters: dpi=300, compressed, comments removed %DVIPSSource: TeX output 1997.03.06:0135 %%BeginProcSet: texc.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]/id ch-image N /rw ch-width 7 add 8 idiv string N /rc 0 N /gp 0 N /cp 0 N{rc 0 ne{rc 1 sub /rc X rw}{G}ifelse}imagemask restore}B /G{{id gp get /gp gp 1 add N dup 18 mod S 18 idiv pl S get exec}loop}B /adv{cp add /cp X}B /chg{rw cp id gp 4 index getinterval putinterval dup gp add /gp X adv}B /nd{/cp 0 N rw exit}B /lsh{rw cp 2 copy get dup 0 eq{pop 1}{ dup 255 eq{pop 254}{dup dup add 255 and S 1 and or}ifelse}ifelse put 1 adv}B /rsh{rw cp 2 copy get dup 0 eq{pop 128}{dup 255 eq{pop 127}{dup 2 idiv S 128 and or}ifelse}ifelse put 1 adv}B /clr{rw cp 2 index string putinterval adv}B /set{rw cp fillstr 0 4 index getinterval putinterval adv}B /fillstr 18 string 0 1 17{2 copy 255 put pop}for N /pl[{adv 1 chg} {adv 1 chg nd}{1 add chg}{1 add chg nd}{adv lsh}{adv lsh nd}{adv rsh}{ adv rsh nd}{1 add adv}{/rc X nd}{1 add set}{1 add clr}{adv 2 chg}{adv 2 chg nd}{pop nd}]dup{bind pop}forall N /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: texps.pro TeXDict begin /rf{findfont dup length 1 add dict begin{1 index /FID ne 2 index /UniqueID ne and{def}{pop pop}ifelse}forall[1 index 0 6 -1 roll exec 0 exch 5 -1 roll VResolution Resolution div mul neg 0 0]/Metrics exch def dict begin Encoding{exch dup type /integertype ne{pop pop 1 sub dup 0 le{pop}{[}ifelse}{FontMatrix 0 get div Metrics 0 get div def} ifelse}forall Metrics /Metrics currentdict end def[2 index currentdict end definefont 3 -1 roll makefont /setfont load]cvx def}def /ObliqueSlant{dup sin S cos div neg}B /SlantFont{4 index mul add}def /ExtendFont{3 -1 roll mul exch}def /ReEncodeFont{/Encoding exch def}def end %%EndProcSet TeXDict begin 40258431 52099146 1000 300 300 (stoc.dvi) @start /Fa 2 113 df107 D<38070780380598403809E060EBC07014301470EA0380A31460380700E014C01301EB03 80380E8600137C90C7FCA25AA4B4FC1417828F13>112 D E /Fb 81[19 51[15 17 17 25 17 19 10 15 15 19 19 19 19 27 10 17 1[10 19 19 10 17 19 17 19 19 12[21 19 23 1[23 27 25 31 21 1[17 12 27 27 23 1[27 25 23 23 6[12 19 2[19 19 1[19 19 19 19 1[9 12 9 5[29 38[{}55 37.500000 /Times-Italic rf /Fc 78[19 2[21 51[17 19 19 27 19 19 10 15 12 1[19 19 19 29 10 19 10 10 19 19 12 17 19 17 19 17 3[12 1[12 1[27 1[35 27 27 23 21 25 1[21 27 27 33 23 27 15 12 27 27 21 23 27 25 25 27 6[10 19 19 19 19 19 19 19 19 19 19 10 9 12 9 2[12 12 1[29 38[{}70 37.500000 /Times-Roman rf /Fd 1 4 df<1218A212DB12FF121812FF12DB1218A208097D890F>3 D E /Fe 4 51 df0 D<1204A3EAC460EAF5E0EA3F80EA0E00EA 3F80EAF5E0EAC460EA0400A30B0D7E8D11>3 D<1204120EA2121CA31238A212301270A2 1260A212C0A2070F7F8F0A>48 D50 D E /Ff 5 116 df<1208A21200A4127012 9812B01230A21260126412681270060F7D8E0B>105 D<13C013801300A41207EA198012 11EA0300A41206A4128C12F00A137F8E0C>I110 D114 D<123E124312421270123C120612C21284127808097D880E>I E /Fg 2 51 df<121812F81218AA12FF080D7D8C0E>49 D<123EEA4180EA80C012C01200A2 EA0180EA03001204EA08401230EA7F8012FF0A0D7E8C0E>I E /Fh 6 114 df<1430146014C0EB0180EB03005B130E130C5B1338133013705B5B12015B1203 A290C7FC5A1206120EA2120C121CA312181238A45AA75AB3A31270A77EA41218121CA312 0C120EA2120612077E7FA212017F12007F13701330133813187F130E7F7FEB0180EB00C0 14601430146377811F>18 D<12C012607E7E7E120E7E7E6C7E7F12007F13701330133813 18131CA2130C130E13061307A27F1480A3130114C0A4EB00E0A71470B3A314E0A7EB01C0 A414801303A314005BA21306130E130C131CA213181338133013705B5B12015B48C7FC5A 120E120C5A5A5A5A14637F811F>I88 D90 D<16021606160CA21618A2 1630A21660A216C0A2ED0180A2ED0300A21506A25DA25DA25DA25D1208001C5C123C00CE 495A120E4AC7FC7E1406EA03805CEA01C05C13E000005BA2EB7060A26D5AA2EB1D80A201 1FC8FC7F130E130627327C812A>112 D<16021606A2160CA31618A31630A31660A316C0 A3ED0180A3ED0300A31506A35DA35DA35DA35DA21208001C5C123C127C00DC495A128E12 0E4AC7FC7EA21406EA0380A25CA2EA01C05CA2EA00E05CA3EB7060A36D5AA3EB1D80A301 1FC8FC7FA2130E1306A2274B7C812A>I E /Fi 22 123 df13 DI<13201360A213C0A3EA0180A3EA0300A31206A25AA35AA35AA35A A35AA30B1D7E9511>61 D67 D97 D<123C120C5AA45AEA3380EA3C60EA3020EA6030A4EAC060A2EA40C0EA6080EA2300121E 0C147F930F>I<133C130C1318A41330EA07B0EA0C701210EA30601260A3EAC0C013C8A2 1241EA62D0EA3C700E147E9311>100 DI<1318136C137C136C13C0A3EA07F8EA 00C0EA0180A5EA0300A512021206A2126612E45A12700E1A7F9310>I<12061207120612 00A41238124CA2128C12981218A212301232A21264A2123808147F930C>105 D<1330133813301300A4EA01C0EA0260EA0430136012081200A213C0A4EA0180A4EA6300 12E312C612780D1A81930E>I<121E12065AA45A1338135C139CEA3118EA36001238EA3F 80EA61C0EA60C8A3EAC0D013600E147F9312>I<123C120C1218A41230A41260A412C012 C8A312D0126006147F930A>I<3830F87C38590C86384E0D06EA9C0EEA980C1218A24848 5A15801418A23960301900140E190D7F8C1D>II112 D114 D<1204120CA35AEAFF80EA1800A25AA45A1261A212621264123809127F910D>116 D<38381820004C13701420EA8C3012981218A238306040A314803818B100EA0F1E140D7F 8C18>119 DIII E /Fj 12 112 df<120212041208121812101230122012601240A212C0AA1240A212601220 123012101218120812041202071E7D950D>40 D<1280124012201230121012181208120C 1204A21206AA1204A2120C1208121812101230122012401280071E7E950D>I<1360AAB5 12F0A238006000AA14167E9119>43 D<120C121C12EC120CAFEAFFC00A137D9211>49 D<121FEA60C01360EAF07013301260EA0070A2136013C012011380EA02005AEA08101210 EA2020EA7FE012FF0C137E9211>II<136013E0A2EA01 6012021206120C120812101220126012C0EAFFFCEA0060A5EA03FC0E137F9211>I<387F FFE0B512F0C8FCA6B512F06C13E0140A7E8B19>61 D103 D<12F01230B212FC06147F9309>108 D110 DI E /Fk 24 121 df0 D<137F3803C1E038070070001C131C003C131E0038130E0078130F0070 7F00F01480A50070140000785BA20038130E6C5BA26C5B00061330A20083EB6080008113 40A2394180C100007F13FFA3191D7E9C1E>10 D<1380EA0100120212065AA25AA25AA35A A412E0AC1260A47EA37EA27EA27E12027EEA0080092A7C9E10>40 D<7E12407E12307EA27EA27EA37EA41380AC1300A41206A35AA25AA25A12205A5A092A7E 9E10>I<1306ADB612E0A2D80006C7FCAD1B1C7E9720>43 D48 D<5A1207123F12C71207B3A5EAFFF80D1C7C9B15>III<130CA2131C133CA2135C13DC139C EA011C120312021204120C1208121012301220124012C0B512C038001C00A73801FFC012 1C7F9B15>II<13F0EA03 0CEA0404EA0C0EEA181E1230130CEA7000A21260EAE3E0EAE430EAE818EAF00C130EEAE0 061307A51260A2EA7006EA300E130CEA1818EA0C30EA03E0101D7E9B15>I<1240387FFF 801400A2EA4002485AA25B485AA25B1360134013C0A212015BA21203A41207A66CC7FC11 1D7E9B15>II<007FB512C0B612E0C9FCA8B612E06C14C01B0C7E8F20>61 D<12FEA212C0B3B312FEA207297C9E0C>91 D<12FEA21206B3B312FEA20729809E0C>93 D97 D103 D<12FC121CB3A9EAFF8009 1D7F9C0C>108 D<39FC7E07E0391C838838391D019018001EEBE01C001C13C0AD3AFF8F F8FF8021127F9124>II< EA03F0EA0E1CEA1806487E00701380EA600100E013C0A600601380EA700300301300EA18 06EA0E1CEA03F012127F9115>I<38FF0FE0381E0700EA1C06EA0E046C5AEA039013B0EA 01E012007F12011338EA021C1204EA0C0E487E003C138038FE1FF014127F9116>120 D E /Fl 17 113 df0 D<126012F0A2126004047C8B0C>I20 D<12C012F0123C120FEA03C0EA00F0133C130FEB03C0EB00F0 143C140FEC0380EC0F00143C14F0EB03C0010FC7FC133C13F0EA03C0000FC8FC123C1270 12C0C9FCA7007FB5FCB6128019227D9920>I25 D<1403A26E7E8114001560007FB512F0B67EC8120E81ED01E0ED0078ED01E0ED0380ED06 005DB612F86C5CC812605D4A5AA24AC7FCA225187E952A>41 D50 D<1460A214C0A2EB0180A3EB0300A21306A25BA25BA35BA25BA25B A2485AA248C7FCA31206A25AA25AA25AA35AA25A124013287A9D00>54 D<1304130CEA03CCEA0C38EA1818EA301C133CEA703EEA60361366A2EAE067A213C7A3EA E187A3EAE307A312E6A3EA6606126CEA7C0EEA3C0C1238EA1818EA1C30EA33C0EA3000A2 10237E9F15>59 D<1478381E03BC3823041C3841881E3880D00EEBF00FEB600700C0EB03 80EA60700030EB01C012180008EB00E0000414C0EC0700EB7FF8EB7070128C1288A21270 1200A413601260EAC0E0D840C013400020EB71803911803A00380F001C1B1F7E9D1E>I< EB03F0EB0FF81330EB4078EA0180380300705A000E13E0A2381C018090C7FC5AA21278A2 1270A212F0A514206C1360EB01C0007C1380387E0300EA3F04EA1FF8EA0FE0151E7F9C16 >67 D<496C141001031530A21760496C14E01601010514031607A26EEB0DC00109141901 0814331673496C13E3ED01C3913870038301201403DA78061380150C903940381807EC3C 3815709038801CE0EC1FC0D801001380EC0F000062130E00FE010414C04890C713F0EE03 C0007892C7FC2C1F7F9C32>77 D<0040130200C01306B20060130CA26C1318001C137038 0F01E03803FF803800FE00171A7E981C>91 D<133C13E0EA01C013801203AD13005A121C 12F0121C12077E1380AD120113C0EA00E0133C0E297D9E15>102 D<12F0121C12077E1380AD120113C0EA00E0133C13E0EA01C013801203AD13005A121C12 F00E297D9E15>I<12C0B3B3A502297B9E0C>106 D<164016C0ED0180A2ED0300A21506A2 5DA25DA25DA25DA25DA24A5AA24AC7FC120C003C1306124E008E5B12075CEA03805CA26C 6C5AA26C6C5AA2EB7180A2013BC8FCA2131EA2130CA2222A7E8123>112 D E /Fm 46 123 df<13F8EA030C380E0604EA1C07383803080030138800701390A200E0 13A0A214C01480A3EA6007EB0B8838307190380F80E016127E911B>11 DI<38078010EA1FC0383FE020EA7FF038603040EAC0183880 088012001304EB0500A21306A31304A3130CA35BA45BA21320141B7F9115>I<1338137F EB87803801030090C7FC7FA27F12007FA2137013F8EA03B8EA063CEA0C1C121812381270 A212E0A413181338EA6030EA70606C5AEA0F80111E7F9D12>II<131EEB7180EBC0 C0EA01801203EB00E05AA2380E01C0A31480EA1C0314001306EA1E0CEA3A18EA39E00038 C7FCA25AA45AA25A131B7F9115>26 D<3801FFF85A120F381E1E00EA180EEA38061270A2 EAE00EA3130C131C13185BEA60606C5A001FC7FC15127E9118>I<126012F0A212600404 7C830C>58 D<126012F0A212701210A41220A212401280040C7C830C>II<130113031306A3130CA313 18A31330A31360A213C0A3EA0180A3EA0300A31206A25AA35AA35AA35AA35AA210297E9E 15>I<12E01278121EEA0780EA01E0EA0078131EEB0780EB01E0EB0078141EEC0780A2EC 1E001478EB01E0EB0780011EC7FC1378EA01E0EA0780001EC8FC127812E019187D9520> I<140CA2141CA2143C145CA2149E148EEB010E1302A21304A213081310A2497EEB3FFFEB 40071380A2EA0100A212025AA2001C148039FF803FF01C1D7F9C1F>65 D<48B5FC39003C01C090383800E015F01570A25B15F0A2EC01E09038E003C0EC0780EC1F 00EBFFFC3801C00FEC0780EC03C0A2EA0380A439070007801500140E5C000E1378B512C0 1C1C7E9B1F>I<903801F80890380E0618903838013890386000F048481370485A48C712 30481420120E5A123C15005AA35AA45CA300701302A200305B00385B6C5B6C1360380701 80D800FEC7FC1D1E7E9C1E>I<48B5128039003C01E090383800701538153C151C5B151E A35BA44848133CA3153848481378157015F015E039070001C0EC0380EC0700141C000E13 78B512C01F1C7E9B22>I<48B512F839003C0078013813181510A35BA214081500495AA2 1430EBFFF03801C020A4390380404014001580A23907000100A25C1406000E133EB512FC 1D1C7E9B1F>I<903801F80890380E0618903838013890386000F048481370485A48C712 30481420120E5A123C15005AA35AA2EC7FF0EC07801500A31270140E123012386C131E6C 136438070184D800FEC7FC1D1E7E9C21>71 D<3801FFC038003C001338A45BA45BA4485A A4485AA448C7FCA45AEAFFE0121C7E9B12>73 D79 D<48B5FC39003C03C090383800E015F01570A24913F0A315E0EBE001EC03C0EC0700141E 3801FFF001C0C7FCA3485AA448C8FCA45AEAFFE01C1C7E9B1B>II<3801FFFE39003C03C090383800E015F0 1570A24913F0A3EC01E001E013C0EC0780EC1E00EBFFF03801C038140C140EA2EA0380A4 3807001E1508A2151048130FD8FFE01320C7EA03C01D1D7E9B20>II< 39FFC00FF0391C00038015001402A25C5C121E000E5B143014205CA25C49C7FC120FEA07 025BA25BA25B5BEA03A013C05BA290C8FCA21C1D7D9B18>86 D<3A01FFC0FF803A001E00 3C00011C13306D13205D010F5B6D48C7FC1482EB038414CCEB01D814F05C130080EB0170 EB0278EB04381308EB103CEB201CEB401EEB800E3801000F00027F1206001E497E39FF80 3FF0211C7F9B22>88 D97 D<123F1207A2120EA45AA4EA39E0EA3A30EA3C 1812381270131CA3EAE038A313301370136013C01261EA2300121E0E1D7E9C12>IIIII105 D<1307130FA213061300A61378139CEA010C1202131C12041200A21338A41370A413E0A4 EA01C01261EAF180EAF30012E6127C1024809B11>III<39381F81F0394E20C618394640E81CEB80F0EA8F0000 8E13E0120EA2391C01C038A315703938038071A215E115E23970070064D8300313382012 7E9124>II<380787803809C8603808D03013E0 EA11C014381201A238038070A31460380700E014C0EB0180EB8300EA0E86137890C7FCA2 5AA4123CB4FC151A819115>112 DII<13C01201 A3EA0380A4EAFFF0EA0700A3120EA45AA4EA3820A21340A2EA1880EA0F000C1A80990F> 116 D<001CEBC080392701C1C0124714C03987038040A2120EA2391C070080A3EC0100EA 1806A2381C0E02EB0F04380E13083803E1F01A127E911E>119 D<380787803808C84038 10F0C03820F1E0EBE3C03840E1803800E000A2485AA43863808012F3EB810012E5EA84C6 EA787813127E9118>I<001C13C0EA27011247A238870380A2120EA2381C0700A4EA180E A3EA1C1EEA0C3CEA07DCEA001C1318EA6038EAF0305B485AEA4180003EC7FC121A7E9114 >II E /Fn 81[23 52[21 1[30 21 23 14 16 18 1[23 21 23 35 12 23 1[12 23 21 14 18 23 18 23 21 9[42 2[28 23 30 1[25 32 1[39 28 2[16 32 3[30 30 1[30 6[14 21 21 21 21 21 21 21 21 21 21 1[10 4[14 14 40[{}50 41.666669 /Times-Bold rf /Fo 134[20 2[20 20 20 20 20 2[20 20 20 1[20 20 20 20 1[20 20 20 20 1[20 32[20 17[20 46[{}20 33.333334 /Courier rf /Fp 134[17 17 24 17 17 9 13 11 1[17 17 17 26 9 2[9 17 17 11 15 17 15 17 15 7[24 24 2[24 20 18 22 1[18 24 24 30 3[11 24 24 18 20 24 22 22 24 6[9 17 17 17 17 17 17 17 1[17 17 1[8 11 8 44[{}54 33.333334 /Times-Roman rf /Fq 4 123 df<120CA2EACCC012EDEA7F80EA0C00EA7F80EAEDC012CCEA0C00A20A0B7D8B10>3 D<123C126212C3A212C0124012601238126612C212C3A212431266121C12061202120312 C3A21246123C08167D900E>120 D<1218A512FFA21218AF08167D900E>I<1218A512FF12 18A512001218A412FFA21218A408167D900E>I E /Fr 81[21 51[16 18 18 28 18 21 12 16 16 21 21 21 21 30 12 18 1[12 21 21 12 18 21 18 21 21 12[23 1[25 1[25 1[28 4[14 30 30 25 25 30 28 1[25 6[14 1[21 4[21 21 21 2[10 14 10 2[14 14 14 39[{}49 41.666669 /Times-Italic rf /Fs 80[23 23 51[18 21 21 30 21 21 12 16 14 21 21 21 21 32 12 21 12 12 21 21 14 18 21 18 21 18 3[14 1[14 1[30 1[39 30 30 25 23 28 1[23 30 30 37 25 2[14 30 30 23 25 30 28 28 30 5[12 12 21 21 21 21 21 21 21 21 21 21 1[10 14 10 2[14 14 14 39[{}69 41.666669 /Times-Roman rf /Ft 134[25 1[36 1[28 17 19 22 28 1[25 28 41 14 28 1[14 28 25 17 22 28 22 28 25 12[33 1[36 1[30 3[33 2[19 1[39 2[36 36 33 36 10[25 25 25 25 25 25 49[{}37 50.000001 /Times-Bold rf /Fu 4 123 df<1202A3EAC218EAF278EA3AE0EA0F80A2EA3AE0EAF278EAC218EA0200A3 0D0E7E8E12>3 D<121FEA3080EA6040EAC0C0A21300A212607E120C1233EA6080EAC0C0 1360A31260EA20C0EA1980EA0600EA0180EA00C01360A21260A2EA40C0EA2180EA1F000B 1D7E9610>120 D<1206A8EAFFF0A2EA0600B30C1D7E9611>I<1206A6EAFFF0A2EA0600A6 C7FC1206A6EAFFF0A2EA0600A60C1D7E9611>I E /Fv 61[17 109[30 1[33 4[44 6[28 2[33 67[{}6 50.000001 /Times-Roman rf /Fw 168[38 29 29 24 22 27 2[29 29 35 1[29 16 13 29 2[24 29 2[29 65[{}16 39.999962 /Times-Roman rf /Fx 134[36 2[36 40 24 28 32 2[36 40 60 20 2[20 1[36 24 32 40 32 1[36 14[52 8[28 4[52 52 67[{}21 71.999998 /Times-Bold rf end %%EndProlog %%BeginSetup %%Feature: *Resolution 300dpi TeXDict begin %%PaperSize: Letter %%BeginPaperSize: Letter letter %%EndPaperSize %%EndSetup %%Page: 1 1 1 0 bop 58 95 a Fx(Incr)o(emental)16 b(Clustering)h(and)h(Dynamic)e (Information)h(Retrieval)31 253 y Fv(M)r Fw(O)r(S)r(E)r(S)h Fv(C)r Fw(H)r(A)r(R)r(I)r(K)r(A)r(R)429 235 y Fu(\003)545 253 y Fv(C)r Fw(H)r(A)r(N)r(D)r(R)r(A)f Fv(C)r Fw(H)r(E)r(K)r(U)r(R)r (I)976 235 y Fu(y)1093 253 y Fv(T)q Fw(O)r(M)1198 249 y Fv(\302)1192 253 y Fw(A)r(S)h Fv(F)r Fw(E)r(D)r(E)r(R)1404 235 y Fu(z)1520 253 y Fv(R)r Fw(A)r(J)r(E)r(E)r(V)f Fv(M)r Fw(O)r(T)r(W)n(A)r(N)r(I)1917 235 y Fu(x)-75 453 y Ft(Abstract)-25 555 y Fs(Motivated)c(by)h(applications)f(such)i(as)g(document)g(and)f (image)-75 605 y(classi\256cation)d(in)f(information)f(retrieval,)i(we) g(consider)g(the)g(prob-)-75 655 y(lem)i(of)g(clustering)e Fr(dynamic)i Fs(point)e(sets)i(in)g(a)g(metric)g(space.)23 b(W)m(e)-75 705 y(propose)7 b(a)h(model)g(called)f Fr(incr)n(emental)h (clustering)f Fs(which)g(is)g(based)-75 755 y(on)12 b(a)g(careful)g (analysis)g(of)g(the)f(requirements)h(of)g(the)f(information)-75 805 y(retrieval)c(application,)g(and)h(which)f(should)f(also)i(be)g (useful)f(in)g(other)-75 854 y(applications.)23 b(The)14 b(goal)f(is)g(to)g(ef)o(\256ciently)h(maintain)e(clusters)i(of)-75 904 y(small)e(diameter)h(as)g(new)f(points)f(are)i(inserted.)19 b(W)m(e)12 b(analyze)h(sev-)-75 954 y(eral)c(natural)f(greedy)h (algorithms)e(and)i(demonstrate)f(that)g(they)g(per)o(-)-75 1004 y(form)16 b(poorly)m(.)32 b(W)m(e)16 b(propose)g(new)h (deterministic)e(and)i(random-)-75 1054 y(ized)e(incremental)g (clustering)f(algorithms)g(which)h(have)g(a)h(prov-)-75 1103 y(ably)e(good)g(performance.)29 b(W)m(e)15 b(complement)h(our)e (positive)f(res-)-75 1153 y(ults)7 b(with)h(lower)g(bounds)f(on)h(the)g (performance)h(of)f(incremental)h(al-)-75 1203 y(gorithms.)22 b(Finally)m(,)13 b(we)h(consider)f(the)g(dual)g(clustering)f(problem) -75 1253 y(where)j(the)f(clusters)g(are)g(of)g(\256xed)g(diameter)n(,)j (and)d(the)g(goal)f(is)h(to)-75 1303 y(minimize)c(the)g(number)h(of)e (clusters.)-75 1413 y Ft(1)50 b(Intr)o(oduction)-25 1516 y Fs(W)m(e)18 b(consider)g(the)f(following)e(problem:)28 b(as)19 b(a)f(sequence)h(of)-75 1565 y(points)10 b(from)h(a)h(metric)f (space)i(is)e(presented,)h(ef)o(\256ciently)f(maintain)-75 1615 y(a)16 b(clustering)e(of)g(the)h(points)f(so)h(as)h(to)e(minimize) h(the)g(maximum)-75 1665 y(cluster)h(diameter)n(.)34 b(Such)16 b(problems)h(arise)g(in)f(a)h(variety)f(of)g(ap-)-75 1715 y(plications,)8 b(in)g(particular)g(in)h(document)f(and)h(image)h (classi\256cation)p -75 1754 401 2 v -33 1781 a Fq(\003)-15 1792 y Fp(Department)g(of)h(Computer)f(Science,)i(Stanford)f (University)n(,)g(Stanford,)h(CA)-75 1832 y(94305-9045)o(.)k(E-mail:)h Fo(moses@cs.stanford.edu)p Fp(.)g(Supported)10 b(by)g(NSF)-75 1871 y(A)m(ward)c(CCR-9357849,)g(with)h(matching)e(funds)h(from)g(IBM,) h(Mitsubishi,)g(Schlum-)-75 1911 y(ber)o(ger)h(Foundation,)e(Shell)j (Foundation,)e(and)g(Xerox)g(Corporation.)-32 1940 y Fq(y)-15 1952 y Fp(Department)j(of)h(Computer)f(Science,)i(Stanford)f (University)n(,)g(Stanford,)h(CA)-75 1991 y(94305-9045)o(.)27 b(E-mail:)d Fo(chekuri@cs.stanford.edu)p Fp(.)j(Supported)13 b(by)-75 2030 y(NSF)h(A)m(ward)f(CCR-9357849,)f(with)i(matching)e (funds)g(from)h(IBM,)g(Mitsubishi,)-75 2070 y(Schlumber)o(ger)7 b(Foundation,)g(Shell)h(Foundation,)f(and)h(Xerox)f(Corporation.)-32 2099 y Fq(z)-15 2111 y Fp(E-mail:)k Fo(tomas@theory.stanford.edu)-32 2140 y Fq(x)-15 2152 y Fp(Department)f(of)h(Computer)f(Science,)i (Stanford)f(University)n(,)g(Stanford,)h(CA)-75 2191 y(94305-9045)o(.)19 b(E-mail:)g Fo(rajeev@cs.stanford.edu)p Fp(.)h(Supported)10 b(by)h(an)-75 2230 y(Alfred)f(P)l(.)i(Sloan)f (Research)e(Fellowship,)i(an)f(IBM)h(Faculty)f(Partnership)g(A)m(ward,) -75 2270 y(an)h(ARO)h(MURI)g(Grant)f(DAAH04-96-1-0007,)f(and)g(NSF)j(Y) m(oung)d(Investigator)-75 2309 y(A)m(ward)c(CCR-9357849,)g(with)h (matching)e(funds)h(from)g(IBM,)h(Mitsubishi,)g(Schlum-)-75 2349 y(ber)o(ger)h(Foundation,)e(Shell)j(Foundation,)e(and)g(Xerox)g (Corporation.)1025 453 y Fs(for)k(information)f(retrieval.)18 b(W)m(e)13 b(propose)e(a)h(model)g(called)g Fr(incr)n(e-)1025 503 y(mental)7 b(clustering)g Fs(based)h(primarily)f(on)g(the)h (requirements)g(for)f(the)1025 553 y(information)g(retrieval)h (application,)h(although)f(our)g(model)h(should)1025 603 y(also)f(be)h(relevant)f(to)g(other)g(applications.)13 b(W)m(e)8 b(begin)g(by)h(analyzing)1025 652 y(several)h(natural)f (greedy)g(algorithms)f(and)i(discover)f(that)g(they)g(per)o(-)1025 702 y(form)f(rather)g(poorly)f(in)h(this)f(setting.)12 b(W)m(e)d(then)f(identify)f(some)i(new)1025 752 y(deterministic)d(and)h (randomized)h(algorithms)e(with)h(provably)f(good)1025 802 y(performance.)13 b(W)m(e)8 b(complement)g(our)f(positive)e (results)i(with)f(lower)1025 852 y(bounds)12 b(on)h(the)h(performance)g (of)f(incremental)h(algorithms.)23 b(W)m(e)1025 901 y(also)11 b(consider)f(the)h(dual)g(clustering)f(problem)h(where)g(the)g (clusters)1025 951 y(are)i(of)f(\256xed)h(diameter)n(,)h(and)f(the)g (goal)f(is)g(to)g(minimize)h(the)f(num-)1025 1001 y(ber)g(of)g (clusters.)20 b(Before)12 b(describing)f(our)h(results)g(in)f(any)i (greater)1025 1051 y(detail,)c(we)i(motivate)f(and)g(formalize)h(our)e (new)i(model.)1074 1101 y(Clustering)e(is)h(used)h(for)f(data)h (analysis)f(and)g(classi\256cation)h(in)f(a)1025 1151 y(wide)g(variety)g(of)g(application)g([1)o(,)i(12)o(,)f(20,)g(27)o(,)h (34)o(].)j(It)c(has)g(proved)1025 1200 y(to)c(be)i(a)f(particularly)f (important)g(tool)g(in)g Fr(information)f(r)n(etrieval)j Fs(for)1025 1250 y(constructing)f(a)k(taxonomy)d(of)i(a)g(corpus)f(of)h (documents)f(by)g(form-)1025 1300 y(ing)g(groups)g(of)h (closely-related)g(documents)g([13,)g(16,)h(34)o(,)g(35)o(,)g(37,)1025 1350 y(38)o(].)i(For)9 b(this)f(purpose,)i(a)g(distance)f(metric)h(is)f (imposed)g(over)g(doc-)1025 1400 y(uments,)g(enabling)f(us)h(to)f(view) h(them)g(as)g(points)f(in)g(a)h(metric)g(space.)1025 1449 y(The)k(central)f(role)g(of)g(clustering)g(in)f(this)h (application)f(is)h(captured)1025 1499 y(by)c(the)g(so-called)h Fn(cluster)h(hypothesis)p Fs(:)i Fr(documents)d(r)n(elevant)g(to)f(a) 1025 1549 y(query)k(tend)g(to)f(be)i(mor)n(e)g(similar)e(to)g(each)i (other)f(than)f(to)g(irr)n(elev-)1025 1599 y(ant)e(documents)h(and)g (hence)i(ar)n(e)f(likely)g(to)f(be)h(cluster)n(ed)g(together)p Fs(.)1025 1649 y(T)m(ypically)m(,)j(clustering)f(is)h(used)g(to)f (accelerate)j(query)d(processing)1025 1698 y(by)c(considering)f(only)h (a)h(small)f(number)h(of)f(representatives)h(of)f(the)1025 1748 y(clusters,)i(rather)h(than)f(the)g(entire)g(corpus.)17 b(In)11 b(addition,)f(it)h(is)g(used)1025 1798 y(for)c (classi\256cation)i([1)n(1)o(])g(and)f(has)h(been)g(suggested)f(as)h(a) g(method)f(for)1025 1848 y(facilitating)g(browsing)h([9)o(,)i(10)o(].) 1074 1898 y(The)16 b(current)g(information)d(explosion,)j(fueled)f(by)g (the)g(avail-)1025 1948 y(ability)d(of)i(hypermedia)h(and)f(the)h(W)m (orld-wide)d(W)m(eb,)17 b(has)d(led)h(to)1025 1997 y(the)c(generation)g (of)h(an)g(ever)o(-increasing)g(volume)g(of)f(data,)i(posing)1025 2047 y(a)c(growing)e(challenge)i(for)f(information)e(retrieval)i (systems)i(to)e(ef)o(\256-)1025 2097 y(ciently)e(store)i(and)f (retrieve)h(this)f(information)e([40].)13 b(A)7 b(major)h(issue)1025 2147 y(that)f(document)g(databases)i(are)g(now)e(facing)h(is)g(the)f (extremely)h(high)1025 2197 y(rate)15 b(of)f(update.)27 b(Several)16 b(practitioners)d(have)i(complained)g(that)1025 2246 y(existing)10 b(clustering)i(algorithms)f(are)i(not)e(suitable)h (for)g(maintain-)1025 2296 y(ing)g(clusters)h(in)g(such)g(a)h(dynamic)f (environment,)h(and)f(they)g(have)1025 2346 y(been)7 b(struggling)e(with)h(the)g(problem)h(of)g(updating)e(clusters)i (without)1025 2396 y(frequently)i(performing)i(complete)g(reclustering) f([4,)i(5,)f(6,)h(8,)f(35].)1025 2446 y(From)g(a)h(theoretical)f (perspective,)i(many)f(dif)o(ferent)f(formulations)1025 2496 y(are)e(possible)e(for)h(this)g(dynamic)h(clustering)e(problem,)h (and)h(it)f(is)g(not)1025 2545 y(clear)13 b(a)g(priori)f(which)g(of)g (these)i(best)e(addresses)i(the)f(concerns)g(of)1025 2595 y(the)f(practitioners.)19 b(After)12 b(a)h(careful)g(study)e(of)i (the)f(requirements,)1025 2645 y(we)e(propose)g(the)g(model)g (described)h(below)m(.)p eop %%Page: 2 2 2 1 bop -75 -33 a Fn(Hierar)o(chical)19 b(Agglomerative)e(Clustering.) 37 b Fs(The)19 b(clustering)-75 16 y(strategy)7 b(employed)g(almost)g (universally)e(in)i(information)e(retrieval)-75 66 y(is)j Fr(Hierar)n(chical)h(Agglomerative)f(Clustering)f(\(HAC\))h Fs([12)o(,)h(34,)g(35)o(,)-75 116 y(37,)k(38,)g(39].)22 b(This)13 b(is)g(also)g(popular)f(in)h(other)g(applications)e(such)-75 166 y(as)e(biology)m(,)e(medicine,)i(image)g(processing,)g(and)f (geographical)f(in-)-75 216 y(formation)k(systems.)22 b(The)13 b(basic)g(idea)g(is:)18 b(initially)10 b(assign)i(the)h Fm(n)-75 265 y Fs(input)d(points)g(to)h Fm(n)g Fs(distinct)f(clusters;) i(repeatedly)f(mer)o(ge)i(pairs)e(of)-75 315 y(clusters)k(until)f (their)h(number)g(is)g(suf)o(\256ciently)g(small.)29 b(Many)15 b(in-)-75 365 y(stantiations)10 b(have)i(been)g(proposed)f (and)h(implemented,)g(dif)o(fering)-75 415 y(mainly)6 b(in)h(the)f(rule)h(for)f(deciding)g(which)h(clusters)f(to)h(mer)o(ge)h (at)e(each)-75 465 y(step.)29 b(Note)15 b(that)g(HAC)g(computes)h (hierarchy)f(trees)h(of)f(clusters)-75 514 y(\(also)10 b(called)g Fr(dendograms)p Fs(\))f(whose)i(leaves)g(are)f(individual)e (points)-75 564 y(and)h(internal)f(nodes)h(correspond)g(to)g(clusters)g (formed)g(by)g(mer)o(ging)-75 614 y(clusters)k(at)g(their)e(children.) 21 b(A)13 b(key)g(advantage)g(of)f(these)i(trees)f(is)-75 664 y(that)6 b(they)h(permit)g(re\256nement)g(of)g(responses)h(to)e (queries)h(by)g(moving)-75 714 y(down)i(the)h(hierarchy)m(.)k(T)m (ypically)m(,)c(the)g(internal)f(nodes)h(are)h(labeled)-75 764 y(with)f(indexing)f(information)g(\(sometimes)j(called)f Fr(conceptual)f(in-)-75 813 y(formation)p Fs(\))d(used)j(for)f (processing)g(queries)g(and)g(in)g(associating)g(se-)-75 863 y(mantics)g(with)f(clusters)h(\(e.g.,)i(for)e(browsing\).)j (Experience)e(shows)-75 913 y(that)d(HAC)g(performs)g(extremely)h(well) f(both)f(in)h(terms)h(of)f(ef)o(\256ciency)-75 963 y(and)16 b(cluster)f(quality)m(.)29 b(In)15 b(the)h(dynamic)f(setting,)h(it)f (is)h(desirable)-75 1013 y(to)f(retain)h(the)f(hierarchical)h (structure)f(while)g(ensuring)g(ef)o(\256cient)-75 1062 y(update)d(and)h(high-quality)d(clustering.)19 b(An)13 b(important)e(goal)h(is)g(to)-75 1112 y(avoid)i(any)h(major)f (modi\256cations)g(in)g(the)g(clustering)f(while)h(pro-)-75 1162 y(cessing)9 b(updates,)g(since)f(any)h(extensive)f(recomputation)f (of)h(the)g(in-)-75 1212 y(dex)h(information)f(will)g(swamp)i(the)f (cost)g(of)g(clustering)f(itself.)13 b(The)-75 1262 y(input)c(size)h (in)g(typical)f(applications)g(is)g(such)i(that)e(super)o(-quadratic) -75 1311 y(time)i(is)g(impractical,)h(and)f(in)g(fact)h(it)e(is)h (desirable)g(to)g(obtain)f(close)-75 1361 y(to)g(linear)g(time.)-75 1455 y Fn(A)g(Model)h(for)f(Incr)o(emental)h(Clustering.)j Fs(V)-5 b(arious)10 b(measures)i(of)-75 1504 y(distance)h(between)h (documents)f(have)h(been)f(proposed)g(in)f(the)h(lit-)-75 1554 y(erature,)k(but)c(we)j(will)d(not)h(concern)h(ourselves)g(with)f (the)g(details)-75 1604 y(thereof;)i(for)d(our)h(purposes,)h(it)f(suf)o (\256ces)h(to)f(note)g(that)g(these)g(dis-)-75 1654 y(tance)e(measures) h(induce)e(a)h(metric)g(space.)19 b(Since)11 b(documents)h(are)-75 1704 y(usually)f(represented)i(as)g(high-dimensional)d(vectors,)j(we)g (cannot)-75 1754 y(make)f(any)f(stronger)f(assumption)g(than)g(that)h (of)f(an)h(arbitrary)f(met-)-75 1803 y(ric)d(space,)i(although,)d(as)i (we)g(will)d(see,)k(our)e(results)f(improve)g(in)h(geo-)-75 1853 y(metric)j(spaces.)-25 1903 y(Formally)m(,)k(the)f Fr(clustering)f Fs(problem)h(is:)19 b(given)12 b Fm(n)i Fs(points)d(in)i(a)-75 1953 y(metric)f(space)h Fl(M)p Fs(,)f(partition)e(the)i(points)e(into)g Fm(k)j Fs(clusters)f(so)g(as)g (to)-75 2003 y(minimize)f(the)g(maximum)h(cluster)f(diameter)n(.)17 b(The)11 b Fr(diameter)g Fs(of)g(a)-75 2052 y(cluster)h(is)f(de\256ned) h(to)f(be)h(the)g(maximum)g(inter)o(-point)d(distance)j(in)-75 2102 y(it.)h(Sometimes)c(the)f(objective)g(function)f(is)h(chosen)h(to) f(be)h(the)f(max-)-75 2152 y(imum)h(cluster)g(radius.)k(In)c(Euclidean) g(spaces,)i Fr(radius)e Fs(denotes)g(the)-75 2202 y(radius)f(of)g(the)h (minimum)f(ball)g(enclosing)f(all)h(points)f(in)h(the)h(cluster)n(.)-75 2252 y(T)m(o)i(extend)f(the)g(notion)f(of)h(radius)g(to)g(arbitrary)f (metric)i(spaces,)h(we)-75 2301 y(\256rst)g(select)h(a)g Fr(center)g Fs(point)e(in)h(each)h(cluster)n(,)g(whereupon)f(the)g(ra-) -75 2351 y(dius)g(is)g(de\256ned)h(as)g(the)g(maximum)g(distance)f (from)h(the)f(center)h(to)-75 2401 y(any)e(point)f(in)g(the)h(cluster)n (.)16 b(W)m(e)c(will)e(assume)i(the)f(diameter)g(meas-)-75 2451 y(ure)f(as)h(the)f(default.)-25 2501 y(W)m(e)g(de\256ne)h(the)f Fr(incr)n(emental)g(clustering)g Fs(problem)g(as)g(follows:)-75 2551 y(for)g(an)h(update)g(sequence)h(of)e Fm(n)h Fs(points)f(in)g Fl(M)p Fs(,)h(maintain)f(a)i(collec-)-75 2600 y(tion)f(of)h Fm(k)h Fs(clusters)f(such)g(that)g(as)h(each)g(input)e(point)f(is)i (presented,)-75 2650 y(either)c(it)g(is)g(assigned)h(to)e(one)i(of)f (the)g(current)g Fm(k)i Fs(clusters,)f(or)f(it)g(starts)-75 2700 y(of)o(f)i(a)h(new)f(cluster)g(while)g(two)f(existing)g(clusters)h (are)h(mer)o(ged)g(into)1025 -33 y(one.)i(W)m(e)c(de\256ne)g(the)f Fr(performance)g(ratio)f Fs(of)h(an)h(incremental)f(clus-)1025 16 y(tering)i(algorithm)g(as)j(the)e(maximum)h(over)g(all)f(update)h (sequences)1025 66 y(of)h(the)g(ratio)g(of)g(its)f(maximum)i(cluster)g (diameter)f(\(or)n(,)i(radius\))e(to)1025 116 y(that)c(of)h(the)g (optimal)f(clustering)h(for)f(the)h(input)f(points.)1074 166 y(Our)14 b(model)f(enforces)i(the)f(requirement)f(that)g Fr(at)h(all)e(times)i Fs(an)1025 216 y(incremental)c(algorithm)e (should)h(maintain)g(a)i(HAC)e(for)h(the)g(points)1025 265 y(presented)h(up)g(to)g(that)g(time.)18 b(As)11 b(before,)i(an)e (algorithm)f(is)i(free)g(to)1025 315 y(use)h(any)f(rule)h(for)f (choosing)g(the)g(two)h(clusters)f(to)g(mer)o(ge)i(at)f(each)1025 365 y(step.)32 b(This)16 b(model)g(preserves)h(all)f(the)g(desirable)g (properties)f(of)1025 415 y(HAC)9 b(while)g(providing)e(a)j(clean)g (extension)e(to)h(the)h(dynamic)f(case.)1025 465 y(In)14 b(addition,)g(it)g(has)h(been)h(observed)e(that)g(such)h(incremental)g (al-)1025 514 y(gorithms)7 b(exhibit)h(good)g(paging)g(performance)i (when)f(the)g(clusters)1025 564 y(themselves)f(are)g(stored)g(in)f (secondary)h(storage,)h(while)e(cluster)g(rep-)1025 614 y(resentatives)j(are)h(preserved)g(in)e(main)i(memory)f([32].)1074 664 y(W)m(e)f(have)f(avoided)g(labeling)f(this)g(model)h(as)h Fr(the)f(online)f(cluster)o(-)1025 714 y(ing)k(pr)n(oblem)i Fs(or)f(referring)g(to)f(the)i(performance)g(ratio)f(as)h(a)g Fr(com-)1025 764 y(petitive)f(ratio)h Fs([25)o(])g(for)g(the)h (following)d(reasons.)24 b(Recall)14 b(that)f(in)1025 813 y(an)f(online)e(setting,)h(we)i(would)d(compare)j(the)f (performance)g(of)g(an)1025 863 y(algorithm)h(to)i(that)g(of)f(an)i (adversary)g(which)f(knows)f(the)h(update)1025 913 y(sequence)g(in)e (advance)i(but)e(must)g(process)i(the)e(points)g(in)g(the)g(or)o(-)1025 963 y(der)j(of)h(arrival.)32 b(Our)17 b(model)f(has)h(a)g(stronger)f (requirement)h(for)1025 1013 y(incremental)h(algorithms,)i(in)e(that)f (they)i(are)g(compared)g(to)f(ad-)1025 1062 y(versaries)e(which)f(do)g (not)g(need)h(to)f(respect)h(the)g(input)e(ordering,)1025 1112 y(i.e.,)20 b(we)e(compare)g(our)f(algorithms)f(to)h(optimal)f (clusterings)g(of)1025 1162 y(the)d(\256nal)h(point)f(set,)i(and)f(no)g (intermediate)f(clusterings)g(need)i(be)1025 1212 y(maintained.)34 b(Also,)19 b(online)d(algorithms)g(are)i(permitted)e(super)o(-)1025 1262 y(polynomial)7 b(running)h(times.)14 b(In)9 b(contrast,)g(our)g (model)h(essentially)1025 1311 y(requires)16 b(polynomial-time)f (approximation)h(algorithms)g(which)1025 1361 y(are)11 b(constrained)g(to)f(incrementally)h(maintain)f(a)i(HAC.)f(It)f(may)i (be)1025 1411 y(interesting)5 b(to)h(explore)h(the)f(several)i(dif)o (ferent)e(formulations)f(of)i(on-)1025 1461 y(line)12 b(clustering;)g(for)g(example,)j(when)d(the)h(newly)f(inserted)h(point) 1025 1511 y(starts)d(of)o(f)g(a)h(new)f(cluster)n(,)h(we)g(could)f (allow)f(the)i(points)e(of)h(one)g(old)1025 1561 y(cluster)h(to)h(be)g (redistributed)e(among)i(the)g(remaining,)h(rather)f(than)1025 1610 y(requiring)h(that)h(two)h(clusters)g(be)h(mer)o(ged)g(together)n (.)27 b(The)16 b(prob-)1025 1660 y(lem)9 b(with)f(such)i(formulations)d (is)j(that)e(they)h(do)g(not)f(lead)i(to)f(HACs;)1025 1710 y(moreover)n(,)14 b(they)f(entail)f(the)h(recomputation)f(of)h (the)g(index)f(struc-)1025 1760 y(tures)i(for)g Fr(all)f(clusters)p Fs(,)k(which)d(renders)h(the)f(algorithms)f(useless)1025 1810 y(from)h(the)g(point)e(of)i(view)g(of)g(applications)f(under)h (consideration)1025 1859 y(here.)1025 1953 y Fn(Pr)o(evious)h(W)n(ork)g (in)g(Static)f(Clustering.)28 b Fs(The)16 b(closely-related)1025 2003 y(problems)c(of)g(clustering)f(to)h(minimize)h(diameter)g(and)f (radius)g(are)1025 2052 y(also)d(called)i Fr(pairwise)e(clustering)g Fs(and)h(the)g Fm(k)q Fr(-center)h(pr)n(oblem)p Fs(,)f(re-)1025 2102 y(spectively)k([2)o(,)i(21)o(].)28 b(Both)14 b(are)h(NP-hard)g ([17)o(,)h(28)o(],)h(and)e(in)f(fact)1025 2152 y(hard)g(to)g (approximate)h(to)f(within)f(factor)h(2)h(for)f(arbitrary)g(metric)1025 2202 y(spaces)f([2,)g(21)o(].)21 b(For)12 b(Euclidean)g(spaces,)j (clustering)c(on)h(the)h(line)1025 2252 y(is)c(easy)h([3],)g(but)f(in)g (higher)g(dimensions)f(it)h(is)h(NP-hard)f(to)g(approx-)1025 2301 y(imate)14 b(to)h(within)d(factors)j(close)g(to)f(2,)i(regardless) f(of)f(the)h(metric)1025 2351 y(used)f([14)o(,)h(15,)f(19,)h(29)o(,)g (30)o(].)26 b(The)15 b Fr(furthest)f(point)e(heuristic)i Fs(due)1025 2401 y(to)c(Gonzalez)h([19])f(\(see)i(also)f(Hochbaum)g (and)g(Shmoys)f([23,)h(24)o(]\))1025 2451 y(gives)e(a)i (2-approximation)c(in)j(all)f(metric)h(spaces.)16 b(This)10 b(algorithm)1025 2501 y(requires)k Fm(O)q Fk(\()p Fm(k)q(n)p Fk(\))h Fs(distance)h(computations,)f(and)g(when)g(the)g(met-)1025 2551 y(ric)e(space)j(is)d(induced)h(by)g(shortest-path)e(distances)i (in)g(weighted)1025 2600 y(graphs,)g(the)g(running)e(time)h(is)h Fm(O)q Fk(\()p Fm(n)1571 2585 y Fj(2)1589 2600 y Fk(\))p Fs(.)25 b(Feder)14 b(and)g(Greene)h([14)o(])1025 2650 y(gave)e(an)h(implementation)e(for)h Fr(Euclidean)g Fs(spaces)i(with)d (running)1025 2700 y(time)e Fm(O)q Fk(\()p Fm(n)d Fk(log)f Fm(k)q Fk(\))p Fs(.)p eop %%Page: 3 3 3 2 bop -75 -33 a Fn(Overview)11 b(of)f(Results.)k Fs(Our)c(results)f (for)h(incremental)g(clustering)-75 16 y(show)g(that)f(it)g(is)h (possible)f(to)g(obtain)g(algorithms)f(that)h(are)i(compar)o(-)-75 66 y(able)f(to)g(the)f(best)h(possible)f(in)h(the)g(static)f(setting,)g (both)g(in)h(terms)g(of)-75 116 y(ef)o(\256ciency)j(and)f(performance)h (ratio.)18 b(W)m(e)13 b(begin)e(in)h(Section)f(2)h(by)-75 166 y(considering)c(natural)g(greedy)h(algorithms)f(that)h(choose)g (clusters)g(to)-75 216 y(mer)o(ge)g(based)f(on)g(some)g(measure)h(of)f (the)f(resulting)f(cluster)n(.)13 b(W)m(e)8 b(es-)-75 265 y(tablish)g(that)i(greedy)f(algorithms)g(behave)h(poorly)e(by)h (proving)f(that)-75 315 y(a)13 b(Center)o(-Greedy)g(algorithm)f(has)h (a)h(tight)d(performance)j(ratio)e(of)-75 365 y Fk(2)p Fm(k)c Fl(\000)g Fk(1)p Fs(,)h(and)h(a)g(Diameter)o(-Greedy)g (algorithm)e(has)i(a)h(lower)e(bound)-75 415 y(of)k Fk(\012\(log)7 b Fm(k)q Fk(\))p Fs(.)24 b(It)12 b(seems)j(likely)e(that)f(greedy)i (algorithms)e(behave)-75 465 y(better)h(in)f(geometric)h(spaces,)i(and) e(we)h(discover)e(some)i(evidence)-75 514 y(in)e(the)h(case)i(of)d(the) h(line.)21 b(W)m(e)14 b(show)e(that)h(Diameter)o(-Greedy)g(has)-75 564 y(performance)i(ratio)f(2)h(for)f Fm(k)27 b Fk(=)f(2)15 b Fs(on)f(the)h(line.)26 b(This)15 b(analysis)-75 614 y(suggests)c(a)i(variant)e(of)g(Diameter)o(-Greedy)m(,)i(and)f(this)f (is)g(shown)g(to)-75 664 y(achieve)h(ratio)e(3)h(for)g(all)g Fm(k)h Fs(on)f(the)f(line.)16 b(In)11 b(Section)g(3)g(we)h(present)-75 714 y(the)e(Doubling)f(Algorithm)f(and)j(show)f(that)g(its)g (performance)h(ratio)-75 764 y(is)f Fk(8)p Fs(,)g(and)g(that)g(a)g (randomized)g(version)g(has)g(ratio)f Fk(5)p Fm(:)p Fk(43)p Fs(.)k(While)d(the)-75 813 y(obvious)d(implementation)g(of)h(these)g (algorithms)f(is)h(expensive,)h(we)-75 863 y(show)j(that)g(they)g(can)h (be)f(implemented)h(so)f(as)h(to)f(achieve)h(amort-)-75 913 y(ized)d(time)g Fm(O)q Fk(\()p Fm(k)d Fk(log)g Fm(k)q Fk(\))j Fs(per)g(update.)j(These)e(results)f(for)f(the)g(Doub-)-75 963 y(ling)k(Algorithm)f(carry)j(over)f(to)g(the)g(radius)g(measure.)28 b(Then,)16 b(in)-75 1013 y(Section)e(4,)i(we)f(present)f(the)h(Clique)e (Algorithm)f(and)j(show)f(that)-75 1062 y(it)h(has)i(performance)f (ratio)g(6,)h(and)f(that)g(a)g(randomized)g(version)-75 1112 y(has)e(ratio)f Fk(4)p Fm(:)p Fk(33)p Fs(.)23 b(While)14 b(the)f(Clique)g(Algorithm)e(may)k(appear)f(to)-75 1162 y(dominate)d(the)h(Doubling)e(Algorithm,)g(this)h(is)g(not)g(the)h (case)h(since)-75 1212 y(the)e(former)g(requires)f(computing)g(clique)g (partitions,)g(an)h(NP-hard)-75 1262 y(problem,)d(although)e(it)g(must) i(be)f(said)h(in)f(its)g(defense)h(that)f(the)g(clique)-75 1311 y(partitions)j(need)i(only)f(be)h(computed)g(in)f(graphs)g(with)g Fm(k)h Fk(+)g(1)f Fs(ver)o(-)-75 1361 y(tices.)j(While)7 b(the)h(performance)h(ratio)f(of)g(the)g(Clique)f(Algorithm)f(is)-75 1411 y(8)i(for)f(the)h(radius)f(measure,)k(improved)c(bounds)g(are)i (possible)e(for)g Fm(d)p Fs(-)-75 1461 y(dimensional)h(Euclidean)i (spaces;)g(speci\256cally)m(,)g(we)g(show)f(that)g(the)-75 1511 y(radius)i(performance)i(ratio)d(of)i(the)f(Clique)f(Algorithm)g (in)h Fl(<)837 1496 y Fi(d)868 1511 y Fs(im-)-75 1561 y(proves)f(to)g Fk(4\(1)g(+)198 1525 y Fh(p)p 240 1525 189 2 v 36 x Fm(d=)p Fk(\(2)p Fm(d)e Fk(+)i(2\))o(\))p Fs(,)i(which)e(is)g(6)h(for)f Fm(d)i Fk(=)g(1)p Fs(,)f(and)g(is)-75 1610 y(asymptotic)c(to)g(6.83)g(for)g(lar)o(ge)h Fm(d)p Fs(.)13 b(In)8 b(Section)f(5,)h(we)g(provide)f(lower)-75 1660 y(bounds)j(for)g(incremental)h(clustering)e(algorithms.)15 b(W)m(e)c(show)f(that)-75 1710 y(even)16 b(for)f Fm(k)29 b Fk(=)g(2)15 b Fs(and)h(on)f(the)g(line,)h(no)f(deterministic)g(or)g (ran-)-75 1760 y(domized)10 b(algorithm)f(can)i(achieve)h(a)e(ratio)g (better)g(than)g(2.)k(W)m(e)d(im-)-75 1810 y(prove)e(this)g(lower)g (bound)g(to)g Fk(2)p Fm(:)p Fk(414)f Fs(for)h(deterministic)g (algorithms)-75 1859 y(in)e(general)g(metric)g(spaces.)15 b(Finally)m(,)7 b(in)f(Section)h(6)g(we)h(consider)f(the)-75 1909 y(dual)g(clustering)g(problem)g(of)g(minimizing)f(the)i(number)f (of)h(clusters)-75 1959 y(of)k(a)g(\256xed)g(radius.)19 b(Since)12 b(it)g(is)f(impossible)g(to)h(achieve)h(bounded)-75 2009 y(ratios)e(for)g(general)h(metric)g(spaces,)i(we)e(focus)g(on)f Fm(d)p Fs(-dimensional)-75 2059 y(Euclidean)g(spaces.)18 b(W)m(e)11 b(present)g(an)h(incremental)f(algorithm)e(that)-75 2108 y(has)g(performance)g(ratio)e Fm(O)q Fk(\(2)361 2093 y Fi(d)380 2108 y Fm(d)g Fk(log)f Fm(d)p Fk(\))p Fs(,)j(and)f(also)g(provide)f(a)i(lower)-75 2158 y(bound)g(of)h Fk(\012\(log)d Fm(d=)g Fk(log)f(log)g(log)h Fm(d)p Fk(\))p Fs(.)-25 2252 y(Many)15 b(interesting)e(directions)h(for)h(future)g (research)h(are)g(sug-)-75 2301 y(gested)i(by)g(our)f(work.)36 b(There)19 b(are)g(the)f(obvious)e(questions)h(of)-75 2351 y(improving)11 b(our)h(upper)g(and)h(lower)f(bounds,)h (particularly)e(for)h(the)-75 2401 y(dual)h(clustering)f(problem.)22 b(An)13 b(important)e(theoretical)i(question)-75 2451 y(is)c(whether)h(the)f(geometric)h(setting)e(permits)i(better)f(ratios) g(than)g(do)-75 2501 y(metric)14 b(spaces.)26 b(Our)13 b(model)h(can)g(be)g(generalized)g(in)f(many)i(dif-)-75 2551 y(ferent)g(ways.)27 b(Depending)14 b(on)g(the)h(exact)g (application,)g(we)g(may)-75 2600 y(wish)e(to)g(consider)h(other)f (measures)j(of)d(clustering)g(quality)m(,)g(such)-75 2650 y(as:)23 b(minimum)14 b(variance)h(in)f(cluster)g(diameter)n(,)j (and)e(the)f(sum)h(of)-75 2700 y(squares)g(of)f(the)g(inter)o(-point)d (distances)k(within)d(a)j(cluster)n(.)25 b(Then,)1025 -33 y(there)16 b(is)f(the)h(issue)g(of)g(handling)e(deletions)h(which,) j(though)c(not)1025 16 y(important)d(for)i(our)g(motivating)e (application)h(of)h(information)f(re-)1025 66 y(trieval,)7 b(may)h(be)g(relevant)f(in)g(other)g(applications.)12 b(Finally)m(,)c(there)f(is)1025 116 y(the)j(question)g(of)h (formulating)e(a)i(model)g(for)g Fr(adaptive)f(clustering)p Fs(,)1025 166 y(wherein)f(the)g(clustering)f(may)i(be)f(modi\256ed)h (as)g(a)f(result)g(of)g(queries)1025 216 y(and)h(user)g(feedback,)i (even)f(without)d(any)i(updates.)1025 321 y Ft(2)49 b(Gr)o(eedy)12 b(Algorithms)1074 419 y Fs(W)m(e)h(begin)e(by)g(examining)g(some)i (natural)e(greedy)h(algorithms.)1025 469 y(A)k Fr(gr)n(eedy)i(incr)n (emental)e(clustering)f(algorithm)f Fs(always)j(mer)o(ges)1025 518 y(clusters)11 b(to)f(minimize)h(some)h(\256xed)f(measure.)19 b(Our)10 b(results)h(indic-)1025 568 y(ate)f(that)g(such)g(algorithms)f (perform)h(poorly)m(.)1025 654 y Fn(De\256nition)f(1)21 b Fr(The)26 b(Center)o(-Gr)n(eedy)i(Algorithm)c(associates)i(a)1025 704 y(center)15 b(for)f(each)h(cluster)g(and)f(mer)n(ges)i(the)f(two)e (clusters)i(whose)1025 754 y(centers)h(ar)n(e)g(closest.)29 b(The)15 b(center)h(of)f(the)g(old)f(cluster)h(with)f(the)1025 804 y(lar)n(ger)c(radius)e(becomes)j(the)f(new)f(center)-5 b(.)15 b(It)9 b(is)h(possible)f(to)g(de\256ne)1025 853 y(variants)j(of)h(Center)o(-Gr)n(eedy)j(based)e(on)f(how)g(the)g (centers)i(of)e(the)1025 903 y(clusters)c(ar)n(e)h(picked)g(but)f(we)h (r)n(estrict)g(ourselves)g(to)f(this)f(de\256nition)1025 953 y(for)h(r)n(easons)i(of)f(simplicity)f(and)g(intuitiveness.)1025 1039 y Fn(De\256nition)g(2)21 b Fr(The)46 b(Diameter)o(-Gr)n(eedy)h (Algorithm)d(always)1025 1089 y(mer)n(ges)17 b(those)e(two)g(clusters)g (which)g(minimize)g(the)g(diameter)h(of)1025 1139 y(the)10 b(r)n(esulting)f(mer)n(ged)i(cluster)-5 b(.)1074 1224 y Fs(W)m(e)13 b(can)f(establish)g(the)g(following)d(lower)j(bounds)f (on)g(the)h(per)o(-)1025 1274 y(formance)f(ratio)f(of)h(these)g(two)f (greedy)h(algorithms.)k(W)m(e)c(omit)f(the)1025 1324 y(proofs)f(in)h(this)f(extended)h(abstract.)1025 1410 y Fn(Theor)o(em)h(1)20 b Fr(The)11 b(Center)o(-Gr)n(eedy)g(Algorithm)e (has)h(performance)1025 1460 y(ratio)f(at)g(least)h Fk(2)p Fm(k)g Fl(\000)f Fk(1)p Fr(.)1025 1546 y Fn(Theor)o(em)i(2)20 b Fr(The)c(Diameter)o(-Gr)n(eedy)h(Algorithm)c(has)i(perform-)1025 1595 y(ance)10 b(ratio)f(at)h(least)g Fk(\012\(log)c Fm(k)q Fk(\))p Fr(,)11 b(even)h(on)e(the)g(line.)1074 1681 y Fs(W)m(e)j(now)g(give)f(a)h(tight)e(upper)i(bound)e(for)i(the)f (Center)o(-Greedy)1025 1731 y(Algorithm.)k(Note)11 b(that)g(for)g Fm(k)17 b Fk(=)f(3)11 b Fs(it)g(has)h(ratio)f(5,)h(but)f(for)g(lar)o (ger)1025 1781 y Fm(k)i Fs(its)e(performance)i(is)f(worse)g(than)g (that)f(of)h(the)g(algorithms)e(to)i(be)1025 1831 y(presented)e(later)n (.)1025 1917 y Fn(Theor)o(em)h(3)20 b Fr(The)11 b(Center)o(-Gr)n(eedy)g (Algorithm)e(has)h(performance)1025 1967 y(ratio)f(of)g Fk(2)p Fm(k)h Fl(\000)g Fk(1)g Fr(in)g(any)g(metric)g(space.)1074 2052 y Fn(Pr)o(oof:)19 b Fs(Suppose)12 b(that)g(a)h(set)g Fm(P)18 b Fs(of)12 b Fm(n)h Fs(points)e(is)h(inserted.)21 b(Let)1025 2102 y(their)10 b(optimal)h(clustering)f(be)i(the)f (partition)e Fm(S)19 b Fk(=)c Fl(f)p Fm(C)1833 2108 y Fj(1)1852 2102 y Fm(;)7 b(:)g(:)g(:)t(;)g(C)1974 2108 y Fi(k)1994 2102 y Fl(g)p Fs(,)1025 2152 y(with)12 b Fm(d)h Fs(as)g(the)g(optimal)g(diameter)n(.)22 b(W)m(e)14 b(will)e(show)h(that)f(the)h(dia-)1025 2202 y(meter)g(of)g(any)h (cluster)f(produced)g(by)g(Center)o(-Greedy)g(is)g(at)g(most)1025 2252 y Fk(\(2)p Fm(k)d Fl(\000)f Fk(1\))p Fm(d)p Fs(.)1074 2301 y(W)m(e)j(de\256ne)f(a)h(graph)f Fm(G)f Fs(on)h(the)g(set)g Fm(S)j Fs(of)d(the)g(optimal)f(clusters,)1025 2351 y(where)18 b(two)f(clusters)g(are)i(connected)f(by)f(an)h(edge)g(if)f(the)h(min-) 1025 2401 y(imum)8 b(distance)h(between)g(them)g(is)f(at)h(most)f Fm(d)p Fs(,)h(where)h(the)e(distance)1025 2451 y(between)20 b(two)g(clusters)g(is)g(the)g(minimum)g(distances)h(between)1025 2501 y(points)12 b(in)i(them.)26 b(Consider)13 b(the)h(connected)h (components)f(of)g Fm(G)p Fs(.)1025 2551 y(Note)j(that)g(two)g (clusters)h(in)f(dif)o(ferent)g(connected)h(components)1025 2600 y(have)12 b(minimum)g(distance)g(strictly)f(greater)i(than)f Fm(d)p Fs(.)19 b(W)m(e)13 b(say)g(that)1025 2650 y(a)g(cluster)f Fm(X)17 b Fs(intersects)12 b(a)i(connected)f(component)f(consisting)f (of)1025 2700 y(the)f(optimal)f(clusters)h Fm(C)1390 2706 y Fi(i)1402 2710 y Fg(1)1420 2700 y Fm(;)d(:)g(:)g(:)e(;)i(C)1543 2706 y Fi(i)1555 2710 y Ff(r)1583 2700 y Fs(if)i Fm(X)14 b Fs(intersects)c Fl([)1861 2685 y Fi(r)1861 2711 y(j)r Fj(=1)1921 2700 y Fm(C)1951 2706 y Fi(i)1963 2710 y Ff(j)1980 2700 y Fs(.)p eop %%Page: 4 4 4 3 bop -25 -33 a Fs(W)m(e)8 b(claim)g(that)f(at)h(all)g(times,)h(any)e (cluster)h(produced)f(by)h(Center)o(-)-75 16 y(Greedy)16 b(intersects)g(exactly)g(one)f(connected)i(component)e(of)g Fm(G)p Fs(.)-75 66 y(W)m(e)c(prove)f(this)f(claim)i(by)f(induction)e (over)i Fm(n)p Fs(.)15 b(Suppose)10 b(the)g(claim)-75 116 y(is)18 b(true)h(before)f(a)i(new)e(point)f Fm(p)i Fs(arrives.)39 b(Initially)m(,)19 b Fm(p)g Fs(is)f(in)g(a)-75 166 y(cluster)9 b(of)g(its)f(own)g(and)i(Center)o(-Greedy)f(has)g Fm(k)e Fk(+)f(1)j Fs(clusters,)g(each)-75 216 y(of)14 b(which)f(intersect)h(exactly)g(one)h(connected)f(component)g(of)f Fm(G)p Fs(.)-75 265 y(Since)h(there)f(are)h Fm(k)g Fk(+)f(1)g Fs(cluster)g(centers,)i(two)e(of)g(them)g(must)g(be)-75 315 y(in)h(the)g(same)i(optimal)d(cluster)n(.)26 b(This)14 b(implies)g(that)f(the)h(distance)-75 365 y(between)f(the)f(two)f (closest)h(centers)h(is)f(at)g(most)h Fm(d)p Fs(.)19 b(If)12 b Fm(X)769 371 y Fj(1)800 365 y Fs(and)g Fm(X)906 371 y Fj(2)-75 415 y Fs(are)h(the)e(clusters)h(that)g(Center)o(-Greedy) f(mer)o(ges)j(at)e(this)f(stage,)i(the)-75 465 y(centers)f(of)g Fm(X)135 471 y Fj(1)165 465 y Fs(and)g Fm(X)271 471 y Fj(2)302 465 y Fs(must)f(be)h(at)f(most)h Fm(d)f Fs(apart.)18 b(Hence,)c(both)-75 514 y(clusters')7 b(centers)h(must)e(lie)h(in)g (the)f(same)j(connected)e(component)g(of)-75 564 y Fm(G)p Fs(,)12 b(say)g Fl(C)r Fs(.)19 b(By)12 b(the)f(inductive)g(hypothesis,) g(all)g(points)g(in)g Fm(X)835 570 y Fj(1)866 564 y Fs(and)-75 614 y Fm(X)-41 620 y Fj(2)-14 614 y Fs(must)c(be)h(in)g Fl(C)r Fs(.)13 b(Hence,)d(all)d(points)g(in)g(the)g(new)h(cluster)g Fm(X)821 620 y Fj(1)842 614 y Fl([)r Fm(X)906 620 y Fj(2)-75 664 y Fs(must)i(lie)g(in)g Fl(C)r Fs(,)h(establishing)d(the)j (inductive)d(hypothesis.)-25 714 y(Since)20 b(each)h(cluster)f (produced)f(by)h(Center)o(-Greedy)g(lies)f(in)-75 764 y(exactly)h(one)h(connected)g(component)f(of)g Fm(G)p Fs(,)j(the)d(diameter)h(is)-75 814 y(bounded)9 b(by)h(the)g(maximum)h (diameter)g(of)f(a)g(connected)h(compon-)-75 864 y(ent,)f(which)g(is)g (at)h(most)f Fk(\(2)p Fm(k)g Fl(\000)f Fk(1\))p Fm(d)p Fs(.)p 896 864 30 30 v -25 914 a(For)14 b(Diameter)o(-Greedy)h(in)f (general)g(metric)h(spaces,)i(we)e(only)-75 964 y(have)d(the)f (following)f(weak)i(upper)f(bound;)g(the)g(proof)g(is)g(deferred)-75 1014 y(to)f(the)g(\256nal)g(version.)-75 1108 y Fn(Theor)o(em)h(4)21 b Fr(For)10 b Fm(k)i Fk(=)g(2)p Fr(,)e(the)f(Diameter)o(-Gr)n(eedy)j (Algorithm)c(has)-75 1158 y(a)i(performance)h(ratio)e Fk(3)h Fr(in)g(any)g(metric)g(space.)-25 1251 y Fs(In)i(spite)h(of)f (the)h(lower)f(bounds)g(for)h(greedy)f(algorithms,)h(they)-75 1301 y(may)e(not)g(be)g(entirely)f(useless)h(since)g(some)h(variant)e (may)i(perform)-75 1351 y(well)e(in)g(geometric)g(spaces.)16 b(W)m(e)11 b(obtain)e(some)i(positive)e(evidence)-75 1401 y(in)g(this)g(regard)h(via)g(the)g(following)d(analysis)j(for)g (the)f(line.)14 b(The)c(up-)-75 1451 y(per)k(bounds)f(given)g(here)h (should)e(be)i(contrasted)g(with)e(the)i(lower)-75 1501 y(bound)e(of)h(2)g(for)g(the)h(line)e(shown)h(in)g(Section)g(5.)23 b(The)14 b(following)-75 1550 y(de\256nitions)9 b(underlie)g(the)h (analysis.)-75 1645 y Fn(De\256nition)g(3)20 b Fr(Given)g(a)f(set)g Fm(S)k Fr(of)18 b Fm(n)i Fr(points)d(in)i(the)g(line,)j(a)d Fm(t)p Fs(-)-75 1694 y(partition)14 b Fr(subdivides)i(the)g(interval)f (between)i(the)f(\256rst)g(and)g(last)-75 1744 y(points)f(of)h Fm(S)k Fr(into)15 b Fm(t)i Fr(subintervals)e(whose)i(endpoints)e(ar)n (e)i(in)f Fm(S)r Fr(.)-75 1794 y(The)d Fm(t)p Fs(-diameter)h Fr(of)e Fm(S)k Fr(is)d(the)f(minimum)g(over)i(all)e Fm(t)p Fr(-partitions)e(of)-75 1844 y(the)15 b(maximum)f(interval)g(length)f (in)i(a)f Fm(t)p Fr(-partition)e(of)i Fm(S)r Fr(.)29 b(The)15 b Fk(1)p Fr(-)-75 1894 y(diameter)d(is)g(the)h(diameter)-5 b(,)13 b(while)f(the)g Fk(2)p Fr(-diameter)g(is)g(the)g(radius)-75 1943 y(of)e Fm(S)j Fr(wher)n(e)e(the)f(center)h(is)f(constrained)g(to)g (be)g(a)g(point)f(of)h Fm(S)r Fr(.)-25 2037 y Fs(W)m(e)e(de\256ne)h (the)f(following)e(family)i(of)g(algorithms)f(based)i(on)f(the)-75 2087 y(notion)g(of)i(the)h Fm(t)p Fs(-diameter)n(.)-75 2172 y Fn(De\256nition)f(4)20 b Fr(The)30 b Fm(t)p Fr(-Diameter)f(Gr)n (eedy)i(Algorithm)d(mer)n(ges)-75 2222 y(those)20 b(two)g(clusters)g (which)g(minimize)g(the)g Fm(t)p Fr(-diameter)g(of)g(the)-75 2272 y(mer)n(ged)12 b(cluster)-5 b(.)16 b(Note)11 b(that)e Fk(1)p Fr(-Diameter)h(Gr)n(eedy)j(is)e(the)f(same)i(as)-75 2322 y(Diameter)o(-Gr)n(eedy)n(.)-25 2407 y Fs(While)g(Diameter)o (-Greedy)i(has)g(ratio)e(2)h(for)f Fm(k)22 b Fk(=)f(2)13 b Fs(and)g(ratio)-75 2456 y(3)f(for)f Fm(k)17 b Fk(=)f(3)p Fs(,)c(we)g(can)h(show)e(a)h(lower)g(bound)e(of)i Fk(\012\(log)6 b Fm(k)q Fk(\))12 b Fs(on)f(its)-75 2506 y(performance)g(ratio)f(on)f (the)i(line.)-75 2600 y Fn(Theor)o(em)g(5)21 b Fr(The)8 b(Diameter)o(-Gr)n(eedy)h(Algorithm)d(for)i(the)g(line)f(has)-75 2650 y(performance)12 b(ratio)e Fk(2)i Fr(for)f Fm(k)17 b Fk(=)g(2)11 b Fr(and)g(performance)h(ratio)f Fk(3)g Fr(for)-75 2700 y Fm(k)h Fk(=)g(3)p Fr(.)1074 -33 y Fs(Unlike)j (Diameter)o(-Greedy)m(,)j(we)e(can)h(show)e(that)g Fk(3)p Fs(-Diameter)1025 16 y(Greedy)10 b(has)h(a)g(bounded)e(performance)i (ratio)f(on)f(the)h(line.)1025 91 y Fn(Theor)o(em)h(6)20 b Fr(The)8 b Fk(3)p Fr(-Diameter)g(Gr)n(eedy)h(Algorithm)e(has)g (perform-)1025 140 y(ance)j(ratio)f Fk(3)h Fr(on)g(the)g(line.)1074 215 y Fn(Pr)o(oof:)k Fs(In)c(fact,)h(we)f(show)g(that)f(it)g(produces)h (a)g(clustering)f(with)1025 264 y Fk(3)p Fs(-diameter)14 b(at)h(most)g(the)g(optimal)f(diameter)n(,)j(and)e(the)g(factor)f(of) 1025 314 y Fk(3)h Fs(follows.)29 b(Assume)17 b(this)e(holds)g(before)h (the)f(last)h(two)f(clusters)1025 364 y(are)10 b(mer)o(ged.)15 b(Let)c Fm(I)1317 370 y Fj(1)1335 364 y Fm(;)c(I)1372 370 y Fj(2)1391 364 y Fm(;)g(:)g(:)g(:)e(;)i(I)1502 370 y Fi(k)1532 364 y Fs(be)j(the)g(intervals)f(in)g(the)h(optimal)1025 414 y(clustering,)d(with)f(maximum)j(diameter)f Fm(d)p Fs(.)13 b(Let)8 b Fm(C)1756 420 y Fj(1)1774 414 y Fm(;)f(C)1823 420 y Fj(2)1841 414 y Fm(;)g(:)g(:)g(:)t(;)g(C)1963 420 y Fi(k)q Fj(+1)1025 464 y Fs(be)14 b(the)h(current)f(clusters,)i(each)g (with)d Fk(3)p Fs(-diameter)i(at)f(most)h Fm(d)p Fs(,)g(of)1025 514 y(which)9 b(two)h(must)g(be)h(mer)o(ged.)k(If)10 b Fm(C)1566 520 y Fi(i)1590 514 y Fs(starts)g(in)g Fm(I)1749 520 y Fi(a)1780 514 y Fs(and)g(ends)h(in)f Fm(I)1998 520 y Fi(b)2015 514 y Fs(,)1025 563 y(let)h Fm(x)1102 569 y Fi(i)1133 563 y Fk(=)17 b Fm(b)11 b Fl(\000)h Fm(a)p Fs(;)g(notice)g(that)f Fm(x)1513 569 y Fj(1)1543 563 y Fk(+)h Fl(\001)7 b(\001)g(\001)i Fk(+)j Fm(x)1714 569 y Fi(k)q Fj(+1)1793 563 y Fl(\024)18 b Fm(k)12 b Fl(\000)g Fk(1)p Fs(.)19 b(W)m(e)1025 613 y(assume)10 b(that)e(if)g Fm(C)1291 619 y Fi(i)1314 613 y Fs(ends)h(in)f Fm(I)1458 619 y Fi(b)1484 613 y Fs(then)h Fm(C)1595 619 y Fi(i)p Fj(+1)1659 613 y Fs(starts)g(in)f Fm(I)1815 619 y Fi(b)1832 613 y Fs(;)h(otherwise,)1025 663 y(we)h(could)g(replace)h(the)f(ar)o (gument)g(in)f(the)h Fm(k)h Fs(intervals)f Fm(I)1851 669 y Fi(j)1879 663 y Fs(by)f(an)i(ar)o(-)1025 713 y(gument)e(either)g (in)h(the)f(\256rst)h Fm(b)g Fs(intervals)f Fm(I)1640 719 y Fj(1)1659 713 y Fm(;)e(:)g(:)g(:)t(;)g(I)1769 719 y Fi(b)1786 713 y Fs(,)j(if)f(there)h(are)h(at)1025 763 y(least)e Fm(b)d Fk(+)g(1)k Fs(clusters)f Fm(C)1369 769 y Fi(i)1392 763 y Fs(in)f(this)h(region,)f(or)h(in)g(the)g(last)g Fm(k)e Fl(\000)f Fm(b)k Fs(inter)o(-)1025 812 y(vals)d Fm(I)1117 818 y Fi(b)p Fj(+1)1176 812 y Fm(;)g(:)g(:)g(:)e(;)i(I)1287 818 y Fi(k)1307 812 y Fs(,)i(if)e(there)h(are)g(at)g(least)g Fm(k)t Fl(\000)r Fm(b)r Fk(+)r(1)g Fs(current)f(clusters)1025 862 y Fm(C)1055 868 y Fi(i)1078 862 y Fs(in)i(this)f(region.)14 b(Now)m(,)c(the)f(bounds)g(imply)g(that)g(for)g(some)h Fm(i)p Fs(,)h(we)1025 912 y(have)h Fm(x)1139 918 y Fi(i)1164 912 y Fk(+)g Fm(x)1232 918 y Fi(i)p Fj(+1)1305 912 y Fm(<)18 b Fk(2)p Fs(.)h(If)12 b Fm(x)1469 918 y Fi(i)1500 912 y Fk(=)18 b Fm(x)1574 918 y Fi(i)p Fj(+1)1647 912 y Fk(=)g(0)p Fs(,)13 b(then)e(the)h(mer)o(ging)1025 962 y(of)g Fm(C)1102 968 y Fi(i)1129 962 y Fs(and)i Fm(C)1233 968 y Fi(i)p Fj(+1)1301 962 y Fs(is)f(contained)g(in)g(a)h(single)e (interval)g Fm(I)1865 968 y Fi(j)1896 962 y Fs(and)i(has)1025 1012 y(diameter)e(at)h(most)g Fm(d)p Fs(.)21 b(If)12 b(say)h Fm(x)1504 1018 y Fi(i)1537 1012 y Fk(=)20 b(0)12 b Fs(and)h Fm(x)1719 1018 y Fi(i)p Fj(+1)1794 1012 y Fk(=)20 b(1)p Fs(,)13 b(then)f(the)1025 1062 y(gap)d Fm(G)h Fs(between)g(the)f(two)g(consecutive)h(intervals)f Fm(I)1794 1068 y Fi(j)1822 1062 y Fs(and)g Fm(I)1909 1068 y Fi(j)r Fj(+1)1979 1062 y Fs(in-)1025 1111 y(volved)g(is)i(at)g (most)g Fm(d)p Fs(,)g(since)g Fm(C)1489 1117 y Fi(i)p Fj(+1)1555 1111 y Fs(has)h Fk(3)p Fs(-diameter)e(at)h(most)g Fm(d)p Fs(,)g(so)1025 1161 y(the)d(mer)o(ger)i(of)f Fm(C)1284 1167 y Fi(i)1306 1161 y Fs(and)g Fm(C)1405 1167 y Fi(i)p Fj(+1)1470 1161 y Fs(has)g Fk(3)p Fs(-diameter)g(at)g(most)g Fm(d)f Fs(given)g(by)1025 1211 y(the)i Fk(3)p Fs(-partition)d Fm(I)1289 1217 y Fi(j)1307 1211 y Fm(;)g(G;)g(I)1396 1217 y Fi(j)r Fj(+1)1454 1211 y Fs(.)14 b(This)d(completes)f(the)g (proof.)p 1996 1211 V 1074 1261 a(W)m(e)f(comment)f(brie\257y)f(on)h (the)g(running)e(time)i(of)f(this)g(algorithm.)1025 1311 y(In)k(the)g(above)h(proof,)f(the)g Fk(3)p Fs(-diameter)h(of)f(an)h (interval)e(may)i(be)g(re-)1025 1360 y(placed)i(by)g(an)h (easily-computed)f(upper)g(bound:)20 b(at)15 b(the)f(time)g(of)1025 1410 y(creation)8 b(of)g(interval)f Fk([)p Fm(a;)g(b)p Fk(])p Fs(,)h(let)g Fk([)p Fm(x;)f(y)q Fk(])g Fs(be)i(the)f(gap)h (containing)d Fk(\()p Fm(a)t Fk(+)1025 1460 y Fm(b)p Fk(\))p Fm(=)p Fk(2)p Fs(,)11 b(and)g(let)g(the)g(upper)g(bound)f(be)h Fk(m)o(ax)n(\()p Fm(x)g Fl(\000)f Fm(a;)d(y)12 b Fl(\000)f Fm(x;)c(b)i Fl(\000)i Fm(y)q Fk(\))p Fs(.)1025 1510 y(Maintaining)f (the)j Fm(n)f Fs(points)g(sorted)g(in)g(a)h(balanced)g(tree,)h(the)f (run-)1025 1560 y(ning)c(time)h(is)g Fm(O)q Fk(\(log)c Fm(n)p Fk(\))11 b Fs(for)f(each)h(of)f(the)g Fm(n)g Fs(points)f (inserted.)1025 1661 y Ft(3)49 b(The)13 b(Doubling)e(Algorithm)1074 1754 y Fs(W)m(e)g(now)f(describe)h(the)f(Doubling)e(Algorithm)g(which)i (has)h(per)o(-)1025 1803 y(formance)f(ratio)f(8)g(for)h(incremental)f (clustering)g(in)g(general)h(metric)1025 1853 y(spaces.)k(The)8 b(algorithm)d(works)i(in)f(phases)i(and)f(uses)h(two)e(paramet-)1025 1903 y(ers)12 b Fm(\013)f Fs(and)h Fm(\014)i Fs(to)d(be)h(speci\256ed)g (later)n(,)h(such)f(that)f Fm(\013=)p Fk(\()p Fm(\013)f Fl(\000)i Fk(1\))k Fl(\024)g Fm(\014)r Fs(.)1025 1953 y(At)c(the)h(start)g(of)g(phase)g Fm(i)p Fs(,)i(it)d(has)i(a)f (collection)f(of)h Fm(k)h Fk(+)f(1)g Fs(clusters)1025 2003 y Fm(C)1055 2009 y Fj(1)1073 2003 y Fm(;)7 b(C)1122 2009 y Fj(2)1140 2003 y Fm(;)g(:)g(:)g(:)t(;)g(C)1262 2009 y Fi(k)q Fj(+1)1334 2003 y Fs(and)j(a)g(lower)f(bound)g Fm(d)1672 2009 y Fi(i)1695 2003 y Fs(on)h(the)g(optimal)e(clus-)1025 2052 y(tering')n(s)k(diameter)j(\(denoted)e(by)i Fp(O)r(P)r(T)r Fs(\).)26 b(Each)15 b(cluster)f Fm(C)1909 2058 y Fi(i)1937 2052 y Fs(has)h(a)1025 2102 y(center)e Fm(c)1157 2108 y Fi(i)1183 2102 y Fs(which)g(is)f(one)h(of)g(the)f(points)g(of)g(the)h (cluster)n(.)21 b(The)13 b(fol-)1025 2152 y(lowing)c(invariants)g(are)j (assumed)g(at)f(the)f(start)h(of)f(phase)i Fm(i)p Fs(:)i Fn(\(a\))d Fs(for)1025 2202 y(each)e(cluster)e Fm(C)1257 2208 y Fi(j)1274 2202 y Fs(,)i(the)f(radius)g(of)f Fm(C)1534 2208 y Fi(j)1559 2202 y Fs(de\256ned)i(as)f Fk(m)o(ax)1809 2208 y Fi(p)p Fe(2)p Fi(C)1872 2212 y Ff(j)1896 2202 y Fm(d)p Fk(\()p Fm(c)1952 2208 y Fi(j)1970 2202 y Fm(;)f(p)p Fk(\))1025 2252 y Fs(is)13 b(at)g(most)g Fm(\013d)1252 2258 y Fi(i)1265 2252 y Fs(;)i Fn(\(b\))e Fs(for)g(each)h(pair)f(of)g (clusters)g Fm(C)1803 2258 y Fi(j)1834 2252 y Fs(and)g Fm(C)1937 2258 y Fi(l)1950 2252 y Fs(,)h(the)1025 2301 y(inter)o(-center)9 b(distance)i Fm(d)p Fk(\()p Fm(c)1428 2307 y Fi(j)1445 2301 y Fm(;)c(c)1482 2307 y Fi(l)1494 2301 y Fk(\))12 b Fl(\025)g Fm(d)1588 2307 y Fi(i)1601 2301 y Fs(;)e(and,)h Fn(\(c\))f Fm(d)1782 2307 y Fi(i)1807 2301 y Fl(\024)j Fp(O)r(P)r(T)r Fs(.)1074 2351 y(Each)h(phase)f (consists)g(of)f(two)g(stages:)19 b(the)12 b(\256rst)h(is)f(a)h Fr(mer)n(ging)1025 2401 y(stage)d Fs(in)h(which)g(the)g(algorithm)e (reduces)j(the)f(number)g(of)g(clusters)1025 2451 y(by)i(mer)o(ging)g (certain)h(pairs;)g(the)g(second)g(is)f(the)h Fr(update)e(stage)i Fs(in)1025 2501 y(which)d(the)h(algorithm)e(accepts)j(new)g(updates)e (and)h(tries)g(to)f(main-)1025 2551 y(tain)i(at)h(most)g Fm(k)i Fs(clusters)e(without)e(increasing)i(the)g(radius)f(of)h(the) 1025 2600 y(clusters)d(or)g(violating)e(the)j(invariants)e(\(clearly)m (,)j(it)d(can)j(always)e(do)1025 2650 y(so)e(by)g(making)g(the)h(new)f (points)g(into)f(separate)i(clusters\).)k(A)9 b(phase)1025 2700 y(ends)h(when)g(the)g(number)h(of)f(clusters)g(again)g(exceeds)i Fm(k)q Fs(.)p eop %%Page: 5 5 5 4 bop -75 -33 a Fn(De\256nition)10 b(5)20 b Fr(The)14 b Fm(t)p Fs(-threshold)d(graph)i Fr(on)g(a)f(set)i(of)e(points)g Fm(P)26 b Fk(=)-75 16 y Fl(f)p Fm(p)-33 22 y Fj(1)-15 16 y Fm(;)7 b(p)25 22 y Fj(2)43 16 y Fm(;)g(:)g(:)g(:)e(;)i(p)157 22 y Fi(n)179 16 y Fl(g)22 b Fr(is)f(the)h(graph)f Fm(G)49 b Fk(=)i(\()p Fm(P)q(;)7 b(E)r Fk(\))21 b Fr(such)h(that)-75 66 y Fk(\()p Fm(p)-38 72 y Fi(i)-24 66 y Fm(;)7 b(p)16 72 y Fi(j)33 66 y Fk(\))k Fl(2)h Fm(E)g Fr(if)d(and)h(only)g(if)f Fm(d)p Fk(\()p Fm(p)423 72 y Fi(i)437 66 y Fm(;)e(p)477 72 y Fi(j)494 66 y Fk(\))k Fl(\024)h Fm(t)p Fr(.)-25 153 y Fs(The)f(mer)o(ging)f(stage)h(works)f(as)h(follows.)i(De\256ne)e Fm(d)743 159 y Fi(i)p Fj(+1)810 153 y Fk(=)h Fm(\014)r(d)901 159 y Fi(i)915 153 y Fs(,)-75 203 y(and)7 b(let)g Fm(G)h Fs(be)f(the)h Fm(d)209 209 y Fi(i)p Fj(+1)264 203 y Fs(-threshold)e (graph)h(on)g(the)g Fm(k)s Fk(+)r(1)g Fs(cluster)g(cen-)-75 253 y(ters)k Fm(c)14 259 y Fj(1)33 253 y Fm(;)c(c)70 259 y Fj(2)88 253 y Fm(;)g(:)g(:)g(:)e(;)i(c)199 259 y Fi(k)q Fj(+1)261 253 y Fs(.)17 b(The)12 b(graph)f Fm(G)g Fs(is)g(used)h(to)e(mer)o(ge)j(clusters)-75 303 y(by)8 b(repeatedly)g(performing)f(the)h(following)e(steps)i(while)g(the)g (graph)-75 352 y(is)h(non-empty:)i(pick)e(an)g(arbitrary)f(cluster)h Fm(C)597 358 y Fi(i)620 352 y Fs(in)f Fm(G)h Fs(and)g(mer)o(ge)h(all) -75 402 y(its)i(neighbors)g(into)g(it;)h(make)h Fm(c)402 408 y Fi(i)429 402 y Fs(the)f(new)g(cluster)r(')n(s)f(center;)i(and,) -75 452 y(remove)9 b Fm(C)88 458 y Fi(i)110 452 y Fs(and)g(its)f (neighbors)f(from)i Fm(G)p Fs(.)k(Let)c Fm(C)642 437 y Fe(0)639 462 y Fj(1)657 452 y Fm(;)e(C)709 437 y Fe(0)706 462 y Fj(2)724 452 y Fm(;)g(:)g(:)g(:)e(;)i(C)850 437 y Fe(0)847 462 y Fi(m)886 452 y Fs(be)-75 502 y(the)j(new)h(clusters)f (at)g(the)g(end)h(of)f(the)g(mer)o(ging)g(stage.)15 b(Note)10 b(that)f(it)-75 552 y(is)i(possible)f(that)g Fm(m)15 b Fk(=)f Fm(k)e Fk(+)e(1)h Fs(when)g(the)g(graph)g Fm(G)f Fs(has)i(no)f(edges,)-75 602 y(in)e(which)g(case)j(the)d(algorithm)g (will)f(be)i(forced)g(declare)h(the)e(end)h(of)-75 651 y(phase)h Fm(i)g Fs(without)d(going)h(through)f(the)i(update)g(stage.) -75 749 y Fn(Lemma)f(1)21 b Fr(The)f(pairwise)f(distance)h(between)g (cluster)g(centers)-75 799 y(after)10 b(the)g(mer)n(ging)g(stage)g(of)g (phase)g Fm(i)h Fr(is)f(at)f(least)h Fm(d)686 805 y Fi(i)p Fj(+1)742 799 y Fr(.)-75 896 y Fn(Lemma)f(2)21 b Fr(The)10 b(radius)f(of)g(the)h(clusters)f(after)h(the)f(mer)n(ging)h(stage)-75 946 y(of)g(phase)g Fm(i)h Fr(is)f(at)f(most)h Fm(d)291 952 y Fi(i)p Fj(+1)356 946 y Fk(+)f Fm(\013d)446 952 y Fi(i)471 946 y Fl(\024)j Fm(\013d)564 952 y Fi(i)p Fj(+1)619 946 y Fr(.)-25 1043 y Fn(Pr)o(oof:)25 b Fs(Prior)15 b(to)g(the)g(mer)o(ging,)j(the)d(distance)h(between)g(two)-75 1092 y(clusters)11 b(which)g(are)h(adjacent)f(in)g(the)g(threshold)f (graph)h(is)g(at)g(most)-75 1142 y Fm(d)-53 1148 y Fi(i)p Fj(+1)2 1142 y Fs(,)f(and)f(their)f(radius)g(is)h(at)g(most)g Fm(\013d)501 1148 y Fi(i)514 1142 y Fs(.)14 b(Therefore,)c(the)f (radius)f(of)-75 1192 y(the)i(mer)o(ged)h(clusters)f(is)g(at)h(most)90 1286 y Fm(d)112 1292 y Fi(i)p Fj(+1)176 1286 y Fk(+)f Fm(\013d)267 1292 y Fi(i)292 1286 y Fl(\024)h Fk(\(1)f(+)f Fm(\013=\014)r Fk(\))p Fm(d)534 1292 y Fi(i)p Fj(+1)601 1286 y Fl(\024)j Fm(\013d)694 1292 y Fi(i)p Fj(+1)749 1286 y Fm(;)-75 1380 y Fs(where)c(the)g(last)g(inequality)e(follows)h (from)g(the)h(choice)h(that)e Fm(\013=)p Fk(\()p Fm(\013)s Fl(\000)-75 1430 y Fk(1\))k Fl(\024)h Fm(\014)r Fs(.)p 896 1430 30 30 v -25 1481 a(The)c(update)g(stage)g(continues)g(while)f (the)h(number)f(of)h(clusters)g(is)-75 1531 y(at)i(most)h Fm(k)q Fs(.)j(When)d(a)f(new)h(point)e(arrives,)i(the)f(algorithm)f (attempts)-75 1581 y(to)e(place)i(it)e(in)h(one)g(of)g(the)g(current)f (clusters)h(without)e(exceeding)j(the)-75 1630 y(radius)g(bound)f Fm(\013d)198 1636 y Fi(i)p Fj(+1)253 1630 y Fs(:)13 b(otherwise,)c(a)h (new)f(cluster)g(is)g(formed)h(with)-75 1680 y(the)f(update)g(as)g(the) g(cluster)g(center)n(.)14 b(When)9 b(the)g(number)g(of)g(clusters)-75 1730 y(reaches)g Fm(k)s Fk(+)r(1)p Fs(,)g(phase)f Fm(i)g Fs(ends)g(and)f(the)h(current)f(set)h(of)f Fm(k)s Fk(+)r(1)h Fs(clusters)-75 1780 y(along)h(with)g Fm(d)133 1786 y Fi(i)p Fj(+1)199 1780 y Fs(are)i(used)f(as)h(the)e(input)g(for)g(the)h Fk(\()p Fm(i)f Fk(+)g(1\))p Fs(st)h(phase.)-25 1831 y(All)f(that)h (remains)g(to)g(be)g(speci\256ed)h(about)e(the)h(algorithm)f(is)h(the) -75 1881 y(initialization.)h(The)e(algorithm)f(waits)h(until)e Fm(k)g Fk(+)f(1)j Fs(points)f(have)h(ar)o(-)-75 1931 y(rived)g(and)g(then)g(enters)g(phase)h Fk(1)g Fs(with)e(each)i(point)e (as)i(the)f(center)h(of)-75 1981 y(a)g(cluster)f(containing)f(just)g (itself,)h(and)g(with)f Fm(d)604 1987 y Fj(1)632 1981 y Fs(set)i(to)e(the)h(distance)-75 2030 y(between)g(the)f(closest)g (pair)g(of)g(points.)13 b(It)7 b(is)h(easily)h(veri\256ed)f(that)g(the) -75 2080 y(invariants)h(hold)h(at)h(the)f(start)g(of)h(phase)g Fk(1)p Fs(.)k(The)c(following)e(lemma)-75 2130 y(shows)i(that)f(the)g (clusters)h(at)g(the)g(end)f(of)h(the)g Fm(i)p Fs(th)f(phase)h(satisfy) g(the)-75 2180 y(invariants)e(for)h(the)g Fk(\()p Fm(i)g Fk(+)f(1\))p Fs(st)h(phase.)-75 2278 y Fn(Lemma)f(3)21 b Fr(The)7 b Fm(k)q Fk(+1)g Fr(clusters)g(at)g(the)f(end)h(of)f(the)h Fm(i)p Fr(th)g(phase)f(satisfy)-75 2328 y(the)k(following)d (conditions:)-44 2415 y(1.)21 b(The)11 b(radius)e(of)h(the)g(clusters)g (is)h(at)e(most)h Fm(\013d)659 2421 y Fi(i)p Fj(+1)714 2415 y Fr(.)-44 2503 y(2.)21 b(The)12 b(pairwise)f(distance)g(between)h (the)f(cluster)h(centers)h(is)e(at)8 2553 y(least)f Fm(d)119 2559 y Fi(i)p Fj(+1)174 2553 y Fr(.)-44 2641 y(3.)21 b Fm(d)30 2647 y Fi(i)p Fj(+1)101 2641 y Fl(\024)c Fp(O)r(P)r(T)r Fr(,)12 b(wher)n(e)h Fp(O)r(P)r(T)h Fr(is)d(the)g(diameter)g(of)g(the)h (optimal)8 2691 y(clustering)d(for)h(the)g(curr)n(ent)h(set)g(of)f (points.)1074 -33 y Fn(Pr)o(oof:)j Fs(W)m(e)8 b(have)h Fm(k)t Fk(+)s(1)e Fs(clusters)h(at)g(the)f(end)h(of)g(the)f(phase)i (since)1025 16 y(that)h(is)g(the)g(terminating)g(condition.)j(From)e (Lemma)h(2,)f(the)g(radius)1025 66 y(of)g(the)i(clusters)f(after)g(the) g(mer)o(ging)g(stage)h(is)f(at)g(most)h Fm(\013d)1898 72 y Fi(i)p Fj(+1)1965 66 y Fs(and)1025 116 y(from)c(the)h(description) f(of)h(the)g(update)g(stage)g(this)g(bound)f(is)h(not)f(vi-)1025 166 y(olated)h(by)h(the)g(insertion)f(of)h(new)g(points.)16 b(The)11 b(distance)h(between)1025 216 y(the)c(clusters)g(centers)h (after)f(the)g(mer)o(ging)g(stage)h(is)f Fm(d)1786 222 y Fi(i)p Fj(+1)1842 216 y Fs(,)h(and)f(a)h(new)1025 265 y(cluster)g(is)h(created)h(only)e(if)g(a)i(request)f(point)e(is)i(at)g (least)g Fm(d)1872 271 y Fi(i)p Fj(+1)1937 265 y Fs(away)1025 315 y(from)d(all)h(current)f(cluster)h(centers.)14 b(Therefore,)9 b(the)f(cluster)f(centers)1025 365 y(have)k(pairwise)h(distance)f(at)h (least)g Fm(d)1566 371 y Fi(i)p Fj(+1)1621 365 y Fs(.)18 b(Since)12 b(at)f(the)h(end)f(of)g(the)1025 415 y(phase)h(we)g(have)g Fm(k)g Fk(+)g(1)f Fs(cluster)h(centers)g(that)f(are)i Fm(d)1802 421 y Fi(i)p Fj(+1)1869 415 y Fs(apart,)f(the)1025 465 y(optimal)d(clustering)f(is)i(forced)g(to)g(put)f(at)h(least)g(two) g(of)g(them)g(in)f(the)1025 514 y(same)i(cluster)n(.)j(It)c(follows)e (that)j Fp(O)r(P)r(T)i Fl(\025)f Fm(d)1642 520 y Fi(i)p Fj(+1)1698 514 y Fs(.)p 1996 514 V 1074 565 a(Based)g(on)f(these)g (lemmas,)i(we)f(make)g(the)e(following)f(observa-)1025 615 y(tions.)16 b(The)d(algorithm)d(ensures)i(the)f(invariant)g(that)g Fm(d)1837 621 y Fi(i)1866 615 y Fl(\024)17 b Fp(O)r(P)r(T)d Fs(at)1025 665 y(the)7 b(start)f(of)h(phase)h Fm(i)p Fs(.)14 b(The)8 b(radius)f(of)g(the)g(clusters)g(during)f(phase)i Fm(i)f Fs(is)1025 715 y(at)j(most)h Fm(\013d)1206 721 y Fi(i)p Fj(+1)1261 715 y Fs(.)k(Therefore,)d(the)e(performance)i (ratio)e(at)h(any)f(time)1025 765 y(during)g(the)j(phase)g(is)f(at)g (most)h Fk(2)p Fm(\013d)1562 771 y Fi(i)p Fj(+1)1617 765 y Fm(=)q Fp(O)r(P)r(T)20 b Fl(\024)f Fk(2)p Fm(\013\014)r(d)1871 771 y Fi(i)1884 765 y Fm(=)q Fp(O)r(P)r(T)i Fl(\024)1025 814 y Fk(2)p Fm(\013\014)r Fs(.)d(W)m(e)12 b(choose)g Fm(\013)k Fk(=)g Fm(\014)j Fk(=)e(2)p Fs(;)11 b(note,)h(this)f(choice)h (satis\256es)g(the)1025 864 y(condition)d(that)j Fm(\013=)p Fk(\()p Fm(\013)f Fl(\000)h Fk(1\))17 b Fl(\024)h Fm(\014)r Fs(.)i(This)12 b(leads)g(to)g(the)g(following)1025 914 y(performance)f(bound,)e(which)h(can)h(be)g(shown)e(to)h(be)h(tight.) 1025 1001 y Fn(Theor)o(em)g(7)20 b Fr(The)10 b(Doubling)e(Algorithm)g (has)i(performance)g(ratio)1025 1051 y(8)g(in)f(any)i(metric)f(space,)h (and)f(this)f(is)h(tight.)1074 1137 y Fs(An)17 b(examination)f(of)g (the)h(proof)f(of)g(the)g(preceding)h(theorem)1025 1187 y(shows)10 b(that)h(the)g(radius)f(of)h(the)g(clusters)g(is)g(within)e (factor)i(4)g(of)f(the)1025 1237 y(diameter)i(of)h(the)f(optimal)g (clustering,)g(leading)g(to)g(the)h(following)1025 1287 y(result.)1025 1374 y Fn(Cor)o(ollary)c(1)21 b Fr(The)8 b(Doubling)d(Algorithm)h(has)h(performance)h(ratio)1025 1424 y Fk(8)i Fr(for)f(the)i(radius)e(measur)n(e.)1025 1510 y Fs(A)i(simple)g(modi\256cation)f(of)h(the)g(Doubling)e (Algorithm,)h(in)h(which)1025 1559 y(we)d(pick)g(the)g(new)h(cluster)f (centers)h(by)f(a)h(simple)f(left-to-right)d(scan,)1025 1609 y(improves)k(the)h(ratio)g(to)g Fk(6)g Fs(for)g(the)g(case)h(of)f (the)h(line.)1074 1660 y(While)j(the)f(obvious)g(implementation)f(of)i (this)f(algorithm)f(ap-)1025 1710 y(pears)i(to)f(be)h(inef)o (\256cient,)h(we)f(can)h(establish)e(the)h(following)d(time)1025 1760 y(bound,)e(which)h(is)g(close)h(to)e(the)h(best)h(possible.)1025 1856 y Fn(Theor)o(em)g(8)20 b Fr(The)10 b(Doubling)d(Algorithm)h(can)h (be)h(implemented)f(to)1025 1906 y(run)h(in)f Fm(O)q Fk(\()p Fm(k)f Fk(log)f Fm(k)q Fk(\))j Fr(amortized)f(time)h(per)h (update.)1074 2002 y Fn(Pr)o(oof:)22 b Fs(First)13 b(of)g(all,)i(we)f (assume)i(that)d(there)h(is)g(a)g(black-box)1025 2051 y(for)f(computing)g(the)g(distance)h(between)h(two)e(points)g(in)g(the) h(met-)1025 2101 y(ric)g(space)j(in)d(unit)g(time.)28 b(This)15 b(is)g(a)h(reasonable)f(assumption)g(in)1025 2151 y(most)8 b(applications,)g(and)g(in)g(any)g(case)i(even)f(the)f (static)h(algorithms')1025 2201 y(analysis)h(requires)h(such)f(an)i (assumption.)i(In)d(the)f(information)f(re-)1025 2251 y(trieval)g(application,)g(the)h(documents)g(are)h(represented)g(as)g (vectors)1025 2300 y(and)f(the)g(black-box)f(implementation)g(will)g (depend)h(on)g(the)g(vector)1025 2350 y(length)f(as)i(well)e(as)i(the)g (exact)f(de\256nition)f(of)h(distance.)1074 2401 y(W)m(e)k(now)e(show)h (how)f(the)h(Doubling)e(Algorithm)g(may)i(be)g(im-)1025 2451 y(plemented)c(so)g(that)f(the)h(amortized)g(time)g(required)g(for) f(processing)1025 2501 y(each)j(new)f(update)f(is)h(bounded)f(by)g Fm(O)q Fk(\()p Fm(k)f Fk(log)f Fm(k)q Fk(\))p Fs(.)14 b(W)m(e)c(maintain)f(the)1025 2551 y(edge)14 b(lengths)f(of)h(the)g (complete)h(graph)f(induced)g(by)f(the)h(current)1025 2600 y(cluster)e(centers)h(in)f(a)h(heap.)21 b(Since)13 b(there)f(at)h(most)f Fm(k)i Fs(clusters)e(the)1025 2650 y(space)h(requirement)f(is)g Fm(O)q Fk(\()p Fm(k)1454 2635 y Fj(2)1473 2650 y Fk(\))p Fs(.)20 b(When)12 b(a)h(new)g(point)d (arrives,)k(we)1025 2700 y(compute)d(the)h(distance)f(of)h(this)e (point)g(to)h(the)h(each)h(of)e(the)g(current)p eop %%Page: 6 6 6 5 bop -75 -33 a Fs(cluster)10 b(centers,)i(which)e(requires)g Fm(O)q Fk(\()p Fm(k)q Fk(\))h Fs(time.)k(If)10 b(the)g(point)f(is)h (ad-)-75 16 y(ded)k(to)g(one)h(of)f(the)g(current)g(clusters,)i(we)f (are)g(done.)26 b(If,)16 b(on)e(the)-75 66 y(other)7 b(hand)g(the)h(new)g(point)e(initiates)g(a)i(new)g(cluster)n(,)h(we)f (insert)f(into)-75 116 y(the)12 b(heap)h(edges)g(labeled)g(with)e(the)h (distances)h(between)g(this)e(new)-75 166 y(center)d(and)g(the)g (existing)e(cluster)i(centers)g(which)g(takes)g Fm(O)q Fk(\()p Fm(k)g Fk(log)e Fm(k)q Fk(\))-75 216 y Fs(time.)14 b(For)c(accounting)g(purposes)g(in)g(the)g(amortized)g(analysis,)h(we) -75 265 y(associate)e Fk(log)e Fm(k)i Fs(credits)f(with)f(each)j (inserted)d(edge.)14 b(W)m(e)9 b(will)e(show)-75 315 y(that)h(it)g(is)h(possible)f(to)g(char)o(ge)i(the)e(cost)h(of)g (implementing)e(the)i(mer)o(-)-75 365 y(ging)g(stage)i(of)f(the)h (algorithm)e(to)h(the)g(credits)g(associated)h(with)f(the)-75 415 y(edges.)15 b(This)10 b(implies)g(the)g(desired)g(time)g(bound.)-25 471 y(W)m(e)j(can)g(assume,)i(without)c(loss)h(of)g(generality)m(,)h (that)f(the)h(mer)o(-)-75 521 y(ging)8 b(stage)h(mer)o(ges)h(at)f (least)g(two)f(clusters.)13 b(Let)c Fm(t)g Fs(be)g(the)g(threshold)-75 571 y(used)j(during)f(the)h(phase.)21 b(The)13 b(algorithm)e(extracts)h (all)g(the)g(edges)-75 621 y(from)h(the)g(heap)g(which)g(have)g(length) f(less)h(than)g Fm(t)p Fs(.)22 b(Let)14 b Fm(m)f Fs(be)h(the)-75 671 y(number)f(of)f(edges)i(deleted)f(from)f(the)h(heap.)23 b(The)13 b(deletion)f(from)-75 720 y(the)g(heap)h(costs)g Fm(O)q Fk(\()p Fm(m)7 b Fk(log)f Fm(k)q Fk(\))13 b Fs(time.)20 b(The)13 b Fm(t)p Fs(-threshhold)e(graph)h(on)-75 770 y(the)h(cluster)g(centers)h(is)f(exactly)h(the)f(graph)g(induced)f(by)h (these)h Fm(m)-75 820 y Fs(edges.)22 b(It)12 b(is)g(easy)i(to)e(see)i (that)e(the)g(procedure)h(described)g(to)f(\256nd)-75 870 y(the)f(new)h(cluster)f(centers)h(using)f(the)g(threshold)f(graph)h (takes)h(time)-75 920 y(linear)d(in)g(the)h(number)f(of)h(edges)g(of)f (the)g(graph,)h(assuming)g(that)f(the)-75 969 y(edges)h(are)f(given)g (in)f(the)h(form)g(of)g(an)g(adjacency)h(list.)j(Forming)8 b(the)-75 1019 y(adjacency)g(list)e(from)g(the)h(edges)g(takes)h (linear)e(time.)13 b(Therefore,)c(the)-75 1069 y(total)i(cost)h(of)g (the)g(mer)o(ging)g(phase)h(is)f(bounded)f(by)h Fm(O)q Fk(\()p Fm(m)7 b Fk(log)g Fm(k)12 b Fk(+)-75 1119 y Fm(m)p Fk(\))g(=)g Fm(O)q Fk(\()p Fm(m)7 b Fk(log)g Fm(k)q Fk(\))j Fs(time.)j(The)d(credit)g(of)f Fk(log)d Fm(k)11 b Fs(placed)f(with)e (each)-75 1169 y(edge)j(when)f(it)g(is)g(inserted)g(in)f(to)h(the)g (heap)h(accounts)g(for)f(this)f(cost,)-75 1219 y(completing)g(the)h (proof.)p 896 1219 30 30 v -25 1275 a(Finally)m(,)j(we)h(describe)g(a)f (Randomized)g(Doubling)f(Algorithm)-75 1325 y(with)i(signi\256cantly)g (better)g(performance)i(ratio.)28 b(The)16 b(algorithm)-75 1375 y(is)d(essentially)g(the)g(same)i(as)f(before,)g(the)f(main)h (change)g(being)e(in)-75 1424 y(the)f(value)g(of)f Fm(d)155 1430 y Fj(1)184 1424 y Fs(which)h(is)g(the)f(lower)h(bound)f(for)g (phase)h Fk(1)p Fs(.)16 b(In)11 b(the)-75 1474 y(deterministic)f(case)k (we)e(chose)g Fm(d)425 1480 y Fj(1)455 1474 y Fs(to)f(be)g(the)h (minimum)f(pairwise)-75 1524 y(distance)k(of)g(the)g(\256rst)f Fm(k)j Fk(+)f(1)f Fs(points,)g(say)g Fm(x)p Fs(.)28 b(W)m(e)16 b(now)e(choose)-75 1574 y(a)f(random)f(value)h Fm(r)g Fs(from)f Fk([1)p Fm(=e;)7 b Fk(1])k Fs(according)h(to)g(the)g (probability)-75 1624 y(density)g(function)f Fk(1)p Fm(=r)q Fs(,)i(set)g Fm(d)375 1630 y Fj(1)406 1624 y Fs(to)f Fm(r)q(x)p Fs(,)h(and)f(rede\256ne)i Fm(\014)22 b Fk(=)e Fm(e)13 b Fs(and)-75 1674 y Fm(\013)e Fk(=)h Fm(e=)p Fk(\()p Fm(e)p Fl(\000)p Fk(1\))p Fs(.)i(Similar)7 b(randomization)f (of)g(doubling)f(algorithms)-75 1723 y(was)10 b(used)g(earlier)f(in)g (scheduling)g([31)o(],)h(and)f(later)h(in)e(other)h(applic-)-75 1773 y(ations)h([7)o(,)h(18)o(].)-75 1883 y Fn(Theor)o(em)g(9)21 b Fr(The)c(Randomized)g(Doubling)e(Algorithm)h(has)h(ex-)-75 1933 y(pected)c(performance)g(ratio)f Fk(2)p Fm(e)19 b Fl(\031)h Fk(5)p Fm(:)p Fk(437)12 b Fr(in)g(any)h(metric)g(space.)-75 1982 y(The)e(same)f(bound)f(is)i(also)e(achieved)i(for)f(the)g(radius)f (measur)n(e.)-25 2086 y Fn(Pr)o(oof:)19 b Fs(Let)13 b Fm(\033)h Fs(be)f(the)f(sequence)i(of)f(updates)g(and)f(let)h(the)f (op-)-75 2135 y(timal)f(cluster)f(diameter)i(for)e Fm(\033)j Fs(be)e Fm(\015)r(x)p Fs(,)i(where)e Fm(x)g Fs(is)g(the)g(minimum)-75 2185 y(pairwise)e(distance)h(of)f(the)g(\256rst)h Fm(k)e Fk(+)f(1)j Fs(points.)i(The)e(optimal)f(value)-75 2235 y(is)14 b(at)f(least)h Fm(x)p Fs(,)h(hence)g Fm(\015)26 b Fl(\025)d Fk(1)p Fs(.)h(Suppose)14 b(we)g(choose)g Fm(d)785 2241 y Fj(1)827 2235 y Fk(=)23 b Fm(r)q(x)-75 2285 y Fs(for)10 b(some)i Fm(r)i Fl(2)e Fk(\(1)p Fm(=e;)7 b Fk(1])p Fs(.)15 b(Let)c Fm(\032)397 2291 y Fi(r)426 2285 y Fs(be)g(the)g(maximum)g(radius)f(of)h(the)-75 2335 y(clusters)g(created)i(for)d Fm(\033)j Fs(with)d(this)h(value)g (of)g Fm(r)q Fs(.)18 b(Using)10 b(ar)o(guments)-75 2384 y(similar)f(to)h(those)f(in)h(the)g(proof)f(of)g(Theorem)i(7,)f(we)h (can)g(show)e(that)-75 2434 y Fm(\032)-54 2440 y Fi(r)-23 2434 y Fs(is)i(at)h(most)g Fm(d)173 2440 y Fi(i)p Fj(+1)239 2434 y Fk(+)g Fm(\013d)332 2440 y Fi(i)361 2434 y Fk(=)17 b Fm(e)429 2419 y Fi(i)p Fj(+1)485 2434 y Fm(d)507 2440 y Fj(1)525 2434 y Fm(=)p Fk(\()p Fm(e)12 b Fl(\000)f Fk(1\))p Fs(,)i(where)f Fm(i)g Fs(is)g(the)-75 2484 y(lar)o(gest)g (integer)f(such)h(that)g Fm(d)359 2490 y Fi(i)389 2484 y Fk(=)18 b Fm(e)458 2469 y Fi(i)p Fe(\000)p Fj(1)514 2484 y Fm(d)536 2490 y Fj(1)572 2484 y Fk(=)f Fm(e)640 2469 y Fi(i)p Fe(\000)p Fj(1)697 2484 y Fm(r)q(x)g Fl(\024)h Fp(O)r(P)r(T)h Fk(=)-75 2534 y Fm(\015)r(x)p Fs(.)24 b(Let)14 b Fm(i)89 2519 y Fe(\003)122 2534 y Fs(be)f(the)h(integer)e (such)i(that)f Fm(e)552 2519 y Fi(i)564 2506 y Fd(\003)581 2519 y Fe(\000)p Fj(1)648 2534 y Fl(\024)22 b Fm(\015)i(<)f(e)821 2519 y Fi(i)833 2506 y Fd(\003)866 2534 y Fs(and)-75 2591 y Fm(\016)14 b Fk(=)d Fm(\015)r(=e)63 2576 y Fi(i)75 2564 y Fd(\003)95 2591 y Fs(.)j(Then,)c Fm(\032)245 2597 y Fi(r)275 2591 y Fl(\024)339 2573 y Fi(r)q(ex\015)p 324 2582 101 2 v 324 2606 a Fj(\()p Fi(e)p Fe(\000)p Fj(1\))p Fi(\016)438 2591 y Fs(when)f Fm(r)j(>)g(\016)r Fs(,)d(and)g Fm(\032)741 2597 y Fi(r)771 2591 y Fl(\024)827 2573 y Fi(r)q(e)859 2560 y Fg(2)875 2573 y Fi(x\015)p 820 2582 V 820 2606 a Fj(\()p Fi(e)p Fe(\000)p Fj(1\))p Fi(\016)-75 2650 y Fs(when)i Fm(r)k Fl(\024)g Fm(\016)r Fs(.)i(Let)11 b Fm(X)257 2635 y Fe(\000)254 2660 y Fi(r)297 2650 y Fs(and)g Fm(X)405 2635 y Fj(+)402 2660 y Fi(r)445 2650 y Fs(be)g(indicator)f(variables)h(for)g(the)-75 2700 y(the)h(events)f Fk([)p Fm(r)17 b Fl(\024)g Fm(\016)r Fk(])11 b Fs(and)h Fk([)p Fm(r)k(>)h(\016)r Fk(])p Fs(,)12 b(respectively)m(.)18 b(W)m(e)12 b(claim)g(that)1025 -33 y(the)e(expected)h(value)f(of)g Fm(\032)1410 -27 y Fi(r)1439 -33 y Fs(is)g(bounded)f(by)1165 82 y Fm(E)r Fk([)p Fm(\032)1231 88 y Fi(r)1249 82 y Fk(])41 b Fl(\024)1376 26 y Fh(Z)1418 36 y Fj(1)1399 120 y(1)p Fi(=e)1463 54 y Fm(r)q(e\015)r(x)p Fk(\()p Fm(eX)1621 39 y Fe(\000)1618 65 y Fi(r)1660 54 y Fk(+)9 b Fm(X)1738 39 y Fj(+)1735 65 y Fi(r)1766 54 y Fk(\))p 1463 73 320 2 v 1541 111 a Fm(\016)r(r)q Fk(\()p Fm(e)h Fl(\000)f Fk(1\))1787 82 y Fs(d)p Fm(r)1302 209 y Fk(=)1409 181 y Fm(e)q Fp(O)r(P)r(T)p 1381 200 144 2 v 1381 238 a Fm(\016)r Fk(\()p Fm(e)h Fl(\000)f Fk(1\))1536 153 y Fh(Z)1578 163 y Fj(1)1559 247 y(1)p Fi(=e)1611 209 y Fk(\()p Fm(eX)1683 192 y Fe(\000)1680 219 y Fi(r)1721 209 y Fk(+)h Fm(X)1800 192 y Fj(+)1797 219 y Fi(r)1828 209 y Fk(\))p Fs(d)p Fm(r)1302 330 y Fk(=)1381 302 y Fm(e)q Fp(O)r(P)r(T)r Fm(\016)r Fk(\()p Fm(e)g Fl(\000)g Fk(1\))p 1381 320 232 2 v 1425 359 a Fm(\016)r Fk(\()p Fm(e)g Fl(\000)g Fk(1\))1629 330 y(=)i Fm(e)q Fp(O)r(P)r(T)r Fm(:)1025 440 y Fs(Therefore,)f(the)f(expected)h (diameter)g(is)f(at)g(most)g Fk(2)p Fm(e)q Fp(O)r(P)r(T)r Fs(.)p 1996 440 30 30 v 1025 546 a Ft(4)49 b(The)13 b(Clique)e (Partition)h(Algorithm)1074 645 y Fs(W)m(e)17 b(now)e(describe)i(the)f (Clique)f(Algorithm)f(which)h(has)i(per)o(-)1025 694 y(formance)f(ratio)f(6.)30 b(This)15 b(does)h(not)f(totally)e(improve)j (upon)e(the)1025 744 y(Doubling)9 b(Algorithm)g(since)j(the)f(new)h (algorithm)e(involves)g(solv-)1025 794 y(ing)i(the)h(NP-hard)g(clique)g (partition)e(problem,)j(even)f(though)f(it)g(is)1025 844 y(only)h(on)h(a)h(graph)f(with)g Fm(k)i Fk(+)f(1)f Fs(vertices.)28 b(Finding)12 b(a)k(minimum)1025 894 y(clique)8 b(partition)e(is)i(NP-hard)h(even)g(for)f(graphs)g(induced)g(by)h (points)1025 944 y(in)f(the)h(Euclidean)g(plane)g([17)o(],)g(although)f (it)g(is)h(in)f(polynomial)f(time)1025 993 y(for)i(points)g(on)h(the)g (line.)j(Since)d(the)g(algorithm)f(needs)i(to)e(solve)h(the)1025 1043 y(clique)h(partition)f(problem)h(on)g(graphs)h(with)f Fm(k)h Fk(+)g(1)f Fs(vertices,)i(this)1025 1093 y(may)d(not)g(be)g(too) g(inef)o(\256cient)g(for)g(small)g Fm(k)q Fs(.)1025 1181 y Fn(De\256nition)f(6)21 b Fr(Given)15 b(an)f(undir)n(ected)h (unweighted)e(graph)h Fm(G)27 b Fk(=)1025 1230 y(\()p Fm(V)r(;)7 b(E)r Fk(\))p Fr(,)j(an)g Fm(l)q Fr(-clique)g(partition)e (is)h(a)h(partition)e(of)i Fm(V)21 b Fk(=)11 b Fm(V)1881 1236 y Fj(1)1909 1230 y Fl([)e Fm(V)1970 1236 y Fj(2)1997 1230 y Fl([)1025 1280 y Fm(:)e(:)g(:)e Fl([)i Fm(V)1139 1286 y Fi(l)1160 1280 y Fr(such)j(that)e(the)h(the)g(induced)g(graphs)g Fm(G)p Fk([)p Fm(V)1775 1286 y Fi(i)1788 1280 y Fk(])p Fr(')-5 b(s)9 b(ar)n(e)h(cliques.)1025 1330 y(A)i Fs(minimum)f(clique)g (partition)f Fr(is)h(an)h Fm(l)q Fr(-clique)f(partition)e(with)h(the) 1025 1380 y(minimum)e(possible)i(value)g(of)g Fm(l)q Fr(.)1074 1468 y Fs(The)e(Clique)e(Algorithm)f(is)i(similar)g(to)f(the) h(Doubling)f(algorithm)1025 1517 y(in)j(that)h(it)f(also)h(operates)h (in)f(phases)h(which)e(have)i(a)g(mer)o(ging)f(stage)1025 1567 y(followed)h(by)h(an)h(update)g(stage.)22 b(The)14 b(invariants)d(maintained)h(by)1025 1617 y(the)j(algorithm)g(are)h(dif) o(ferent)f(though.)30 b(At)15 b(the)h(start)f(of)h(the)f Fm(i)p Fs(th)1025 1667 y(phase)8 b(we)g(have)g Fm(k)s Fk(+)r(1)g Fs(clusters)f Fm(C)1521 1673 y Fj(1)1539 1667 y Fm(;)g(C)1588 1673 y Fj(2)1606 1667 y Fm(;)g(:)g(:)g(:)e(;)i(C)1729 1673 y Fi(k)q Fj(+1)1798 1667 y Fs(and)h(a)g(value)g Fm(d)2012 1673 y Fi(i)1025 1717 y Fs(such)h(that:)j Fn(\(a\))d Fs(the)g(radius)f(of)h(each)h(cluster)f Fm(C)1704 1723 y Fi(j)1731 1717 y Fs(is)g(at)g(most)g Fk(2)p Fm(d)1940 1723 y Fi(i)1953 1717 y Fs(;)g(the)1025 1766 y(diameter)f(of)g(each)i (cluster)e Fm(C)1455 1772 y Fi(j)1481 1766 y Fs(is)g(at)g(most)g Fk(3)p Fm(d)1687 1772 y Fi(i)1701 1766 y Fs(;)g(and,)h Fn(\(c\))g Fm(d)1877 1772 y Fi(i)1902 1766 y Fl(\024)k Fp(O)r(P)r(T)r Fs(.)1074 1816 y(The)e(mer)o(ging)f(works)f(as)i (follows.)h(Let)f Fm(d)1689 1822 y Fi(i)p Fj(+1)1756 1816 y Fk(=)h(2)p Fm(d)1843 1822 y Fi(i)1856 1816 y Fs(.)i(W)m(e)c (form)1025 1866 y(the)g(minimum)h(clique)f(partition)f(of)h(the)h Fm(d)1652 1872 y Fi(i)p Fj(+1)1708 1866 y Fs(-threshold)e(graph)h Fm(G)1025 1916 y Fs(of)i(the)g(cluster)g(centers.)21 b(The)13 b(new)g(clusters)f(are)h(then)f(formed)g(by)1025 1966 y(mer)o(ging)i(the)h(clusters)h(in)e(each)j(clique)d(of)h(the)g (clique)g(partition.)1025 2016 y(W)m(e)9 b(arbitrarily)f(choose)i(one)f (cluster)h(from)f(each)i(clique)e(and)g(make)1025 2065 y(its)j(center)i(the)f(cluster)h(center)f(of)h(the)f(new)g(mer)o(ged)i (cluster)n(.)23 b(Let)1025 2115 y Fm(C)1058 2100 y Fe(0)1055 2125 y Fj(1)1073 2115 y Fm(;)7 b(C)1125 2100 y Fe(0)1122 2125 y Fj(2)1140 2115 y Fm(;)g(:)g(:)g(:)t(;)g(C)1265 2100 y Fe(0)1262 2127 y Fi(l)1272 2131 y Ff(i)1301 2115 y Fs(be)14 b(the)g(resulting)e(clusters.)24 b(In)14 b(the)f(rest)h(of)f (the)1025 2165 y(phase)i(we)h(also)e(need)i(to)e(know)g(which)h(old)f (clusters)h(mer)o(ged)h(to)1025 2215 y(form)10 b(each)h(of)f(the)g(new) h(clusters.)1025 2303 y Fn(Lemma)e(4)20 b Fr(The)10 b(radius)f(of)h (the)f(clusters)h(after)f(the)h(mer)n(ging)f(stage)1025 2352 y(is)h(at)f(most)h Fk(2)p Fm(d)1237 2358 y Fi(i)p Fj(+1)1303 2352 y Fr(and)f(the)h(diameter)g(is)g(at)g(most)g Fk(3)p Fm(d)1807 2358 y Fi(i)p Fj(+1)1862 2352 y Fr(.)1074 2440 y Fn(Pr)o(oof:)37 b Fs(Let)22 b Fm(C)1330 2446 y Fi(j)1344 2450 y Fg(1)1362 2440 y Fm(;)7 b(C)1411 2446 y Fi(j)1425 2450 y Fg(2)1442 2440 y Fm(;)g(:)g(:)g(:)e(;)i(C)1565 2446 y Fi(j)1579 2450 y Ff(n)1597 2457 y(j)1637 2440 y Fs(be)22 b(the)f(clusters)h(whose)1025 2496 y(union)7 b(is)i(the)g(new)g(cluster)g Fm(C)1456 2481 y Fe(0)1453 2507 y Fi(j)1479 2496 y Fs(and)g(without)e(loss)i(of)f(generality)h (as-)1025 2546 y(sume)14 b(that)f(the)g(center)h(of)g Fm(C)1460 2552 y Fi(j)1474 2556 y Fg(1)1505 2546 y Fs(was)g(chosen)g (to)f(be)h(the)f(center)h(of)1025 2596 y Fm(C)1058 2581 y Fe(0)1055 2607 y Fi(j)1072 2596 y Fs(.)k(Since)13 b(the)e(centers)i (of)e Fm(C)1473 2602 y Fi(j)1487 2606 y Fg(1)1505 2596 y Fm(;)c(C)1554 2602 y Fi(j)1568 2606 y Fg(2)1585 2596 y Fm(;)g(:)g(:)g(:)e(;)i(C)1708 2602 y Fi(j)1722 2606 y Ff(n)1740 2613 y(j)1771 2596 y Fs(induce)k(a)i(clique)1025 2650 y(in)7 b(the)i Fm(d)1147 2656 y Fi(i)p Fj(+1)1202 2650 y Fs(-threshold)e(graph,)i(the)f(distance)h(from)f(the)h(new)g (center)1025 2700 y(to)h(each)h(of)g(the)f(old)g(cluster)g(centers)i (is)e(at)h(most)f Fm(d)1767 2706 y Fi(i)p Fj(+1)1823 2700 y Fs(.)15 b(The)d(radius)p eop %%Page: 7 7 7 6 bop -75 -33 a Fs(of)8 b(each)h(of)f Fm(C)125 -27 y Fi(j)139 -23 y Fg(1)157 -33 y Fm(;)f(C)206 -27 y Fi(j)220 -23 y Fg(2)237 -33 y Fm(;)g(:)g(:)g(:)e(;)i(C)360 -27 y Fi(j)374 -23 y Ff(n)392 -16 y(j)419 -33 y Fs(is)h(at)g(most)g Fk(2)p Fm(d)625 -27 y Fi(i)639 -33 y Fs(.)13 b(Therefore)c(it)f(fol-) -75 21 y(lows)i(that)g(the)h(new)g(radius)f(is)h(at)g(most)f Fm(d)534 27 y Fi(i)p Fj(+1)600 21 y Fk(+)g(2)p Fm(d)685 27 y Fi(i)711 21 y Fl(\024)j Fk(2)p Fm(d)799 27 y Fi(i)p Fj(+1)866 21 y Fs(and)-75 70 y(the)d(diameter)h(is)f(at)g(most)g Fk(2)p Fm(d)354 76 y Fi(i)377 70 y Fk(+)f Fm(d)440 76 y Fi(i)p Fj(+1)505 70 y Fk(+)g(2)p Fm(d)589 76 y Fi(i)614 70 y Fl(\024)j Fk(3)p Fm(d)701 76 y Fi(i)p Fj(+1)756 70 y Fs(.)p 896 70 30 30 v -25 120 a(During)d(the)i(update)f(phase,)i (a)f(new)g(point)f Fm(p)g Fs(is)h(handled)f(as)i(fol-)-75 170 y(lows.)20 b(Let)13 b(the)g(current)f(number)g(of)h(clusters)f(be)h Fm(m)p Fs(,)h(where)f Fm(l)860 176 y Fi(i)893 170 y Fl(\024)-75 220 y Fm(m)j Fl(\024)g Fm(k)q Fs(.)i(Recall)12 b(that)f Fm(C)301 205 y Fe(0)298 230 y Fj(1)316 220 y Fm(;)c(C)368 205 y Fe(0)365 230 y Fj(2)383 220 y Fm(;)g(:)g(:)g(:)e(;)i(C)509 205 y Fe(0)506 232 y Fi(l)516 236 y Ff(i)542 220 y Fs(are)13 b(the)e(clusters)h(formed)-75 270 y(during)f(the)h(mer)o(ging)g(stage.) 20 b(If)12 b(there)h(exists)e Fm(j)k Fs(such)e(that)e Fm(j)21 b(>)d(l)911 276 y Fi(i)-75 319 y Fs(and)10 b Fm(d)p Fk(\()p Fm(p;)d(c)91 304 y Fe(0)91 330 y Fi(j)108 319 y Fk(\))k Fl(\024)h Fm(d)201 325 y Fi(i)p Fj(+1)257 319 y Fs(,)e(or)g(if)f Fm(j)14 b Fl(\024)e Fm(l)444 325 y Fi(i)468 319 y Fs(and)e Fm(d)p Fk(\()p Fm(p;)d(c)634 325 y Fi(j)648 329 y Ff(s)665 319 y Fk(\))12 b Fl(\024)g Fm(d)759 325 y Fi(i)p Fj(+1)824 319 y Fs(where)-75 369 y Fm(C)-45 375 y Fi(j)-31 379 y Ff(s)-5 369 y Fs(is)c(a)h(cluster)g (which)f(mer)o(ged)h(to)f(form)g Fm(C)583 354 y Fe(0)580 380 y Fi(j)597 369 y Fs(,)i(add)e Fm(p)h Fs(to)f(the)g(cluster)-75 419 y Fm(C)-42 404 y Fe(0)-45 430 y Fi(j)-28 419 y Fs(.)14 b(If)9 b(no)g(such)g Fm(j)j Fs(exists,)d(make)h(a)g(new)f(cluster)g (with)f Fm(p)h Fs(as)h(the)f(cen-)-75 469 y(ter)n(.)17 b(The)12 b(phase)g(ends)f(when)h(the)f(number)g(of)g(clusters)g (exceeds)i Fm(k)q Fs(,)-75 519 y(or)d(if)f(there)h(are)g Fm(k)f Fk(+)g(1)h Fs(clusters)f(at)h(the)g(end)g(of)f(the)h(mer)o(ging) g(phase.)-25 569 y(The)j(intuition)c(behind)j(the)g(new)h(algorithm)e (is)h(the)h(following.)-75 618 y(At)h(the)g(beginning)e(of)i(the)g (phase)h(we)g(have)g Fm(k)g Fk(+)g(1)f Fs(clusters)h(and)-75 668 y(a)f(lower)g(bound)e(on)i(the)f(optimal.)24 b(W)m(e)14 b(use)g(the)g(lower)g(bound)e(to)-75 718 y(increase)i(the)e(radius)g (of)g(our)g(existing)f(clusters)i(and)f(mer)o(ge)i(some)-75 768 y(of)g(them.)26 b(T)m(o)15 b(maintain)f(the)g(invariant)f(for)h (the)g(lower)g(bound)f(in)-75 818 y(the)i(next)f(phase)h(we)g(need)h (to)e(ensure)h(during)e(this)h(mer)o(ging)g(that)-75 867 y(the)c(number)h(of)f(clusters)g(we)h(have)g(after)g(the)f(mer)o (ging)g(is)g(no)g(more)-75 917 y(that)g(what)h(the)g(optimal)f (algorithm)f(can)j(achieve)f(using)f(the)h(lower)-75 967 y(bound)g(for)g(the)g(next)g(phase.)19 b(The)12 b(doubling)e (algorithm)g(achieved)-75 1017 y(this)k(by)g(picking)g(an)h (independent)f(set)h(as)h(the)e(new)h(cluster)g(cen-)-75 1067 y(ters)g(in)f(the)g(distance)h(threshold)e(graph.)26 b(The)16 b(weakness)f(of)g(this)-75 1116 y(approach)f(is)g(that)f(we)h (have)h(a)f(bound)f(on)h(the)f(diameter)n(,)j(only)d(as)-75 1166 y(a)h(function)e(of)h(the)g(radius)g(of)g(the)g(new)g(cluster)n(.) 23 b(W)m(e)14 b(get)f(the)g(im-)-75 1216 y(provement)g(by)g(observing)f (that)g(a)i(better)f(bound)f(on)h(the)g(number)-75 1266 y(of)d(clusters)g(achievable)g(by)g(the)f(optimal)g(with)g(diameter)i (bounded)-75 1316 y(by)h Fm(d)1 1322 y Fi(i)26 1316 y Fs(is)g(the)f(size)i(of)f(the)f(minimum)h(clique)f(partition)f(of)h (the)h(dis-)-75 1366 y(tance)d(threshold)e(graph.)13 b(W)m(e)c(still)e(need)i(a)g(condition)d(on)i(the)g(radius)-75 1415 y(in)g(order)f(to)h(do)g(the)g(doubling,)e(but)i(now)m(,)h(since)f (we)h(use)f(cliques,)h(we)-75 1465 y(can)i(bound)f(the)g(diameter)h(of) f(the)g(new)h(clusters)f(better)h(than)f(twice)-75 1515 y(the)g(radius.)-25 1565 y(The)g(following)c(lemmas)11 b(show)e(that)f(the)h(clusters)g(at)h(the)f(end)g(of)-75 1615 y(phase)i Fm(i)g Fs(satisfy)e(the)h(invariants)g(for)f(phase)i Fm(i)f Fk(+)f(1)p Fs(.)-75 1694 y Fn(Lemma)g(5)21 b Fr(The)11 b(radius)f(of)g(the)h(clusters)g(at)f(the)h(end)g(of)f(the)h(phase)-75 1744 y Fm(i)g Fr(is)f(at)g(most)g Fk(2)p Fm(d)163 1750 y Fi(i)p Fj(+1)229 1744 y Fr(and)g(the)g(diameter)h(of)f(the)g (clusters)h(is)f(at)g(most)-75 1794 y Fk(3)p Fm(d)-32 1800 y Fi(i)p Fj(+1)23 1794 y Fr(.)-75 1873 y Fn(Lemma)f(6)21 b Fr(At)10 b(the)g(end)h(of)e(phase)i Fm(i)p Fr(,)g Fm(d)499 1879 y Fi(i)p Fj(+1)566 1873 y Fl(\024)h Fp(O)r(P)r(T)r Fr(.)-25 1953 y Fn(Pr)o(oof:)h Fs(Suppose)7 b Fm(d)270 1959 y Fi(i)p Fj(+1)337 1953 y Fm(>)13 b Fp(O)r(P)r(T)r Fs(.)g(Let)c Fm(S)14 b Fk(=)e Fl(f)p Fm(c)659 1959 y Fj(1)677 1953 y Fm(;)7 b(c)714 1959 y Fj(2)732 1953 y Fm(;)g(:)g(:)g(:)e(;)i(c)843 1959 y Fi(k)q Fj(+1)905 1953 y Fl(g)-75 2003 y Fs(be)i(the)g(cluster)f(centers)i(at)f(the)f (beginning)f(of)i(the)f(phase.)15 b(Note)8 b(that)-75 2052 y(the)j(centers)i Fm(c)135 2037 y Fe(0)135 2063 y Fj(1)153 2052 y Fm(;)7 b(:)g(:)g(:)e(;)i(c)264 2037 y Fe(0)264 2064 y Fi(l)274 2068 y Ff(i)301 2052 y Fs(belong)j(to)h Fm(S)r Fs(.)19 b(Let)12 b Fm(S)619 2037 y Fe(0)648 2052 y Fk(=)k Fl(f)p Fm(c)735 2037 y Fe(0)735 2063 y Fi(j)768 2052 y Fl(j)f Fm(j)j(>)f(l)891 2058 y Fi(i)905 2052 y Fl(g)-75 2102 y Fs(be)11 b(the)f(set)h(of)f(cluster)h(centers)g(of)f (the)h(clusters)f(which)g(are)i(formed)-75 2152 y(in)e(phase)i Fm(i)g Fs(after)f(the)g(mer)o(ging)g(stage.)17 b(Since)11 b(each)h(of)f(the)g(centers)-75 2202 y Fm(c)-57 2187 y Fe(0)-57 2213 y Fi(j)-26 2202 y Fs(in)i Fm(S)47 2187 y Fe(0)74 2202 y Fs(started)g(a)h(new)g(cluster)g Fm(d)p Fk(\()p Fm(c)494 2187 y Fe(0)494 2213 y Fi(j)511 2202 y Fm(;)7 b(p)p Fk(\))23 b Fm(>)g(d)667 2208 y Fi(i)p Fj(+1)736 2202 y Fs(for)14 b(all)f Fm(p)23 b Fl(2)-75 2252 y Fm(S)t Fl([)q Fm(S)10 2237 y Fe(0)23 2252 y Fl(\000)q(f)p Fm(c)95 2237 y Fe(0)95 2262 y Fi(j)113 2252 y Fl(g)p Fs(.)13 b(Therefore)8 b(in)f(the)g(optimal)f(solution)f(each)j(center)g (in)-75 2301 y Fm(S)-48 2286 y Fe(0)-26 2301 y Fs(is)i(in)f(a)i (cluster)e(which)g(contains)h(no)f(center)h(in)g Fm(S)r Fs(.)15 b(This)9 b(implies)-75 2351 y(that)i(the)g(centers)h(in)f Fm(S)j Fs(are)f(contained)e(in)f(at)i(most)f Fm(l)698 2357 y Fi(i)723 2351 y Fl(\000)g Fk(1)h Fs(clusters)-75 2401 y(of)c(diameter)i Fm(d)145 2407 y Fi(i)p Fj(+1)200 2401 y Fs(.)k(This)9 b(is)f(a)i(contradiction)c(since)k Fm(l)705 2407 y Fi(i)728 2401 y Fs(was)f(the)g(size)-75 2451 y(of)h(the)h(minimum)f(clique)g(partition)f(of)h(the)g Fm(d)596 2457 y Fi(i)p Fj(+1)652 2451 y Fs(-threshold)f(graph)-75 2501 y(on)h Fm(S)r Fs(.)p 896 2501 V -25 2551 a(The)18 b(diameter)f(of)g(the)g(clusters)g(during)f(phase)i Fm(i)f Fs(is)g(at)h(most)-75 2600 y Fk(3)p Fm(d)-32 2606 y Fi(i)p Fj(+1)37 2600 y Fs(and)c(we)g(maintain)f(the)h(invariant)e(that)h Fm(d)656 2606 y Fi(i)693 2600 y Fl(\024)24 b Fp(O)r(P)r(T)16 b Fs(at)e(the)-75 2650 y(start)f(of)g(the)h(phase.)24 b(Therefore,)16 b(the)d(performance)i(ratio)d(of)i(this)-75 2700 y(algorithm)9 b(is)h(at)g(most)g Fk(3)p Fm(d)309 2706 y Fi(i)p Fj(+1)365 2700 y Fm(=d)408 2706 y Fi(i)432 2700 y Fl(\024)i Fk(6)p Fs(.)1025 -33 y Fn(Theor)o(em)f(10)20 b Fr(The)9 b(Clique)f(Algorithm)f(has)i(performance)g(ratio)f Fk(6)1025 16 y Fr(in)h(any)h(metric)h(space,)g(and)f(this)f(is)h (tight.)1074 100 y Fs(Since)i(the)f(radius)g(of)h(the)f(clusters)g(is)h (within)d Fk(4)j Fs(of)f(the)g(optimal)1025 150 y(diameter)n(,)g(we)g (obtain)e(the)h(following)e(corollary)m(.)1025 242 y Fn(Cor)o(ollary)h(2)21 b Fr(The)10 b(Clique)g(Algorithm)f(has)h (performance)h(ratio)e Fk(8)1025 292 y Fr(in)g(any)h(metric)h(space)g (for)f(the)g(radius)f(measur)n(e.)1074 384 y Fs(As)g(in)f(the)h(case)h (of)e(the)h(Doubling)d(Algorithm,)i(we)h(can)g(use)g(ran-)1025 434 y(domization)d(to)i(improve)f(the)h(bound.)k(Let)c Fm(x)g Fs(be)g(the)g(minimum)g(dis-)1025 483 y(tance)g(among)g(the)g (\256rst)f Fm(k)t Fk(+)s(1)h Fs(points.)k(The)d(randomized)f(algorithm) 1025 533 y(sets)g Fm(d)1117 539 y Fj(1)1147 533 y Fk(=)k Fm(r)q(x)c Fs(in)g(phase)g Fk(1)h Fs(of)f(the)g(deterministic)f (algorithm,)h(where)1025 583 y Fm(r)i Fs(is)f(chosen)g(from)g Fk([1)p Fm(=)p Fk(2)p Fm(;)e Fk(1])g Fs(according)i(to)g(the)g (probability)d(density)1025 633 y(function)1208 617 y Fj(1)p 1180 624 72 2 v 1180 647 a Fi(r)h Fj(ln)f(2)1257 633 y Fs(.)20 b(The)12 b(analysis)g(is)g(similar)g(to)f(that)g(of)h (Theorem)h(9)1025 683 y(and)d(we)h(omit)e(the)h(details.)1025 775 y Fn(Theor)o(em)h(1)n(1)20 b Fr(The)f(Randomized)g(Clique)f (Algorithm)g(has)h(per)o(-)1025 825 y(formance)10 b(ratio)1304 808 y Fj(3)p 1288 815 50 2 v 1288 839 a(ln)c(2)1354 825 y Fl(\031)12 b Fk(4)p Fm(:)p Fk(33)d Fr(in)h(any)g(metric)h(space.)1025 917 y Fn(Cor)o(ollary)e(3)21 b Fr(The)g(Randomized)f(Clique)f (Algorithm)g(has)i(per)o(-)1025 967 y(formance)13 b(ratio)1312 950 y Fj(4)p 1295 957 V 1295 981 a(ln)7 b(2)1374 967 y Fl(\031)24 b Fk(5)p Fm(:)p Fk(77)13 b Fr(for)h(the)f(radius)h(measur) n(e)h(in)e(any)1025 1016 y(metric)d(space.)1074 1109 y Fs(The)19 b(special)g(structure)e(of)h(the)g(clusters)g(in)g(the)g (Clique)f(Al-)1025 1158 y(gorithm)11 b(can)i(be)g(used)g(to)g(show)f (that)g(the)h(performance)h(ratio)e(for)1025 1208 y(the)i(radius)g (measure)j(is)d(better)h(than)f Fk(8)g Fs(for)h(the)f(geometric)h (case.)1025 1258 y(This)d(is)g(based)h(on)e(the)h(following)e(result)i (in)f(geometry;)i(we)g(defer)1025 1308 y(the)d(proofs)f(of)h(the)g (proposition)e(and)i(its)g(consequence.)1025 1400 y Fn(Pr)o(oposition)f (12)21 b Fr(Any)12 b(convex)g(set)g(in)e Fm(R)1637 1385 y Fi(d)1668 1400 y Fr(of)h(diameter)g(at)f(most)h Fk(1)1025 1450 y Fr(can)e(be)h(cir)n(cumscribed)h(by)f(a)g(spher)n(e)h(of)e (radius)g Fm(r)1765 1456 y Fi(d)1785 1450 y Fr(,)h(wher)n(e)h Fm(r)1934 1456 y Fi(d)1963 1450 y Fr(sat-)1025 1500 y(is\256es)f(the)g (following)d(r)n(ecurr)n(ence)14 b(with)9 b(the)h(base)g(case)h Fm(r)1868 1506 y Fj(1)1898 1500 y Fk(=)h(1)p Fm(=)p Fk(2)p Fr(,)1360 1611 y Fm(r)1379 1617 y Fi(d)1410 1611 y Fk(=)1555 1583 y(1)p 1459 1601 215 2 v 1459 1656 a(2)1480 1610 y Fh(q)p 1521 1610 153 2 v 1521 1656 a Fk(1)d Fl(\000)g Fm(r)1612 1641 y Fj(2)1611 1668 y Fi(d)p Fe(\000)p Fj(1)1678 1611 y Fm(:)1025 1768 y Fr(The)h(solution)e(to)i(this)f(r)n(ecurr)n (ence)14 b(is)c Fm(r)1601 1774 y Fi(d)1631 1768 y Fk(=)1675 1732 y Fh(p)p 1717 1732 189 2 v 36 x Fm(d=)p Fk(\(2)p Fm(d)e Fk(+)h(2\))p Fr(.)1025 1860 y Fn(Theor)o(em)i(13)20 b Fr(The)15 b(Clique)f(Algorithm)f(has)i(performance)g(ratio)1025 1909 y Fk(4\(1)s(+)s Fm(r)1140 1915 y Fi(d)1159 1909 y Fk(\))8 b Fr(for)f(the)h Fs(radius)g Fr(measur)n(e)h(in)e Fm(R)1627 1894 y Fi(d)1646 1909 y Fr(.)14 b(This)7 b(implies)g (perform-)1025 1959 y(ance)g(ratio)g Fk(6)g Fr(for)g Fm(d)k Fk(=)h(1)p Fr(,)c Fk(6)p Fm(:)p Fk(3)f Fr(for)g Fm(d)k Fk(=)h(2)p Fr(,)c(and)f Fk(6)p Fm(:)p Fk(83)f Fr(asymptotically)1025 2009 y(for)j(lar)n(ge)i Fm(d)p Fr(.)1025 2118 y Ft(5)49 b(Lower)13 b(Bounds)1074 2218 y Fs(W)m(e)e(present)f(some)h(lower)e(bounds)h(on)f(the)h(performance)h (of)f(in-)1025 2268 y(cremental)k(clustering.)23 b(The)15 b(lower)e(bounds)g(apply)g(to)g(both)f(dia-)1025 2317 y(meter)h(and)h(radius)f(measures)h(but)f(our)f(proofs)h(are)h(given)f (for)f(the)1025 2367 y(diameter)h(case.)26 b(The)14 b(following)d (theorem)i(shows)h(that)f(even)h(for)1025 2417 y(the)9 b(simplest)g(geometric)g(space,)j(we)e(cannot)f(expect)h(a)g(ratio)e (better)1025 2467 y(than)h(2;)h(the)g(proof)f(is)h(omitted.)1025 2551 y Fn(Theor)o(em)h(14)20 b Fr(For)14 b Fm(k)24 b Fk(=)g(2)p Fr(,)15 b(ther)n(e)f(is)g(a)g(lower)f(bound)g(of)g Fk(2)h Fr(and)1025 2600 y Fk(2)r Fl(\000)r Fk(1)p Fm(=)p Fk(2)1145 2585 y Fi(k)q(=)p Fj(2)1204 2600 y Fr(on)7 b(the)h(performance)f(ratio)g(of)f(deterministic)h(and)g(ran-)1025 2650 y(domized)j(algorithms,)f(r)n(espectively)n(,)14 b(for)c(incr)n(emental)h(clustering)1025 2700 y(on)e(the)h(line.)p eop %%Page: 8 8 8 7 bop -25 -33 a Fs(In)14 b(the)f(case)j(of)e(general)g(metric)g (spaces,)j(we)e(can)g(establish)e(a)-75 16 y(stronger)c(lower)h(bound.) -75 89 y Fn(Theor)o(em)h(15)20 b Fr(Ther)n(e)12 b(is)e(a)h(lower)f (bound)f(of)h Fk(1)f(+)667 55 y Fl(p)p 702 55 21 2 v 34 x Fk(2)j Fl(\031)g Fk(2)p Fm(:)p Fk(414)d Fr(on)-75 139 y(the)h(performance)g(ratio)f(of)g(any)h(deterministic)f(incr)n (emental)h(clus-)-75 189 y(tering)g(algorithm)e(for)i(arbitrary)f (metric)i(spaces.)-25 262 y Fn(Pr)o(oof:)21 b Fs(Consider)12 b(a)i(metric)g(space)h(consisting)d(of)i(the)f(points)-75 312 y Fm(p)-54 318 y Fi(ij)-25 312 y Fs(,)g Fk(1)j Fl(\024)g Fm(i;)7 b(j)19 b Fl(\024)e Fk(4)p Fs(,)12 b Fm(i)k Fl(6)p Fk(=)h Fm(j)r Fs(.)i(The)12 b(distances)g(between)g(the)g(points)-75 362 y(are)d(the)f(shortest)f(path)h(distances)h(in)e(the)h(graph)g (with)f(the)h(following)-75 412 y(distances)j(speci\256ed:)j Fm(d)p Fk(\()p Fm(p)320 418 y Fi(ij)349 412 y Fm(;)7 b(p)389 418 y Fi(j)r(i)417 412 y Fk(\))12 b(=)h(1)p Fs(,)d(and)h Fm(d)p Fk(\()p Fm(p)661 418 y Fi(ij)687 422 y Fg(1)704 412 y Fm(;)c(p)744 418 y Fi(ij)770 422 y Fg(2)787 412 y Fk(\))12 b(=)860 377 y Fl(p)p 894 377 V 894 412 a Fk(2)p Fs(.)-75 462 y(Let)i Fm(B)25 468 y Fi(i)60 462 y Fk(=)22 b Fl(f)p Fm(p)156 468 y Fi(ij)206 462 y Fl(j)f Fk(1)g Fl(\024)g Fm(j)j Fl(\024)d Fk(4)p Fm(;)7 b(i)21 b Fl(6)p Fk(=)h Fm(j)r Fl(g)p Fs(.)h(Note)13 b(that)f(the)h(sets)-75 511 y Fm(B)-44 517 y Fi(i)-30 511 y Fs(,)j Fk(1)24 b Fl(\024)g Fm(i)h Fl(\024)f Fk(4)p Fs(,)16 b(partition)11 b(the)j(metric)h(space)g(into)e Fk(4)h Fs(clusters)-75 561 y(of)g(diameter)134 527 y Fl(p)p 169 527 V 34 x Fk(2)o Fs(.)27 b(Let)15 b Fm(A)g Fs(be)f(any)h(deterministic)e(algorithm)g (for)-75 611 y(the)h(incremental)f(clustering)g(problem.)24 b(Let)14 b Fm(k)24 b Fk(=)f(6)p Fs(.)i(Consider)-75 661 y(the)11 b(clusters)g(produced)f(by)h Fm(A)g Fs(after)g(it)f(is)h (given)f(the)h Fk(12)g Fs(points)e Fm(p)896 667 y Fi(ij)-75 711 y Fs(described)h(above.)-75 810 y Fn(Case)k(1:)19 b Fs(Suppose)13 b(the)h(maximum)g(diameter)f(of)g Fm(A)p Fs(')n(s)h(clusters)f(is)-75 860 y Fk(1)p Fs(.)18 b(Then)12 b Fm(A)p Fs(')n(s)g(clusters)g(must)f(be)h(the)g Fk(6)f Fs(sets)i Fl(f)p Fm(p)636 866 y Fi(ij)664 860 y Fm(;)7 b(p)704 866 y Fi(j)r(i)733 860 y Fl(g)p Fs(.)18 b(Now)12 b(the)-75 910 y(adversary)f(gives)f(a)h(point)d Fm(q)k Fs(such)e(that)g Fm(d)p Fk(\()p Fm(q)q(;)d(p)607 916 y Fi(ij)635 910 y Fk(\))12 b(=)g(10)e Fs(\(any)g(lar)o(ge)-75 960 y(number)h(will)f(do\))h(for)f Fk(1)15 b Fl(\024)f Fm(i;)7 b(j)17 b Fl(\024)e Fk(4)p Fs(.)i(The)12 b(optimal)e(clustering) g(is)-75 1009 y Fl(f)p Fm(q)q Fl(g)15 b Fs(and)g(the)g(sets)h Fm(B)252 1015 y Fj(1)271 1009 y Fm(;)7 b(B)321 1015 y Fj(2)339 1009 y Fm(;)g(B)389 1015 y Fj(3)408 1009 y Fm(;)g(B)458 1015 y Fj(4)476 1009 y Fs(.)29 b(The)16 b(optimal)e(diameter)i(is)-75 1025 y Fl(p)p -40 1025 V 34 x Fk(2)o Fs(.)25 b(W)m(e)14 b(claim)g(that)f(the)h(maximum)g(diameter)g(of)f Fm(A)h Fs(is)g(at)f(least)-75 1109 y Fk(2)5 b(+)-12 1075 y Fl(p)p 23 1075 V 34 x Fk(2)p Fs(.)13 b(If)c(the)f(cluster)h(that)f(contains)g Fm(q)i Fs(contains)e(any)h(other)f(point)-75 1159 y(then)g(our)g(claim) h(is)f(clearly)h(true.)k(If)8 b(on)g(the)h(other)e(hand,)j(the)e (cluster)-75 1209 y(that)17 b(contains)f Fm(q)j Fs(does)e(not)g (contain)f(any)i(other)e(point,)i Fm(A)g Fs(must)-75 1259 y(have)10 b(mer)o(ged)g(two)f(of)g(its)g(existing)e(clusters.)14 b(Then)c(the)f(maximum)-75 1308 y(diameter)k(of)g Fm(A)p Fs(')n(s)g(resulting)f(clusters)h(is)g(at)g(least)g Fk(2)g(+)754 1274 y Fl(p)p 789 1274 V 34 x Fk(2)p Fs(.)22 b(Thus)-75 1358 y(the)10 b(performance)h(ratio)f(of)g Fm(A)g Fs(is)g(at)h(least)f Fk(1)f(+)616 1324 y Fl(p)p 650 1324 V 650 1358 a Fk(2)p Fs(.)-75 1458 y Fn(Case)14 b(2:)19 b Fs(Suppose)13 b(the)h(maximum)g (diameter)f(of)g Fm(A)p Fs(')n(s)h(clusters)f(is)-75 1508 y(greater)j(than)f Fk(1)p Fs(.)31 b(Then)16 b(some)g(cluster)g(of) f Fm(A)h Fs(contains)f Fk(2)h Fs(points)-75 1557 y(which)9 b(are)h(at)g(least)g(distance)367 1523 y Fl(p)p 402 1523 V 34 x Fk(2)f Fs(apart.)14 b(Let)c(these)g(points)e(be)i Fm(p)880 1563 y Fi(w)q(x)-75 1607 y Fs(and)h Fm(p)17 1613 y Fi(y)q(z)54 1607 y Fs(,)h Fk(\()p Fm(w)q(;)7 b(x)p Fk(\))15 b Fl(6)p Fk(=)g(\()p Fm(z)r(;)7 b(y)q Fk(\))p Fs(.)19 b(Now)11 b(the)g(adversary)h(gives)f Fk(6)g Fs(points)-75 1657 y Fm(r)-56 1663 y Fi(ij)-27 1657 y Fs(,)h Fk(1)j Fl(\024)g Fm(i)g(<)g(j)j Fl(\024)d Fk(4)c Fs(such)h(that)e Fm(d)p Fk(\()p Fm(r)486 1663 y Fi(ij)515 1657 y Fm(;)d(p)555 1663 y Fi(ij)584 1657 y Fk(\))15 b(=)g Fm(d)p Fk(\()p Fm(r)719 1663 y Fi(ij)748 1657 y Fm(;)7 b(p)788 1663 y Fi(j)r(i)816 1657 y Fk(\))15 b(=)g(1)p Fs(.)-75 1707 y(The)f(optimal)f(clustering)f(consists)h(of)g(the)g Fk(6)h Fs(sets)g Fl(f)p Fm(r)729 1713 y Fi(ij)757 1707 y Fm(;)7 b(p)797 1713 y Fi(ij)826 1707 y Fm(;)g(p)866 1713 y Fi(j)r(i)894 1707 y Fl(g)p Fs(.)-75 1757 y(The)k(optimal)f (diameter)h(is)g Fk(1)p Fs(.)k(W)m(e)c(claim)g(that)f(the)h(maximum)g (dia-)-75 1806 y(meter)16 b(of)f Fm(A)p Fs(')n(s)g(clusters)g(must)g (be)h(at)f(least)g Fk(1)h(+)673 1772 y Fl(p)p 707 1772 V 707 1806 a Fk(2)p Fs(.)29 b(Note)15 b(that)-75 1856 y Fm(d)p Fk(\()p Fm(r)-18 1862 y Fi(i)-6 1866 y Fg(1)9 1862 y Fi(j)23 1866 y Fg(1)41 1856 y Fm(;)7 b(p)81 1862 y Fi(i)93 1866 y Fg(2)109 1862 y Fi(j)123 1866 y Fg(2)141 1856 y Fk(\))17 b Fl(\025)h Fk(1)11 b(+)300 1822 y Fl(p)p 335 1822 V 34 x Fk(2)g Fs(for)h Fk(\()p Fm(i)458 1862 y Fj(2)477 1856 y Fm(;)7 b(j)513 1862 y Fj(2)531 1856 y Fk(\))18 b Fl(6)p Fk(=)f(\()p Fm(i)644 1862 y Fj(1)663 1856 y Fm(;)7 b(j)699 1862 y Fj(1)717 1856 y Fk(\))p Fs(,)14 b Fk(\()p Fm(i)787 1862 y Fj(2)806 1856 y Fm(;)7 b(j)842 1862 y Fj(2)860 1856 y Fk(\))17 b Fl(6)p Fk(=)-75 1906 y(\()p Fm(j)-42 1912 y Fj(1)-23 1906 y Fm(;)7 b(i)10 1912 y Fj(1)28 1906 y Fk(\))p Fs(.)14 b(Also)8 b Fm(d)p Fk(\()p Fm(r)212 1912 y Fi(i)224 1916 y Fg(1)239 1912 y Fi(j)253 1916 y Fg(1)271 1906 y Fm(;)f(r)309 1912 y Fi(i)321 1916 y Fg(2)336 1912 y Fi(j)350 1916 y Fg(2)368 1906 y Fk(\))12 b Fl(\025)g Fk(2)t(+)501 1872 y Fl(p)p 535 1872 V 535 1906 a Fk(2)c Fs(for)g Fk(\()p Fm(i)651 1912 y Fj(1)670 1906 y Fm(;)f(j)706 1912 y Fj(1)724 1906 y Fk(\))12 b Fl(6)p Fk(=)g(\()p Fm(i)826 1912 y Fj(2)845 1906 y Fm(;)7 b(j)881 1912 y Fj(2)899 1906 y Fk(\))p Fs(.)-75 1956 y(If)i Fm(A)h Fs(puts)f(any)h(two)f Fm(r)243 1962 y Fi(ij)281 1956 y Fs(in)g(the)h(same)h(cluster)n(,)f(our)f(claim) h(is)g(clearly)-75 2006 y(true.)33 b(If)16 b(all)h(the)f Fm(r)222 2012 y Fi(ij)268 2006 y Fs(are)i(in)e(separate)h(clusters,)i (each)f(of)e(the)h Fk(6)-75 2056 y Fs(clusters)9 b(must)f(contain)g (one)h(of)f(them.)14 b(Also)8 b(one)h(of)f(the)h Fk(6)f Fs(clusters,)-75 2105 y(say)f Fm(C)j Fs(must)d(contain)f(both)g(the)h (points)e Fm(p)512 2111 y Fi(w)q(x)565 2105 y Fs(and)i Fm(p)653 2111 y Fi(y)q(z)690 2105 y Fs(.)13 b(Then)7 b Fm(C)j Fs(must)-75 2155 y(have)h(diameter)h(at)f(least)g Fk(1)f(+)372 2121 y Fl(p)p 407 2121 V 34 x Fk(2)p Fs(,)h(since)h(the)e Fm(r)626 2161 y Fi(ij)666 2155 y Fs(in)h Fm(C)i Fs(must)e(be)h(at)-75 2205 y(distance)e(at)f(least)h Fk(1)d(+)263 2171 y Fl(p)p 297 2171 V 297 2205 a Fk(2)j Fs(from)f(one)h(of)f Fm(p)553 2211 y Fi(w)q(x)608 2205 y Fs(and)g Fm(p)698 2211 y Fi(y)q(z)735 2205 y Fs(.)14 b(Hence)d(the)-75 2255 y(performance)g(ratio)f(of)g Fm(A)g Fs(is)g(at)g(least)h Fk(1)e(+)554 2220 y Fl(p)p 589 2220 V 35 x Fk(2)p Fs(.)p 896 2255 30 30 v -25 2305 a(Finally)m(,)20 b(we)g(can)g(improve)e(the)h(randomized)g(lower)g (bound)-75 2354 y(slightly)8 b(for)i(the)g(case)i(of)e(arbitrary)f (metric)h(spaces.)-75 2428 y Fn(Theor)o(em)h(16)20 b Fr(For)14 b(any)g Fm(\017)22 b(>)h Fk(0)13 b Fr(and)g Fm(k)23 b Fl(\025)g Fk(2)p Fr(,)15 b(ther)n(e)f(is)g(a)f(lower)-75 2477 y(bound)d(of)g Fk(2)g Fl(\000)h Fm(\017)g Fr(on)g(the)g (performance)g(ratio)f(of)g(any)h(randomized)-75 2527 y(incr)n(emental)f(algorithm.)-25 2600 y Fn(Pr)o(oof:)17 b Fs(W)m(e)12 b(use)g(Y)l(ao')n(s)f(technique)g(and)h(show)f(a)h(lower) g(bound)-75 2650 y(on)g(deterministic)f(algorithms)f(on)i(an)g (appropriately)f(chosen)h(dis-)-75 2700 y(tribution.)f(Let)f Fm(A)g Fs(be)f(a)h(deterministic)f(algorithm)f(for)h(incremental)1025 -33 y(clustering.)k(The)e(distributio)o(n)d(on)i(inputs)f(is)h(as)h (follows.)i(Initially)m(,)1025 16 y(the)g(adversary)h(provides)f Fm(n)g Fs(points)f Fm(P)1601 22 y Fj(1)1620 16 y Fm(;)7 b(P)1666 22 y Fj(2)1690 16 y Fm(:)g(:)g(:)f(P)1773 22 y Fi(n)1809 16 y Fs(such)13 b(that)g(the)1025 66 y(distance)f(between)g (any)h(two)e(of)h(them)g(is)g Fk(1)p Fs(.)20 b(Then)13 b(the)f(adversary)1025 116 y(partitions)i(the)i Fm(n)g Fs(points)f(into)g Fm(k)i Fs(disjoint)d(sets)j Fm(S)1789 122 y Fj(1)1808 116 y Fm(;)7 b(S)1852 122 y Fj(2)1877 116 y Fm(:)g(:)g(:)f(S)1958 122 y Fi(k)1995 116 y Fs(at)1025 166 y(random,)16 b(such)f(that)f(all)h(partitions)e(are)i(equally)f (likely)m(.)27 b(Finally)1025 216 y(the)17 b(adversary)g(provides)g Fm(k)h Fs(points)e Fm(Q)1624 222 y Fj(1)1643 216 y Fm(;)7 b(Q)1695 222 y Fj(2)1713 216 y Fm(;)g(:)g(:)g(:)t(Q)1819 222 y Fi(k)1840 216 y Fs(,)19 b(such)f(that)1025 265 y Fm(d)p Fk(\()p Fm(Q)1096 271 y Fi(i)1109 265 y Fm(;)7 b(P)1155 271 y Fi(j)1171 265 y Fk(\))26 b(=)f(1)14 b Fs(if)g Fm(P)1372 271 y Fi(j)1415 265 y Fl(2)24 b Fm(S)1492 271 y Fi(i)1507 265 y Fs(,)15 b Fm(d)p Fk(\()p Fm(Q)1603 271 y Fi(i)1617 265 y Fm(;)7 b(P)1663 271 y Fi(j)1679 265 y Fk(\))26 b(=)f(2)14 b Fs(if)g Fm(P)1880 271 y Fi(j)1923 265 y Fl(62)24 b Fm(S)2000 271 y Fi(i)2015 265 y Fs(,)1025 315 y Fm(d)p Fk(\()p Fm(Q)1096 321 y Fi(i)1109 315 y Fm(;)7 b(Q)1161 321 y Fi(j)1178 315 y Fk(\))19 b(=)h(3)p Fs(.)h(Now)m(,)14 b(the)f(diameter)g(of)f(the)h(optimal)e(solution)1025 365 y(for)g(any)h(input)f(in)h(the)g(distributi)o(on)d(is)j Fk(1)p Fs(,)h(obtained)e(by)h(construct-)1025 415 y(ing)f(the)h Fm(k)h Fs(clusters)f Fm(S)1352 421 y Fi(i)1378 415 y Fl([)g(f)p Fm(Q)1472 421 y Fi(i)1485 415 y Fl(g)p Fs(.)20 b(However)n(,)14 b(the)e(incremental)g(al-)1025 465 y(gorithm)d(can)i (produce)f(a)h(clustering)e(with)h(diameter)h Fk(1)f Fs(only)f(if)h(the)1025 514 y(clusters)g(it)f(produces)h(after)h(it)e (sees)i(points)e Fm(P)1693 520 y Fj(1)1712 514 y Fm(;)e(P)1758 520 y Fj(2)1782 514 y Fm(:)g(:)g(:)f(P)1865 520 y Fi(n)1897 514 y Fs(are)11 b(pre-)1025 564 y(cisely)f(the)h(sets)g Fm(S)1292 570 y Fi(i)1317 564 y Fs(\(selected)h(at)f(random)f(by)h(the) g(adversary\).)16 b(Let)1025 614 y Fm(X)1059 620 y Fi(k)1079 614 y Fk(\()p Fm(n)p Fk(\))d Fs(be)g(the)f(number)g(of)g(ways)h(to)f (partition)e(the)i Fm(n)g Fs(points)f(into)1025 664 y Fm(k)j Fs(sets.)23 b(Then)14 b(the)f(probability)e(that)h(the)h (incremental)h(algorithm)1025 714 y(produces)9 b(a)i(clustering)d(of)i (diameter)g Fk(1)g Fs(is)f(at)h(most)g Fm(p)h Fk(=)h(1)p Fm(=X)1937 720 y Fi(k)1957 714 y Fk(\()p Fm(n)p Fk(\))p Fs(.)1025 764 y(W)n(ith)7 b(probability)e(at)j(least)g Fk(1)s Fl(\000)s Fm(p)p Fs(,)g(the)g(incremental)f(algorithm)g(pro-) 1025 813 y(duces)12 b(a)g(clustering)f(of)g(diameter)i(at)e(least)h Fk(2)p Fs(.)19 b(Thus)12 b(the)f(expected)1025 863 y(value)j(of)g(the)g (diameter)g(of)g(the)g(clustering)f(produced)h(is)g(at)g(least)1025 913 y Fk(2)s Fl(\000)s Fm(p)p Fs(.)g(Hence)9 b(the)f(expected)g(value)g (of)g(the)g(performance)h(ratio)e(is)h(at)1025 963 y(least)h Fk(2)e Fl(\000)h Fm(p)p Fs(.)14 b(By)9 b(chosing)f Fm(n)i Fs(suitably)e(lar)o(ge,)i Fm(X)1731 969 y Fi(k)1752 963 y Fk(\()p Fm(n)p Fk(\))g Fs(can)g(be)g(made)1025 1013 y(arbitrarily)g(lar)o(ge,)j(and)f(hence)i Fm(p)e Fs(can)h(be)f(made)h (arbitrarily)e(small,)1025 1062 y(in)e(particular)h(smaller)g(than)g Fm(\017)g Fs(for)g(any)g(\256xed)h Fm(\017)g(>)h Fk(0)p Fs(.)p 1996 1062 V 1025 1171 a Ft(6)49 b(Dual)12 b(Clustering)1074 1271 y Fs(W)m(e)j(now)e(consider)h(the)g(dual)f(clustering)g(problem:) 20 b(for)13 b(a)i(se-)1025 1321 y(quence)7 b(of)g(points)e Fm(p)1320 1327 y Fj(1)1339 1321 y Fm(;)i(p)1379 1327 y Fj(2)1397 1321 y Fm(;)g(:)g(:)g(:)e(;)i(p)1511 1327 y Fi(n)1544 1321 y Fl(2)k(<)1613 1305 y Fi(d)1633 1321 y Fs(,)d(cover)f(each)h(point)e(with)g(a)1025 1370 y(unit)g(ball)h(in)f Fl(<)1236 1355 y Fi(d)1263 1370 y Fs(as)i(it)f(arrives,)i(so)e(as)h(to) f(minimize)g(the)h(total)e(number)1025 1420 y(of)j(balls)h(used.)k(In)c (the)f(static)h(case)i(this)d(problem)g(is)h Fr(NP-Complete)1025 1470 y Fs(and)i(there)g(is)g(a)h(PT)m(AS)g(for)e(any)i(\256xed)f (dimension)f([22].)20 b(W)m(e)13 b(note)1025 1520 y(that)8 b(in)g(general)h(metric)h(spaces,)h(it)d(is)h(not)f(possible)g(to)g (achieve)i(any)1025 1570 y(bounded)f(ratio.)1074 1620 y(Our)g(algorithm')n(s)e(analysis)h(is)h(based)g(on)f(a)h(theorem)g (from)g(com-)1025 1669 y(binatorial)14 b(geometry)j(called)f(Roger)r(') n(s)f(theorem)i([36)o(])g(\(see)g(also)1025 1719 y(Theorem)c(7.17)g ([33)o(]\),)g(which)g(says)g(that)f Fm(R)1685 1704 y Fi(d)1717 1719 y Fs(can)h(be)g(covered)g(by)1025 1769 y(any)g(convex)h(shape)h(with)e(covering)g(density)g Fm(O)q Fk(\()p Fm(d)7 b Fk(log)f Fm(d)p Fk(\))p Fs(.)25 b(Since)1025 1819 y(the)8 b(volume)g(of)h(a)g(radius)f Fk(2)h Fs(ball)f(is)g Fk(2)1556 1804 y Fi(d)1584 1819 y Fs(times)h(the)g(volume)f(of)g(a)i(unit-)1025 1869 y(radius)g(ball,)h(the)g(number)f(of)h(balls)f(needed)i(to)e(cover)i(a) f(ball)f(of)h(ra-)1025 1918 y(dius)e Fk(2)h Fs(using)g(balls)g(of)g (unit)f(radius)h(is)g Fm(f)t Fk(\()p Fm(d)p Fk(\))j(=)f Fm(O)q Fk(\(2)1800 1903 y Fi(d)1819 1918 y Fm(d)7 b Fk(log)f Fm(d)p Fk(\))p Fs(.)15 b(W)m(e)1025 1968 y(\256rst)e(describe)h(an)g (incremental)g(algorithm)e(which)h(has)h(perform-)1025 2018 y(ance)8 b(ratio)f Fm(f)t Fk(\()p Fm(d)p Fk(\))p Fs(.)14 b(W)m(e)7 b(also)h(establish)f(an)g(asymptotic)g(lower)g(bound) 1025 2068 y(of)12 b Fk(\012\()1172 2049 y Fj(log)6 b Fi(d)p 1124 2058 164 2 v 1124 2082 a Fj(log)f(log)h(log)f Fi(d)1292 2068 y Fk(\))p Fs(;)14 b(for)f Fm(d)21 b Fk(=)h(1)13 b Fs(and)h Fk(2)p Fs(,)g(our)f(proof)f(yields)g(lower)1025 2118 y(bounds)d(of)h Fk(2)g Fs(and)g Fk(4)p Fs(,)h(respectively)m(.) 1025 2210 y Fn(Theor)o(em)g(17)20 b Fr(For)31 b(the)g(dual)e (clustering)h(pr)n(oblem)h(in)f Fl(<)1995 2195 y Fi(d)2015 2210 y Fr(,)1025 2259 y(ther)n(e)18 b(is)f(an)g(incr)n(emental)g (algorithm)f(with)g(performance)h(ratio)1025 2309 y Fm(O)q Fk(\(2)1095 2294 y Fi(d)1114 2309 y Fm(d)7 b Fk(log)f Fm(d)p Fk(\))p Fr(.)1074 2401 y Fn(Pr)o(oof:)16 b Fs(Our)11 b(algorithm)f(maintains)h(a)g(set)h Fl(C)h Fs(of)e Fr(centers)i Fs(which)1025 2451 y(is)8 b(a)h(subset)g(of)f(the)h(points)e(that)h (have)h(arrived)f(so)h(far;)g(initially)m(,)e Fl(C)14 b Fk(=)1025 2501 y Fl(;)p Fs(.)23 b(De\256ne)14 b(the)f Fr(range)h Fm(R)p Fk(\()p Fm(p)p Fk(\))f Fs(of)g(a)h(center)g Fm(p)g Fs(to)f(be)g(the)h(sphere)f(of)1025 2551 y(radius)e Fk(2)h Fs(about)f Fm(p)p Fs(.)19 b(For)12 b(any)g(two)f(centers)h Fm(p)1691 2557 y Fj(1)1722 2551 y Fs(and)g Fm(p)1815 2557 y Fj(2)1833 2551 y Fs(,)h(we)g(ensure)1025 2600 y(that)d Fm(d)p Fk(\()p Fm(p)1157 2606 y Fj(1)1175 2600 y Fm(;)d(p)1215 2606 y Fj(2)1233 2600 y Fk(\))14 b Fm(>)g Fk(2)p Fs(.)i(Associated)11 b(with)f(each)i(center)f Fm(p)g Fs(is)g(a)g(set)g(of)1025 2650 y(points)f Fk(\000\()p Fm(p)p Fk(\))i Fs(called)g(the)g Fr(neighbors)f Fs(of)g Fm(p)p Fs(.)19 b(For)11 b(convenience,)j(we)1025 2700 y(assume)e(that)f Fm(p)k Fl(2)g Fk(\000\()p Fm(p)p Fk(\))p Fs(.)j(W)m(e)11 b(ensure)h(that)f(all)g(neighbors)f(of)h Fm(p)g Fs(lie)p eop %%Page: 9 9 9 8 bop -75 -33 a Fs(in)12 b Fm(R)p Fk(\()p Fm(p)p Fk(\))p Fs(.)21 b(When)13 b(a)g(new)g(point)f Fm(x)g Fs(is)g(received,)j(if)d Fm(x)19 b Fl(2)g Fm(R)p Fk(\()p Fm(p)p Fk(\))13 b Fs(for)-75 16 y(some)e(center)g Fm(p)p Fs(,)h(we)f(add)f Fm(x)h Fs(to)f Fk(\000\()p Fm(p)p Fk(\))p Fs(,)h(breaking)f(ties)g (arbitrarily)m(.)k(If)-75 66 y(no)d(such)h(center)g(exists,)g Fm(x)g Fs(must)f(be)h(at)g(a)g(distance)g(greater)g(than)f Fk(2)-75 116 y Fs(from)g(all)g(the)g(existing)f(centers.)18 b(In)11 b(this)f(case,)j(we)f(make)g Fm(x)g Fs(a)f(new)-75 166 y(center)g(and)f(set)h Fk(\000\()p Fm(x)p Fk(\))g(=)h Fl(f)p Fm(x)p Fl(g)p Fs(.)-25 218 y(From)17 b(Roger)r(')n(s)f(theorem)i (on)f(packing)g(density)f(a)i(sphere)g(of)-75 268 y(radius)e Fk(2)h Fs(in)f Fl(<)160 253 y Fi(d)196 268 y Fs(can)h(be)g(covered)g (by)g Fm(f)t Fk(\()p Fm(d)p Fk(\))33 b(=)h Fm(O)q Fk(\(2)780 253 y Fi(d)799 268 y Fm(d)7 b Fk(log)f Fm(d)p Fk(\))-75 318 y Fs(spheres)17 b(of)e(radius)h Fk(1)p Fs(.)31 b(When)16 b(a)h(new)f(center)h Fm(p)f Fs(is)f(created,)k(we)-75 368 y(\256x)13 b(a)g(set)g(of)g(spheres)g Fm(S)282 374 y Fj(1)301 368 y Fk(\()p Fm(p)p Fk(\))p Fm(;)7 b(S)398 374 y Fj(2)417 368 y Fk(\()p Fm(p)p Fk(\))p Fm(;)g(:)g(:)g(:)e(;)i(S) 588 375 y Fi(f)s Fj(\()p Fi(d)p Fj(\))653 368 y Fk(\()p Fm(p)p Fk(\))13 b Fs(which)f(cover)-75 417 y Fm(R)p Fk(\()p Fm(p)p Fk(\))p Fs(.)h(Whenever)c(a)f(point)e Fm(x)i Fs(is)f(added)h(to) f Fk(\000\()p Fm(p)p Fk(\))p Fs(,)i(if)e(it)g(is)g(not)g(already)-75 467 y(covered)h(by)f(some)i(previously)d(placed)i(sphere,)h(we)f(add)g (the)f(sphere)-75 517 y Fm(S)-50 523 y Fi(r)-31 517 y Fk(\()p Fm(p)p Fk(\))16 b Fs(where)h Fm(r)h Fs(is)e(any)g(value)g(such) h(that)f Fm(x)31 b Fl(2)g Fm(S)730 523 y Fi(r)749 517 y Fk(\()p Fm(p)p Fk(\))p Fs(.)i(Note)-75 567 y(that)12 b(such)h(a)h(sphere)f(must)g(exist)f(as)i Fm(x)20 b Fl(2)f Fm(R)p Fk(\()p Fm(p)p Fk(\))13 b Fs(and)g(the)g(spheres)-75 617 y Fm(S)-50 623 y Fj(1)-31 617 y Fk(\()p Fm(p)p Fk(\))p Fm(;)7 b(S)66 623 y Fj(2)85 617 y Fk(\()p Fm(p)p Fk(\))p Fm(;)g(:)g(:)g(:)e(;)i(S)256 624 y Fi(f)s Fj(\()p Fi(d)p Fj(\))320 617 y Fk(\()p Fm(p)p Fk(\))k Fs(cover)g Fm(R)p Fk(\()p Fm(p)p Fk(\))f Fs(completely)m(.)-25 669 y(Since)j(no)f(two)g (centers)i(can)f(be)g(covered)h(by)e(a)h(sphere)g(of)g(unit)-75 719 y(radius,)d(any)f(solution)e(must)j(use)f(a)h(separate)h(sphere)f (to)f(cover)g(each)-75 769 y(center)n(.)25 b(Hence,)17 b(the)c(number)h(of)g(centers)h(is)e(a)i(lower)e(bound)g(for)-75 819 y(the)d(number)f(of)h(spheres)g(used)g(by)g(the)f(optimal)g(of)o (\257ine)h(algorithm.)-75 868 y(For)15 b(each)i(center)g Fm(p)p Fs(,)g(the)f(incremental)f(algorithm)g(uses)h(at)g(most)-75 918 y Fm(f)t Fk(\()p Fm(d)p Fk(\))g Fs(spheres)f(to)g(cover)g(the)g (points)f(in)g Fk(\000\()p Fm(p)p Fk(\))p Fs(.)29 b(Hence,)18 b(the)c(per)o(-)-75 968 y(formance)h(ratio)e(of)h(the)g(incremental)g (algorithm)e(is)i(bounded)f(by)-75 1018 y Fm(f)t Fk(\()p Fm(d)p Fk(\))f(=)g Fm(O)q Fk(\(2)129 1003 y Fi(d)148 1018 y Fm(d)7 b Fk(log)f Fm(d)p Fk(\))p Fs(.)p 896 1018 30 30 v -25 1070 a(The)13 b(following)d(theorem)j(gives)f(a)h(lower)f (bound)g(for)g(the)g(dual)-75 1120 y(clustering)d(problem.)-75 1224 y Fn(Theor)o(em)i(18)20 b Fr(For)31 b(the)g(dual)f(clustering)g (pr)n(oblem)h(in)f Fl(<)896 1209 y Fi(d)915 1224 y Fr(,)-75 1274 y(any)22 b(incr)n(emental)f(algorithm)f(must)h(have)h(performance) g(ratio)-75 1324 y Fk(\012\()25 1306 y Fj(log)5 b Fi(d)p -24 1314 164 2 v -24 1338 a Fj(log)h(log)f(log)h Fi(d)144 1324 y Fk(\))p Fr(.)-25 1426 y Fn(Pr)o(oof:)19 b Fs(The)14 b(idea)f(is)g(as)h(follows.)21 b(At)13 b(time)g Fm(t)p Fs(,)h(when)f Fm(t)g Fs(points)-75 1476 y(have)e(been)g(given)f(by)g (the)h(adversary)m(,)g(it)f(will)f(be)i(the)g(case)h(that)e(the)-75 1525 y(points)f Fm(p)58 1531 y Fj(1)77 1525 y Fm(;)e(:)g(:)g(:)e(;)i(p) 191 1531 y Fi(t)216 1525 y Fs(can)k(be)g(covered)g(by)g(a)g(ball)f(of)h (radius)f Fm(R)821 1531 y Fi(t)849 1525 y Fm(<)j Fk(1)p Fs(.)-75 1575 y(Then,)e(the)f(adversary)g(will)f(\256nd)h(a)g(point)f Fm(p)558 1581 y Fi(t)p Fj(+1)624 1575 y Fs(lying)g(outside)g(the)h Fm(t)-75 1625 y Fs(unit)h(balls)h(laid)g(down)g(by)g(the)g(algorithm)f (so)h(as)i(to)d(minimize)i(the)-75 1675 y(radius)d Fm(R)69 1681 y Fi(t)p Fj(+1)135 1675 y Fs(of)g(the)g(ball)f(required)h(to)f (cover)i(all)e Fm(t)g Fk(+)g(1)h Fs(points)f(and)-75 1725 y(present)h(that)e(as)j(a)f(request.)j(The)e(game)f(terminates)g (when)f(at)h(some)-75 1774 y(time)f Fm(k)d Fk(+)f(1)p Fs(,)k(we)h(have)f(for)f(the)h(\256rst)f(time)h(that)f Fm(R)634 1780 y Fi(k)q Fj(+1)707 1774 y Fm(>)k Fk(1)p Fs(.)i(Clearly)m(,)-75 1824 y Fm(k)e Fs(is)e(a)h(lower)f(bound)g(on)g (the)g(performance)i(ratio)e(since)h(the)f(points)-75 1874 y Fm(p)-54 1880 y Fj(1)-35 1874 y Fm(;)d(:)g(:)g(:)t(;)g(p)78 1880 y Fi(k)111 1874 y Fs(can)13 b(be)g(covered)g(by)f(a)h(ball)f(of)g (radius)h Fm(R)731 1880 y Fi(k)770 1874 y Fl(\024)19 b Fk(1)p Fs(,)14 b(and)-75 1924 y(the)d(algorithm)e(has)i(used)g Fm(k)h Fs(balls)e(up)g(to)h(that)f(point.)k(It)c(remains)h(to)-75 1974 y(analyze)i(the)f(worst-case)g(growth)f(rate)i(of)e Fm(R)599 1980 y Fi(t)626 1974 y Fs(as)h(a)h(function)d(of)i Fm(t)p Fs(.)-75 2024 y(Note)e(that)g Fm(R)121 2030 y Fj(1)150 2024 y Fk(=)i(0)e Fs(and)h Fm(R)328 2030 y Fj(2)357 2024 y Fk(=)h(1)p Fm(=)p Fk(2)p Fs(.)-25 2076 y(Let)i Fm(\013)71 2082 y Fi(d)104 2076 y Fs(denote)f(the)h(volume)f(of)h(a)g (unit)e(ball)h(in)g Fl(<)742 2061 y Fi(d)762 2076 y Fs(.)24 b(At)14 b(time)-75 2126 y Fm(t)p Fs(,)h(let)f Fm(D)55 2132 y Fi(t)83 2126 y Fs(be)g(any)g(ball)f(of)h(radius)f(\(at)h(most\)) f Fm(R)648 2132 y Fi(t)676 2126 y Fs(that)h(covers)g(the)-75 2176 y(points)7 b Fm(p)56 2182 y Fj(1)74 2176 y Fm(;)g(:)g(:)g(:)e(;)i (p)188 2182 y Fi(t)202 2176 y Fs(.)14 b(For)8 b(some)h Fm(\016)406 2182 y Fi(t)429 2176 y Fs(to)f(be)h(speci\256ed)g(later)n (,)g(de\256ne)g(the)-75 2225 y(ball)h Fm(D)33 2210 y Fe(\003)32 2236 y Fi(t)63 2225 y Fs(as)h(a)g(ball)f(with)g(the)g(same)i (center)f(as)g Fm(D)643 2231 y Fi(t)669 2225 y Fs(and)g(with)e(radius) -75 2275 y Fm(R)-43 2281 y Fi(t)-19 2275 y Fk(+)h Fm(\016)41 2281 y Fi(t)56 2275 y Fs(.)15 b(W)m(e)c(will)e(choose)i Fm(\016)365 2281 y Fi(t)391 2275 y Fs(such)f(that)g(the)h(volume)f(of)g Fm(D)827 2260 y Fe(\003)826 2285 y Fi(t)857 2275 y Fs(is)h(at)-75 2325 y(least)f Fm(t\013)53 2331 y Fi(d)72 2325 y Fs(,)h(implying)d (that)i(the)g(current)g Fm(t)g Fs(unit)f(balls)h(placed)h(by)f(the)-75 2375 y(algorithm)e(cannot)h(cover)h(the)f(entire)g(volume)g(of)g Fm(D)695 2360 y Fe(\003)694 2385 y Fi(t)715 2375 y Fs(.)k(This)d(would) -75 2425 y(imply)g(that)g(there)h(is)g(a)h(choice)f(of)g(a)g(point)f Fm(p)581 2431 y Fi(t)p Fj(+1)648 2425 y Fs(inside)g Fm(D)793 2410 y Fe(\003)792 2435 y Fi(t)824 2425 y Fs(which)-75 2474 y(is)i(not)f(covered)h(by)f(the)h(current)f Fm(t)h Fs(balls.)18 b(It)12 b(is)f(also)h(clear)h(that)e(the)-75 2524 y(new)e(set)g(of)f Fm(t)d Fk(+)g(1)j Fs(points)g(now)g(can)h(be)g (covered)g(by)g(a)g(ball)f(of)g(radius)-75 2574 y(at)i(most)g Fm(R)88 2580 y Fi(t)112 2574 y Fk(+)f Fm(\016)171 2580 y Fi(t)186 2574 y Fm(=)p Fk(2)p Fs(.)14 b(implying)8 b(that)278 2692 y Fm(R)310 2698 y Fi(t)p Fj(+1)377 2692 y Fk(=)k Fm(R)453 2698 y Fi(t)477 2692 y Fk(+)523 2664 y Fm(\016)541 2670 y Fi(t)p 523 2683 34 2 v 529 2721 a Fk(2)561 2692 y Fm(:)1025 -33 y Fs(T)m(o)h(determine)h(the)f(value)h (of)f Fm(\016)1495 -27 y Fi(t)1524 -33 y Fs(is)g(easy)m(,)j(since)e(we) g(have)g(the)g(in-)1025 16 y(equality)9 b(that)1353 66 y Fm(\013)1380 72 y Fi(d)1399 66 y Fk(\()p Fm(R)1447 72 y Fi(t)1470 66 y Fk(+)h Fm(\016)1530 72 y Fi(t)1545 66 y Fk(\))1561 49 y Fi(d)1592 66 y Fm(>)i(t\013)1678 72 y Fi(d)1025 140 y Fs(from)f(the)h(requirement)f(that)g(the)h(ball)f Fm(D)1637 146 y Fi(t)1664 140 y Fs(have)h(volume)g(equal)g(to)1025 190 y(that)d(of)h Fm(t)h Fs(unit)e(balls.)14 b(Now)c(let)h Fm(R)1522 196 y Fi(t)1548 190 y Fk(=)h(1)d Fl(\000)h Fm(\017)1681 196 y Fi(t)1695 190 y Fs(.)15 b(Substituting)7 b(in)j(the)1025 239 y(above)g(equations)f(we)i(obtain)e(that:)1383 329 y Fm(\016)1401 335 y Fi(t)1614 329 y Fk(=)j(2\()p Fm(\017)1712 335 y Fi(t)1735 329 y Fl(\000)e Fm(\017)1794 335 y Fi(t)p Fj(+1)1850 329 y Fk(\))1144 391 y Fl(\))149 b Fm(R)1367 397 y Fi(t)1390 391 y Fk(+)10 b Fm(\016)1450 397 y Fi(t)1614 391 y Fk(=)i(1)d(+)g Fm(\017)1746 397 y Fi(t)1770 391 y Fl(\000)g Fk(2)p Fm(\017)1849 397 y Fi(t)p Fj(+1)1144 453 y Fl(\))41 b Fm(\013)1254 459 y Fi(d)1273 453 y Fk(\(1)9 b(+)g Fm(\017)1377 459 y Fi(t)1401 453 y Fl(\000)h Fk(2)p Fm(\017)1481 459 y Fi(t)p Fj(+1)1537 453 y Fk(\))1553 438 y Fi(d)1614 453 y Fm(>)i(t\013)1700 459 y Fi(d)1144 537 y Fl(\))56 b Fk(ln\(1)9 b(+)g Fm(\017)1381 543 y Fi(t)1405 537 y Fl(\000)h Fk(2)p Fm(\017)1485 543 y Fi(t)p Fj(+1)1541 537 y Fk(\))57 b Fm(>)1663 509 y Fk(ln)6 b Fm(t)p 1663 528 57 2 v 1680 566 a(d)1025 640 y Fs(Note)h(that)h Fm(\017)1201 646 y Fi(t)1218 640 y Fl(\000)s Fk(2)p Fm(\017)1291 646 y Fi(t)p Fj(+1)1360 640 y Fm(<)j Fk(1)p Fs(.)j(Using)7 b(the)h(fact)g(that)f Fk(ln\(1)s(+)s Fm(x)p Fk(\))12 b Fm(>)g(x=)p Fk(2)1025 690 y Fs(for)d Fm(x)j(<)f Fk(1)p Fs(,)g(we)g(see)g(that)f(choosing)f Fm(\017)1576 696 y Fi(i)1600 690 y Fs(such)h(that)1376 772 y Fm(\017)1393 778 y Fi(t)1416 772 y Fl(\000)g Fk(2)p Fm(\017)1496 778 y Fi(t)p Fj(+1)p 1376 790 177 2 v 1453 828 a Fk(2)1569 800 y(=)1617 772 y(ln)d Fm(t)p 1617 790 57 2 v 1635 828 a(d)1025 900 y Fs(will)h(satisfy)i(our)g(requirements.) k(Unfolding)8 b(the)i(recurrence,)1030 999 y Fm(\017)1047 1005 y Fj(1)p 1030 1017 36 2 v 1030 1055 a Fk(2)1051 1043 y Fi(t)1080 1027 y Fl(\000)f Fm(\017)1138 1033 y Fi(t)p Fj(+1)1206 1027 y Fk(=)1274 975 y Fi(t)1250 987 y Fh(X)1253 1076 y Fi(i)p Fj(=1)1341 999 y Fk(ln)e Fm(i)p 1322 1017 95 2 v 1322 1055 a(d)p Fk(2)1365 1043 y Fi(t)p Fe(\000)p Fi(i)1433 1027 y Fk(=)1500 975 y Fi(t)1477 987 y Fh(X)1480 1076 y Fi(i)p Fj(=1)1568 999 y Fk(ln)g Fm(i)p 1549 1017 V 1549 1055 a(d)p Fk(2)1592 1043 y Fi(t)p Fe(\000)p Fi(i)1660 1027 y Fl(\024)1727 975 y Fi(t)1704 987 y Fh(X)1707 1076 y Fi(i)p Fj(=1)1795 999 y Fk(ln)f Fm(t)p 1775 1017 V 1775 1055 a(d)p Fk(2)1818 1043 y Fi(t)p Fe(\000)p Fi(i)1887 1027 y Fl(\024)1935 999 y Fk(2)h(ln)g Fm(t)p 1935 1017 85 2 v 1967 1055 a(d)1025 1158 y Fs(Noting)i(that)i Fm(\017)1242 1164 y Fj(1)1275 1158 y Fk(=)k(1)p Fs(,)d(we)f(obtain)g (that)f Fm(\017)1630 1164 y Fi(t)p Fj(+1)1701 1158 y Fl(\025)15 b Fk(2)1769 1143 y Fe(\000)p Fi(t)1820 1158 y Fl(\000)c Fk(2)p Fm(d)1906 1143 y Fe(\000)p Fj(1)1957 1158 y Fk(ln)6 b Fm(t:)1025 1207 y Fs(The)11 b(lower)g(bound)f(is)g (the)h(smallest)g(value)g(of)g Fm(t)g Fs(for)f(which)h Fm(\017)1930 1213 y Fi(t)p Fj(+1)1997 1207 y Fs(is)1025 1257 y(negative.)i(Let)e Fm(t)1270 1263 y Fi(max)1349 1257 y Fs(be)f(the)g(lar)o(gest)h(value)f(of)g Fm(t)g Fs(for)g(which)1257 1339 y Fk(1)p 1250 1357 36 2 v 1250 1395 a(2)1271 1383 y Fi(t)1299 1367 y Fl(\000)1346 1339 y Fk(2)d(ln)f Fm(t)p 1346 1357 85 2 v 1377 1395 a(d)1446 1367 y Fl(\025)12 b Fk(0)f Fl(\))h Fk(2)1597 1350 y Fi(t)p Fj(+1)1660 1367 y Fk(ln)6 b Fm(t)12 b Fl(\024)g Fm(d:)1264 1499 y Fl(\))f Fm(t)1332 1505 y Fi(max)1412 1499 y Fk(=)h(\012)1493 1441 y Fh(\022)1589 1471 y Fk(log)6 b Fm(d)p 1528 1490 204 2 v 1528 1528 a Fk(log)h(log)f(log)h Fm(d)1736 1441 y Fh(\023)1774 1499 y Fm(:)1025 1595 y Fs(This)j(gives)g(the)g(desired) g(lower)g(bound.)p 1996 1645 30 30 v 1025 1752 a Ft(Acknowledgements) 1074 1851 y Fs(W)m(e)h(thank)f(Pankaj)h(Agarwal)f(and)h(Leonidas)f (Guibas)h(for)f(help-)1025 1900 y(ful)f(discussions,)h(and)h(for)f (suggesting)f(that)h(we)h(consider)f(the)h(dual)1025 1950 y(clustering)e(problem.)1025 2057 y Ft(Refer)o(ences)1050 2152 y Fc([1])21 b(M.S.)c(Aldenderfer)e(and)g(R.K.)i(Blash\256eld.)45 b Fb(Cluster)15 b(Analysis.)1114 2198 y Fc(Sage,)9 b(Beverly)f(Hills,)j (1984.)1050 2243 y([2])21 b(M.)15 b(Bern)f(and)f(D.)i(Eppstein.)36 b(Approximation)14 b(Algorithms)g(for)1114 2289 y(Geometric)f (Problems.)31 b(In:)20 b(D.S.)14 b(Hochbaum,)e(editor)o(,)i Fb(Appr)o(ox-)1114 2335 y(imation)d(Algorithms)e(for)h(NP-Har)o(d)f(Pr) o(oblems)p Fc(.)f(PWS)i(Publishing)1114 2380 y(Company)n(,)e(1996.)1050 2426 y([3])21 b(P)l(.)e(Brucker)n(.)59 b(On)18 b(the)g(complexity)g(of) h(clustering)f(problems.)1114 2472 y(In:)h(R.)13 b(Henn,)f(B.)h(Korte,) g(and)f(W)m(.)g(Oletti,)j(editors,)e Fb(Optimization)1114 2517 y(and)c(Operations)f(Resear)o(ch,)f Fc(Heidelber)o(g,)j(New)f(Y)l (ork,)i(NY)-5 b(,)10 b(1977,)1114 2563 y(pp.)f(45\26154.)1050 2609 y([4])21 b(F)m(.)8 b(Can.)i(Incremental)d(Clustering)h(for)g (Dynamic)f(Information)h(Pro-)1114 2654 y(cessing.)20 b Fb(ACM)11 b(T)n(ransactions)d(on)j(Information)f(Pr)o(ocessing)e (Sys-)1114 2700 y(tems)p Fc(,)i(1)o(1)e(\(1993\),)h(pp.)g(143\261164.)p eop %%Page: 10 10 10 9 bop -49 -33 a Fc([5])21 b(F)m(.)8 b(Can)f(and)f(E.A.)j(Ozkarahan.) f(A)g(Dynamic)f(Cluster)h(Maintenance)15 12 y(System)e(for)i (Information)f(Retrieval.)j(In)d Fb(Pr)o(oceedings)t(of)g(the)g(T)m (enth)15 58 y(Annual)f(International)h(ACM)h(SIGIR)g(Confer)o(ence)o(,) e Fc(1987,)h(pp.)g(123-)15 103 y(131.)-49 154 y([6])21 b(F)m(.)10 b(Can)f(and)g(N.D.)i(Drochak)e(II.)18 b(Incremental)10 b(Clustering)g(for)g(Dy-)15 200 y(namic)d(Document)f(Databases.)i(In)f Fb(Pr)o(oceedings)t(of)h(the)f(1990)f(Sym-)15 245 y(posium)i(on)h (Applied)f(Computing,)h Fc(1990,)g(pp.)g(61\26167.)-49 296 y([7])21 b(S.)8 b(Chakrabarti,)f(C.)h(Phillips,)g(A.)g(Schulz,)f (D.B.)h(Shmoys,)f(C.)g(Stein,)15 341 y(and)j(J.)i(W)m(ein.)25 b(Improved)10 b(Scheduling)g(Algorithms)i(for)g(Minsum)15 387 y(Criteria.)f(In)c Fb(Pr)o(oceedings)t(of)g(the)g(23r)o(d)f (International)g(Colloquium)15 433 y(on)j(Automata,)g(Languages)d(and)i (Pr)o(ogramming)p Fc(,)f(Springer)o(,)i(1996.)-49 483 y([8])21 b(B.B.)7 b(Chaudhri.)i(Dynamic)d(clustering)g(for)i(time)g (incremental)e(data.)15 529 y Fb(Pattern)i(Recognition)g(Letters)p Fc(,)h(13)f(\(1994\),)i(pp.)f(27-34.)-49 579 y([9])21 b(D.R.)14 b(Cutting,)h(D.R.)f(Kar)o(ger)o(,)g(J.O.)g(Pederson,)f(and)f (J.W)m(.)h(T)o(ukey)n(.)15 625 y(Scatter/Gather:)e(A)c(Cluster)o (-based)e(Approach)g(to)i(Browsing)f(Lar)o(ge)15 670 y(Document)g(Collections.)11 b(In)d Fb(Pr)o(oceedings)t(of)g(the)g (15th)f(Annual)g(In-)15 716 y(ternational)h(ACM)i(SIGIR)f(Confer)o (ence)p Fc(,)e(1992,)h(pp.)h(318\261329.)-68 766 y([10])21 b(D.R.)16 b(Cutting,)i(D.R.)f(Kar)o(ger)o(,)g(and)e(J.O.)h(Pederson.)44 b(Constant)15 812 y(interaction-time)9 b(Scatter/Gather)e(Browsing)h (of)g(V)l(ery)f(Lar)o(ge)h(Doc-)15 858 y(ument)h(Collections.)17 b(In)10 b Fb(Pr)o(oceedings)d(of)j(the)g(16th)f(Annual)g(Inter)o(-)15 903 y(national)g(ACM)g(SIGIR)h(Confer)o(ence)p Fc(,)c(1993,)j(pp.)g (126\261135.)-67 954 y([1)o(1])21 b(R.O.)12 b(Duda)f(and)g(P)l(.E.)h (Hart.)28 b Fb(Pattern)11 b(Classi\256cation)f(and)h(Scene)15 999 y(Analysis.)h Fc(John)c(W)o(iley)h(&)h(Sons,)e(NY)-5 b(,)10 b(1973.)-68 1050 y([12])21 b(B.)11 b(Everitt.)22 b Fb(Cluster)10 b(Analysis.)21 b Fc(Heinemann)9 b(Educational,)h(Lon-) 15 1095 y(don,)f(1974.)-68 1146 y([13])21 b(C.)12 b(Faloutsos)e(and)h (D.W)m(.)h(Oard.)27 b(A)11 b(Survey)g(of)h(Information)h(Re-)15 1192 y(trieval)7 b(and)f(Filtering)i(Methods.)g(T)m(echnical)e(Report)g (CS-TR-3514,)15 1237 y(Department)13 b(of)h(Computer)g(Science,)f (University)h(of)g(Maryland,)15 1283 y(College)8 b(Park,)i(1995.)-68 1333 y([14])21 b(T)m(.)11 b(Feder)e(and)g(D.H.)i(Greene.)17 b(Optimal)11 b(Algorithms)f(for)h(Approx-)15 1379 y(imate)j (Clustering.)36 b Fb(In)14 b(Pr)o(oceeding)o(s)d(of)j(the)f(T)m (wentieth)h(Annual)15 1425 y(Symposium)7 b(on)i(Theory)e(of)j (Computing)p Fc(,)e(1988,)h(pp.)g(434\261444.)-68 1475 y([15])21 b(R.J.)6 b(Fowler)o(,)h(M.S.)g(Paterson,)f(and)g(S.L.)g(T)m (animoto.)j(Optimal)e(pack-)15 1521 y(ing)j(and)f(covering)h(in)g(the)g (plane)g(are)g(NP-complete.)18 b Fb(Information)15 1566 y(Pr)o(ocessing)6 b(Letters,)i Fc(12)h(\(1981\),)g(pp.)g(133\261137.) -68 1617 y([16])21 b(W)m(.)7 b(Frakes)e(and)g(R.)i(Baeza-Y)l(ates,)f (editors.)i Fb(Information)e(Retrieval:)15 1662 y(Data)j(Structur)o(es) e(and)h(Algorithms.)13 b Fc(Prentice-Hall,)d(1992.)-68 1713 y([17])21 b(M.R.)9 b(Garey)e(and)h(D.S.)g(Johnson,)h Fb(Computers)e(and)g(Intractability:)15 1758 y(A)k(Guide)f(to)i(the)f (Theory)e(of)i(NP-Completeness)p Fc(,)21 b(W)m(.H.)12 b(Freeman)15 1804 y(and)c(Company)n(,)g(1979.)-68 1854 y([18])21 b(M.)11 b(Goemans)e(and)h(J.)g(Kleinber)o(g.)20 b(An)11 b(improved)f(approximation)15 1900 y(ratio)j(for)h(the)e (minimum)h(latency)f(problem.)30 b Fb(In)13 b(Pr)o(oceedings)c(of)15 1946 y(the)h(Seventh)f(ACM-SIAM)i(Symposium)e(on)h(Discr)o(ete)f (Algorithms)p Fc(,)15 1991 y(1996,)f(pp.)h(152\261157.)-68 2042 y([19])21 b(T)m(.E.)12 b(Gonzalez.)24 b(Clustering)11 b(to)h(minimize)g(the)f(maximum)g(inter)o(-)15 2087 y(cluster)h (distance.)26 b Fb(Theor)o(etical)10 b(Computer)h(Science,)g Fc(38)h(\(1985\),)15 2133 y(pp.)d(293\261306.)-68 2184 y([20])21 b(J.A.)9 b(Hartigan.)j Fb(Clustering)c(Algorithms.)k Fc(W)o(iley)n(,)c(New)h(Y)l(ork,)g(NY)-5 b(,)15 2229 y(1975.)-68 2280 y([21])21 b(D.)12 b(Hochbaum.)25 b(V)l(arious)11 b(Notions)g(of)h(Approximations:)17 b(Good,)15 2325 y(Better)o(,)11 b(Best,)f(and)f(More.)18 b(In:)d(D.S.)10 b(Hochbaum,)f(editor)o(,)h Fb(Appr)o(ox-)15 2371 y(imation)g(Algorithms)g(for)f(NP-Har)o(d)g(Pr)o (oblems)p Fc(.)g(PWS)h(Publishing)15 2417 y(Company)n(,)d(1996.)-68 2467 y([22])21 b(D.S.)c(Hochbaum)e(and)g(W)m(.)i(Maas.)50 b(Approximation)16 b(Schemes)15 2513 y(for)10 b(Covering)e(and)g (Packing)g(Problems)g(in)i(Image)e(Processing)g(and)15 2558 y(VLSI.)14 b Fb(Journal)7 b(of)j(the)f(ACM)p Fc(,)g(32)g (\(1985\),)g(pp.)g(130\261135.)-68 2609 y([23])21 b(D.S.)10 b(Hochbaum)e(and)h(D.B.)i(Shmoys.)16 b(A)10 b(best)f(possible)g (heuristic)15 2654 y(for)14 b(the)g Fa(k)q Fc(-center)g(problem.)36 b Fb(Mathematics)13 b(of)i(Operations)d(Re-)15 2700 y(sear)o(ch,)7 b Fc(10)i(\(1985\),)g(pp.)g(180\261184.)1031 -33 y([24])21 b(D.S.)10 b(Hochbaum)c(and)i(D.B.)h(Shmoys.)i(A)e(uni\256ed)e(approach) g(to)h(ap-)1114 12 y(proximation)j(algorithms)g(for)g(bottleneck)e (problems.)21 b Fb(Journal)9 b(of)1114 58 y(the)g(ACM,)h Fc(33)f(\(1986\),)g(pp.)g(533\261550.)1031 103 y([25])21 b(S.)11 b(Irani)f(and)f(A.)h(Karlin.)18 b(Online)10 b(Computation.)16 b(In:)e(D.S.)d(Hoch-)1114 149 y(baum,)g(editor)o(,)h Fb(Appr)o(oximation)d(Algorithms)h(for)g(NP-Har)o(d)g(Pr)o(ob-)1114 195 y(lems)p Fc(.)g(PWS)f(Publishing)f(Company)n(,)f(1996.)1031 240 y([26])21 b(N.)11 b(Jardine)e(and)g(C.J.)h(van)f(Rijsber)o(gen.)17 b(The)9 b(Use)g(of)h(Hierarchical)1114 286 y(Clustering)e(in)g (Information)g(Retrieval.)j Fb(Information)d(Storage)e(and)1114 332 y(Retrieval)p Fc(,)j(7)g(\(1971\),)g(pp.)g(217\261240.)1031 377 y([27])21 b(A.K.)12 b(Jain)e(and)g(R.C.)i(Dubes.)20 b Fb(Algorithms)11 b(for)f(Clustering)g(Data.)1114 423 y Fc(Prentice-Hall,)g(NJ,)f(1988.)1031 469 y([28])21 b(O.)12 b(Kariv)f(and)f(S.L.)h(Hakimi.)22 b(An)11 b(algorithmic)g (approach)e(to)i(net-)1114 514 y(work)f(location)f(problems,)g(part)h (I:)g(the)f Fa(p)p Fc(-centers)g(problem.)15 b Fb(SIAM)1114 560 y(Journal)8 b(of)h(Applied)g(Mathematics,)g Fc(37)f(\(1979\),)i (pp.)f(513\261538.)1031 606 y([29])21 b(N.)13 b(Megiddo)e(and)f(K.J.)j (Supowit.)26 b(On)11 b(the)h(complexity)f(of)h(some)1114 651 y(common)d(geometric)h(problems.)17 b Fb(SIAM)10 b(Journal)e(on)i(Computing,)1114 697 y Fc(13)f(\(1984\),)g(pp.)g (182\261196.)1031 743 y([30])21 b(S.G.)13 b(Mentzer)n(.)28 b(Lower)11 b(bounds)f(on)i(metric)h Fa(k)q Fc(-center)f(problems.)1114 788 y(Manuscript,)d(1988.)1031 834 y([31])21 b(R.)c(Motwani,)i(S.)d (Phillips)h(and)f(E.)g(T)m(orng.)50 b(Non-Clairvoyant)1114 880 y(Scheduling,)21 b(In)11 b Fb(Pr)o(oceeding)o(s)d(of)j(the)f (Fourth)g(ACM-SIAM)h(Sym-)1114 925 y(posium)d(on)f(Discr)o(ete)g (Algorithms)p Fc(,)g(1993,)h(pp.)g(422\261431.)h(See)e(also:)1114 971 y Fb(Theor)o(etical)h(Computer)f(Science,)h Fc(130)h(\(1994\),)g (pp.)g(17\26147.)1031 1017 y([32])21 b(E.)12 b(Omiecinski)f(and)g(P)l (.)h(Scheuermann.)24 b(A)11 b(Global)h(Approach)e(to)1114 1062 y(Record)g(Clustering)h(and)e(File)i(Or)o(ganization.)21 b(In)11 b Fb(Pr)o(oceedings)c(of)1114 1108 y(the)13 b(Thir)o(d)e (BCS-ACM)h(Symposium)f(on)g(Resear)o(ch)f(and)h(Develop-)1114 1154 y(ment)e(in)h(Information)f(Retrieval,)f Fc(1984,)h(pp.)g (201\261219.)1031 1199 y([33])21 b(J.)12 b(Pach)f(and)g(P)l(.K.)h (Agarwal.)28 b Fb(Combinatorial)11 b(Geometry)n(.)25 b Fc(John)1114 1245 y(W)o(iley)10 b(&)f(Sons,)f(New)h(Y)l(ork,)h(NY)-5 b(,)10 b(1995.)1031 1291 y([34])21 b(E.)d(Rasmussen.)48 b(Clustering)17 b(Algorithms.)52 b(Chapter)16 b(16)h(in:)1114 1336 y(W)m(.)7 b(Frakes)f(and)f(R.)i(Baeza-Y)l(ates,)f(editors,)h Fb(Information)g(Retrieval:)1114 1382 y(Data)14 b(Structur)o(es)e(and)h (Algorithms,)i Fc(Prentice-Hall,)h(Englewood)1114 1428 y(Clif)o(fs,)c(NJ,)d(1992.)1031 1473 y([35])21 b(C.J.)13 b(van)f(Rijsber)o(gen.)30 b Fb(Information)12 b(Retrieval.)30 b Fc(Butterworths,)1114 1519 y(London,)8 b(1979.)1031 1565 y([36])21 b(C.)14 b(Rogers.)31 b(A)13 b(note)g(on)f(coverings.)31 b Fb(Mathematika,)13 b Fc(4)g(\(1957\),)1114 1610 y(pp.)c(1)o(1\2616.) 1031 1656 y([37])21 b(G.)16 b(Salton.)40 b Fb(Automatic)15 b(T)m(ext)e(Pr)o(ocessing.)38 b Fc(Addison-W)m(esley)n(,)1114 1702 y(Reading,)9 b(MA,)g(1989.)1031 1747 y([38])21 b(G.)10 b(Salton)e(and)g(M.J.)h(McGill.)15 b Fb(Intr)o(oduction)7 b(to)i(Modern)e(Informa-)1114 1793 y(tion)h(Retrieval.)i Fc(McGraw-Hill)g(Book)c(Company)n(,)h(New)g(Y)l(ork,)i(NY)-5 b(,)1114 1839 y(1983.)1031 1884 y([39])21 b(P)l(.)10 b(W)o(illett.)19 b(Recent)9 b(T)o(rends)g(in)h(Hierarchical)g(Document) e(Cluster)o(-)1114 1930 y(ing:)15 b(A)10 b(Critical)i(Review)n(.)18 b Fb(Information)10 b(Pr)o(ocessing)d(&)j(Manage-)1114 1976 y(ment,)g Fc(24)e(\(1988\),)i(pp.)f(577\261597.)1031 2021 y([40])21 b(I.H.)12 b(W)o(itten,)e(A.)h(Mof)o(fat,)g(and)e(T)m (.C.)i(Bell.)17 b Fb(Managing)9 b(Gigabytes:)1114 2067 y(Compr)o(essing)c(and)h(Indexing)h(Documents)f(and)g(Images.)k Fc(V)l(an)c(Nos-)1114 2113 y(trand)k(Reinhold,)e(New)h(Y)l(ork,)h(NY)-5 b(,)10 b(1994.)p eop %%Trailer end userdict /end-hook known{end-hook}if %%EOF