Algorithms and Data Structures : 9th International Workshop, WADS 2005, Waterloo, Canada, August 15-17, 2005, Proceedings

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.