Algorithms and Data Structures

The papers in this volume were presented at the 9th Workshop on Algorithms and Data Structures (WADS 2005). The workshop took place during August 15 - 17, 2005, at the University of Waterloo, Waterloo, Canada. The workshop alternateswith the ScandinavianWorkshopon Algorithm Theory(SWAT), c- tinuing the traditionof SWAT and WADS startingwith SWAT 1988and WADS 1989. From 90 submissions, the Program Committee selected 37 papers for p- sentation at the workshop. In addition, invited lectures were given by the f- lowing distinguished researchers: Allan Borodin and Max J. Egenhofer. OnbehalfoftheProgramCommittee, wewouldliketoexpressoursincere- preciation to the many persons whose e?ort contributed to making WADS 2005 a success. These include the invited speakers, members of the ste- ing and ProgramCommittees, the authors who submitted papers, and the many referees who assisted the ProgramCommittee. We are indebted to Robert Kane forinstallingandmodifyingthesubmissionsoftware, maintainingthesubmission server and interacting with authors as well as for helping with the preparation of the program. August 2005 Frank Dehne, Alejandro Lop ´ ez-Ortiz, and Jorg-R ] u ]diger Sack WADS Organization Organizing Institutions Steering Committee Frank Dehne Carleton University, Canada Ian Munro University of Waterloo, Canada J] org-Rudig ] er Sack Carleton University, Canada Roberto Tamassia Brown University, Canada Program Co-chairs Frank Dehne Carleton University, Canada Alejandro Lop ´ ez-Ortiz University of Waterloo, Canada J] org-Rudig ] er Sack Carleton University, Canada Conference Chair Alejandro Lop ´ ez-Ortiz University of Waterloo, Canada Program Committee Pankaj Agarwal Duke University, USA Michael Atkinson University of Otago, New Zealand Gill Barequet Technion, Israel Mark de Berg Tech.