Algorithms and Computation

This volume contains the proceedings of the 15th Annual International Sym- sium on Algorithms and Computation (ISAAC 2004), held in Hong Kong, 20-22 December, 2004. In the past, it has been held in Tokyo (1990), Taipei (1991), Nagoya (1992), Hong Kong (1993), Beijing (1994), Cairns (1995), Osaka (1996), Singapore (1997), Taejon (1998), Chennai (1999), Taipei (2000), Christchurch (2001), Vancouver (2002), and Kyoto (2003). ISAAC is an annual international symposium that covers a wide range of topics,namelyalgorithmsandcomputation.Themainpurposeofthesymposium is to provide a forum for researchers working in the active research community of algorithms and the theory of computation to present and exchange new ideas. In response to our call for papers we received 226 submissions. The task of selectingthepapersinthisvolumewasdonebyourprogramcommitteeandother referees. After a thorough review process the committee selected 76 papers, the decisions being based on originality and relevance to the ?eld of algorithms and computation. We hope all accepted papers will eventually appear in scienti?c journals in a more polished form. Two special issues, one of Algorithmica and one of the International Journal of Computational Geometry and Applications, with selected papers from ISAAC 2004 are in preparation. ThebeststudentpaperawardwillbegivenforGeometricoptimizationpr- lems over sliding windows by Bashir S. Sadjad and Timothy M. Chan from the University of Waterloo. Two eminent invited speakers, Prof. Erik D. Demaine, MIT, and Prof. David M. Mount, University of Maryland, also contributed to this volume.