Data Structures And Efficient Algorithms: Final Report On The Dfg Special Joint Initiative

Lecture Notes in Computer Science Edited by G. Goos and J. Hartmanis Advisory Board: Wo Brauer D. Gries J. Stoer 594 B. Monien Th. Ottmann (Eds.) Data Structures and Efficient Algorithms Final Report on the DFG Special Joint Initiative Springer-Verlag Berlin Heidelberg NewYork London Paris Tokyo Hong Kong Barcelona Budapest Series Editors Gerhard Goos Universit~it Karlsruhe Postfach 69 80 Vincenz-Priessnitz-Strage 1 W-7500 Karlsruhe, FRG Juris Hartmanis Department of Computer Science Cornell University 5149 Upson Hall Ithaca, NY 14853, USA Volume Editors Burkhard Monien Fachbereich Mathematik/Informatik, Universit~tt-Gesamthochschule Paderborn Postfach 1621, W-4790 Paderborn, FRG Thomas Ottmann Institut ftir Informatik, Universit~it Freiburg Rheinstr. 10-12, W-7800 Freiburg i. Br., FRG CR Subject Classification (1991): F.2.2, 1.3.5, E.5, G.1.0, H.2.8, 1.2.1, G.2.2, C.2.1 ISBN 3-540-55488-2 Springer-Verlag Berlin Heidelberg New York ISBN 0-387-55488-2 Springer-Verlag New York Berlin Heidelberg This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, re-use of illustrations, recitation, broadcasting, reproduction on microfilms or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer-Verlag. Violations are liable for prosecution under the German Copyright Law. 9 Springer-Verlag Berlin Heidelberg 1992 Printed in Germany Typesetting: Camera ready by author/editor Printing and binding: Druckhaus Beltz, Hemsbach/Bergstr. 45/3140-543210 - Printed on acid-free paper Preface The German Science Foundation (Deutsche Forschungsgemeinschaft, DFG) started a special joint intiative (Schwerpunktprogramm) entitled "Datenstruktur ~ und effiziente A1gorithmen" in 1986. The aim of the initiative was to encourage collaborative research on algorithms, a central concept in computer science. For a period of five years about a dozen projects were funded with an emphasis on algorithms and data structures for geometric problems, on the one hand, and parallel and distributed algorithms, on the other. The first group of projects addressed research on fundamental data structures, computational geometry, graph algorithms, computer graphics, and spatial databases. The second group of projects centered around the following problems: the design of parallel architectures and routing strategies, simulation of parallel machines, and the design of distributed algorithms for solving difficult problems. The initiative has proven to be very successfu