E-Book Overview
Algorithms are a central concept in computer science. The German Science Foundation (DFG) started a special joint initiative on data structures and efficient algorithms in 1986 with the aim of encouraging collaborative research on algorithms. 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. This volume contains 18 papers that are intended to give an impression of the achievements of this joint research initiative. The first group of papers addresses research on fundamental data structures, computational geometry, graph algorithms, computer graphics, and spatial databases. The second group of papers centers on 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.
E-Book Content
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