Algorithms and Computation

This volume contains the papers selected for presentation at the Thirteenth - nual International Symposium on Algorithms and Computation (ISAAC 2002) tobeheldinVancouver,CanadaonNovember21-23,2002.Thisisthe?rsttime thatISAAChasventuredintoNorthAmerica,asitistraditionallyheldinthe Asia-Paci?c region. ISAAC is an annual international symposium that covers the very broad areas of algorithms and computing in general. The scope of this symposium - cludes both theoretical and applied research from these ?elds. The main aim of the symposium is to promote the exchange of ideas in this active research community. The speci?c themes targeted for ISAAC 2002 were Computational Geometry,AlgorithmsandDataStructures,ApproximationAlgorithms,Ran- mizedAlgorithms,GraphDrawingandGraphAlgorithms,Combinatorial- timization,ComputationalBiology,ComputationalFinance,Cryptography,and Parallel and Distributed Computing. Inresponsetoourcallforpapers,wereceivedcloseto160submissions.The challenging task of selecting the papers for presentation was performed by the membersofourprogramcommittee,theirsupportsta?,andreferees.Allof them deserve special thanks for their hard work in the di?cult task of selecting amere54papersfromthehigh-qualitysubmissions. Unfortunately,duetothe timeconstraintsimposedbyathree-dayconference,wewereforcedtoturn away many excellent papers. John Iacono will receive the traditionalbestpaperaward for his paper entitled KeyIndependentOptimality. Our three invited speakers are Luc Devroye from McGill University who will speak onRandomTries,J'anos Pach from New York University who will speak onMonotoneDrawingsofPlanarGraphs,andNic- las Pippenger from the University of British Columbia who will speak on the ExpectedAcceptanceCountsforFiniteAutomatawithAlmostUniformInput. No conference can succeed without exceptional local organization. For the often overlooked and thankless task of ?nding a suitable venue and banquet location,dealingwiththelogisticsofregistration,organizinglunchesandco?ee, etc.,wewouldliketothankthetheorganizingcommittee,NadjaRence,andOlga Stachova for all their e?orts above and beyond the call of duty. We thank our sponsorsSimonFraserUniversity,thePaci?cInstituteofMathematicalSciences, the institute for Mathematics of Information Technology and Complex Systems, andBajaiInc.fortheirgeneroussupport.Finally,wethankalltheauthorsand participants. We hope this edition of ISAAC will be a success.