\providecommand{\Prefacedir}{.}% ===> this file was generated automatically by noweave --- better not edit it
\providecommand{\Prefacepreamble}{%
\input vorspann

\begin{document}
}
\Prefacepreamble



\chapter*{Preface}
%\pagenumbering{roman}

\newcommand{\citetextbooks}{%
\cite{Aho-Hopcroft-Ullman2,%
Berg-Kreveld-Overmars-Schwarzkopf:book,%
Boissonnat-Yvinec:book,%
Cormen-Leiserson-Rivest,%
Kingston,%
Klein:book,%
Nievergelt-Hinrichs,%
Mehlhorn,%
ORourke,%
Ottmann-Widmayer,%
Preparata-Shamos,%
Sedgew,%
Tarjan,%
VWyk,%
Wood%
}%
}

\newcommand{\citeCCbooks}{%
\cite{%Gorlen-Orlow-Plexico,%
Lippmann-Jajoie,%
Murray,%
Stroustrup%
}%
}

\label{Preface}



LEDA (\underline{L}ibrary of \underline{E}fficient \underline{D}ata Types
and \underline{A}lgorithms) is a \CC\ library of combinatorial and geometric data
types and algorithms. 
It offers
\begin{description}
\item[Data Types,] such as random sources, stacks, queues, maps, lists, 
sets, partitions, dictionaries, sorted sequences, point sets, interval sets,
\ldots, 
\item[Number Types,] such as integers, rationals, 
bigfloats, algebraic numbers, and linear algebra.
\item[Graphs and Supporting Data Structures,] such as node- and edge-arrays,
node- and edge-maps, node priority queues and node partitions, iteration statements for nodes and
edges, \ldots, 
\item[Graph Algorithms,] such as shortest paths, spanning trees, 
flows, matchings, components,
planarity, planar embedding, \ldots,
\item[Geometric Objects,] such as points, lines, segments, rays, planes, circles, polygons,
\ldots,
\item[Geometric Algorithms,] such as convex hulls, triangulations, Delaunay
diagrams, Voronoi diagrams, segment intersection, \ldots, and 
\item[Graphical Input and Output.]
\end{description}
The modules just mentioned cover a considerable part of combinatorial and
geometric computing as treated in courses and textbooks on data structures and 
algorithms~\citetextbooks.


From a user's point of view, 
LEDA is a platform for combinatorial and geometric
computing. It provides \emph{algorithmic intelligence} for a wide range of
applications. 
It eases a programmer's life by providing
powerful and easy-to-use data types and algorithms which can be used as
building blocks in larger programs.
It has been used in such diverse areas as
code optimization, VLSI design, robot motion planning, traffic scheduling, 
machine learning and computational biology. The LEDA system is installed at
more than 1500 sites. %\smallskip

We started the LEDA project in the fall of 1988. The project grew out 
of several considerations.
\begin{itemize}
\item We had always felt that a significant fraction of the 
research done in the algorithms area was
  eminently practical. However, only a small part of it was actually used.
  We frequently heard from our former students that the 
intellectual and programming effort needed to 
  implement an advanced data structure or algorithm is too large to be
  cost-effective. We concluded that \emph{algorithms research must include  
implementation if the field wants to have maximum impact}. 
\item We surveyed the amount of code reuse in our own small and tightly
connected research group. We found several implementations
  of the same balanced tree data structure. Thus there was constant 
reinvention of the wheel even within our own small group. 
\item Many of our students had implemented algorithms for their 
master's thesis.
  Work invested by these students was usually lost after the students
  graduated. We had no depository for implementations.
\item The specifications of advanced data types which we gave 
in class and which
  we found in text books, including the one written by one of the authors,
  were incomplete and not sufficiently abstract to allow to combine
implementations easily.  They contained phrases of the
  form: ``Given a pointer to a node in the heap its priority can be decreased
  in constant amortized time". Phrases of this kind
 imply that a user of a data structure
  has to know its implementation. As a consequence combining
  implementations is a non-trivial task. We performed the following
experiment. We asked two groups of students to read the chapters on priority
queues and shortest path algorithms in a standard text book, respectively, and
to implement the part they had read. The two parts would not fit, because the
specifications were incomplete and not sufficiently abstract.
\end{itemize}
We started the LEDA project to overcome these shortcomings by creating
a platform for combinatorial and geometric computing. 
\emph{LEDA should 
contain the major findings of the algorithms community in a form that makes
them directly accessible to non-experts having only limited knowledge of
the area}. In this way we hoped to reduce the gap between research and 
application.%\smallskip

The LEDA system is available from the LEDA web-site.
\begin{center}
{\tt http://www.mpi-sb.mpg.de/LEDA/leda.html}\end{center}

\noindent
A commercial version of LEDA is available from Algorithmic Solutions Software
GmbH. 
\begin{center}
{\tt http://www.algorithmic-solutions.de}
\end{center}

LEDA can be used with almost any \CC\ compiler and is available for 
UNIX and WINDOWS systems. The LEDA mailing list (see the LEDA web page)
facilitates the
exchange of information between LEDA users.

\ignore{
Our design goals for LEDA were:
\emph{Ease of Use}, 
\emph{Comprehensiveness},
\emph{Extendibility},
\emph{Correctness}, and
\emph{Efficiency}
}

\ignore{
We now give a brief historical account of the project. As mentioned already,
we started it in the fall of 1988. We spent the first 6 months of the project
on specifications and on selecting our implementation language. Our test cases 
were priority queues, dictionaries, partitions, and algorithms for shortest
paths and minimum spanning trees. We came up with the item concept as
an abstraction of the notion ``pointer into a data structure". It worked
successfully for the three data types mentioned above and we are now using 
it for most data types in LEDA. Concurrently with searching for the correct
specifications we investigated several languages for their suitability
as our implementation platform. We looked at Smalltalk, Modula, Ada, Eiffel, 
and \CC. We wanted a language that supported abstract data types and type
parameters (poly-morphism) and that was widely available. We wrote sample
programs in each language. Based on our experiences we selected \CC\ because
of its flexibility, expressive power, and availability. We are even more
convinced now that our choice was the right one. A first publication about
LEDA appeared in MFCS 1989 (Lecture Note in Computer Science, Volume???)
and ICALP 1990 (Lecture Notes in Computer Science, Volume???). Stefan
N\"aher became the head of the LEDA project and he is the main designer 
and implementer of LEDA.

In the second half of 1989 and during 1990 Stefan N\"aher implemented a 
first version of the combinatorial part (= data structures and graph
algorithms) of LEDA (Version 1.0).

Version 2.0 (June 1992) allowed to use arbitrary data types (not only 
pointer and simple types) as actual type parameters of parameterized data
types. It included a first implementation of the two-dimensional geometry
library (libP) and an interface to the X-Window system for graphical input
and output (data type window).

Version 3.0 (February 1993) switched to the template mechanism to realize
parameterized data types (macro substitution was used before), introduced 
implementation parameters that allow to choose between different 
implementations, extended the LEDA memory management system to user-defined
classes, and further improved the efficiency of many data types and 
algorithms.

Version 3.1 (January 1995) provides a more efficient graph data type and 
contains new data types (arbitrary precision number types and basic geometric
objects) used for robust implementations of geometric algorithms.

LEDA was first distributed in the summer of 1990. Its user community has grown
to a respectable size by now. Industrial use started in 1994 and LEDA 
Software GmbH was founded in early 1995. It will maintain LEDA and further 
develop it according to the needs of the LEDA users.

LEDA will also stay an active research project for quite some time. Two
main areas of our current research are geometric algorithms and the exact
and approximate solution of NP-complete problems.

The implementation of geometric algorithms is notoriously difficult due to
the degeneracy and the precision problem. Most algorithms in the
computational geometry literature are formulated for inputs in so-called
general position and assume exact real arithmetic. However, real-life 
inputs are usually not in general position (= the degeneracy problem) and
floating point arithmetic is only a crude approximation of real arithmetic
(= the precision problem). Version 3.1 addresses both issues. It offers support
for exact computation and some of the basic geometric algorithms can now handle 
arbitrary inputs. However, many research problems still remain.


CGAL, write something about it.

LEDA offers a wide range of graph and network algorithms. However, only 
problems solvable in polynomial time are currently addressed and no support
for NP-complete problems is given. We have started to investigate exact
and approximate algorithms for some NP-complete problems, e.g., graph
layout and balanced cuts.

}

\smallskip

\emph{This book provides a comprehensive treatment of the LEDA system and its use}.
We treat the architecture of the system, we
discuss
the functionality of the data types and algorithms available in the system, 
we discuss the implementation of many modules of the system, and we give 
many
examples for the use of LEDA. We believe 
that the book is useful to five types of readers: readers with a general
interest in combinatorial and geometric computing, casual users of LEDA,
intensive users of LEDA, library designers and software engineers, and
students taking an algorithms course.
\ignore{
The book can also be used as a companion to traditional data structure and
algorithm books, to books on object oriented design, and to \CC\ books.
It is a companion to algorithms books as LEDA
turns algorithms into programs, it is a companion to books on
object-oriented software construction as it describes the construction
of a successful software library, and it is a companion to \CC\  books as it 
shows how the features of \CC\ can be used for library construction.}
\smallskip



The book is structured into fourteen chapters. \smallskip
\ignore{
The five chapters have the headers overview,
foundations, a tour of LEDA, case studies, and implementation. 
}

Chapter 1, Introduction, introduces the reader 
to the use of LEDA and gives an overview
of the system and our design goals.  %\smallskip

Chapter 2, Foundations, discusses the basic concepts 
 of the LEDA system. It defines 
key concepts, such as type, object, variable, value, item, copy, linear
order, and running time, and it relates these concepts to \CC. We 
recommend that you 
read this chapter quickly and come back to it as needed. The
detailed knowledge of this chapter is a prerequisite for the intensive use
of LEDA. The casual user should be able to satisfy his needs by simply
modifying example programs given in the book. The chapter draws upon
several sources: object-oriented programming, abstract data types, and
efficient algorithms. It lays out many of our major design decisions which 
we call LEDA axioms.%\smallskip

Chapters 3 to 12 form  the bulk of the book. They constitute
a guided tour of
LEDA. We discuss numbers, basic data types, advanced data types, graphs, graph
algorithms, embedded graphs, geometry kernels, geometry algorithms,
windows, and graphwins. In each chapter we introduce the 
functionality of the available 
data types and algorithms, illustrate their use, and give the implementation 
of some of them. %\smallskip

Chapter 13, Implementation, discusses the core part of LEDA,
\ignore{some basic concepts in the implementation
of LEDA which are common to all preceding chapters,} e.g.,  
the implementation of parameterized data types, implementation parameters,
memory management, and iteration. %\smallskip

Chapter 14, Documentation, discusses the principles underlying the documentation
of LEDA and the tools supporting it.\smallskip

The book can be read without having the LEDA system installed. However, access
to the LEDA system will greatly increase the \emph{joy of reading}. 
\ignore{Section~\ref{Intro: installation} gives information about how to obtain and
install LEDA.}
The demo directory
of the LEDA system contains numerous programs that allow the reader to exercise
the algorithms discussed in the book. The demos give a feeling for the
functionality and the efficiency of the algorithms, and in a few cases even 
animate them. 
 

%\smallskip

The book can be read from cover to cover, but we expect few readers to do it.
We wrote the book such that, although the chapters depend on each other as
shown in Figure~\ref{Preface: dependency graph}, 
most chapters can be read independently of
each other. We sometimes even repeat material in order to allow for
independent reading. %\smallskip



{
\begin{figure}[t]
\begin{center}
%\epsfysize=\textwidth
%\epsffile{book_structure.ps}  
\input \Prefacedir/book_structure
\end{center}
\def\thefigure{A}
\caption{The dependency graph between the chapters. A 
dashed arrow means that partial
knowledge is required and a solid arrow means that extensive knowledge is
required. Introduction and Foundations should be read before all other chapters
and Implementation and Documentation can be read independently from the
other chapters. }
\label{Preface: dependency graph}
\end{figure} 
}




\emph{All readers} 
should start with the chapters Introduction and Foundations. 
In these chapters we give an overview of LEDA and introduce the
basic concepts of LEDA.
We suggest that you read the chapter on foundations quickly and come back
to it as needed. 

The chapter on basic data types (list, stacks, queues, array, random number
generators, and strings) should also be read by every reader. The 
basic data types
are ubiquitous in the book.%\smallskip

Having read the chapters Introduction, Foundations and Basic Data Types, 
the reader may
take different paths depending on interest.%\smallskip

\emph{Casual users of LEDA} should read the chapters treating their
domain of interest, and \emph{intensive users of LEDA} should also read the
chapter on implementation.%\smallskip


\emph{Readers interested in Data Structures} should read the chapters on advanced data types, on implementation,
and some of the sections of the chapter on geometric algorithms. The chapter on
advanced data types treats dictionaries, search trees and hashing, priority
queues, partitions, and sorted sequences, and the chapter on implementation
discusses, among other things, the realization of
parameterized data types.
The different sections in the chapter on advanced data types can be read
independently. In the chapter on geometric algorithms we recommend 
the section on dynamic
Delaunay triangulations; some knowledge of
graphs and computational geometry is required to read it.%\smallskip




\emph{Readers interested in Graphs and Graph Algorithms} should continue with
the chapter on
graphs. From there one can proceed to either the chapter on
graph algorithms or the chapter on embedded graphs. Within the chapter on graph
algorithms the sections can be read independently. However, the chapter on
embedded graphs must be read from front to rear. Some knowledge of priority
queues and partitions is required for some of the sections on graph
algorithms. %\smallskip

\emph{Readers interested in Computational Geometry} 
can continue with either the chapter on graphs or the
chapter on geometry kernels. Both chapter are a prerequisite for the chapter on
geometric algorithms. The chapter on geometry kernels requires partial
knowledge of the chapter on numbers.
The chapter on geometric algorithms splits into two parts
that can be read independently. The first part is on convex hulls, Delaunay
triangulations, and Voronoi diagrams, and the second part is on line segment
intersection and polygons. 

Geometric algorithms are dull without graphical input and output. 
The required knowledge
is provided by the chapter on windows. The section on the Voronoi demo
in the chapter on
geometric algorithms gives a comprehensive example for the interplay between
geometric data types and algorithms and the window class.  %\smallskip

\emph{Readers interested in Algorithm Animation} 
should read the chapter on windows and graphwin, the section on
animating strongly connected components in the chapter on graph algorithms,
the section on the Voronoi demo in the geometric algorithms chapter, 
and study the many programs in the xlman subdirectory of the demo directory.
%\smallskip

\emph{Readers interested in Software Libraries} 
should read the chapters on foundations, on implementation,
and on documentation. They should also study some other chapters at their
own choice. %\smallskip

\emph{Readers interested in developing a LEDA Extension Package}
should read the chapters
on implementation and documentation in addition to the chapters related to
their domain of algorithmic interest.\smallskip

For all the algorithms
discussed in the book, we also derive the required theory and give the proof of
correctness. However, sometimes our theoretical treatment is quite compact
and tailored to our specific needs. We refer the reader to the
textbooks~\cite{Aho-Hopcroft-Ullman2,Mehlhorn,Tarjan,Cormen-Leiserson-Rivest,ORourke,Wood,Sedgew,Kingston,VWyk,Nievergelt-Hinrichs,Preparata-Shamos,Boissonnat-Yvinec:book,Berg-Kreveld-Overmars-Schwarzkopf:book}
for a more comprehensive view. 
%\smallskip

\hyphenation{know-ledge}

LEDA is implemented in \CC\ and we expect our readers to have some knowledge of
it. We are quite conservative in our use of \CC\ and hence a basic knowledge of
the language suffices for most parts of the book. The required concepts include
classes, objects, templates, member functions, and non-member functions and are
typically introduced in the first fifty 
pages of a \CC\ book~\citeCCbooks.
Only the chapter on implementation requires the reader
to know more advanced concepts like
inheritance and virtual functions.

\ignore{
\paragraph*{What this book is not:}
This book is not a textbook in data structures and algorithms, it is not a book
on object-oriented software construction, and it is not a book on 
\CC\  programming. We refer the reader to~\citetextbooks
for the design and analysis of algorithms, to 
\cite{Meyer:object-oriented-software},\dots, for object-oriented
software construction, and to \cite{Stroustrup,Gorlen-Orlow-Plexico,Murray}
for software development in \CC. However, this book can be used as a companion
to all books mentioned above: It is a companion to algorithms books as LEDA
turns algorithms to running software, it is a companion to books on
object-oriented software construction as it describes the construction
of a successful software library, and it is a companion to \CC\  books as it 
shows how the features of \CC\ can be used for library construction.
}




\ignore{
\paragraph*{How to use this book:}
This book is structured into five chapters and an appendix. The appendix 
contains the LEDA manual. The five chapters have the headers overview,
foundations, a tour of LEDA, case studies, and implementation. We believe 
that the book may be useful to five types of readers: readers with a general
interest in combinatorial and geometric computing, casual users of LEDA,
intensive users of LEDA, library designers and software engineers, and
students taking an algorithms course.

The overview chapter quickly surveys LEDA. It reviews the motivation, it
illustrates the use of LEDA by four examples, one each in data structures,
graphs, geometry, and graphics, it comments on the scope and efficiency.
This chapter is for everyone.

The foundations chapter discusses the basics of the LEDA system. It defines 
some key concepts, such as type, object, variable, value, item, copy, linear
order, and running time, and it relates these concepts to \CC. We 
recommend to read this chapter quickly and to come back to it as needed. The
detailed knowledge of this chapter is a prerequisite for the intensive use
of LEDA. The casual user should be able to satisfy his needs by simply
modifying example programs given in the book. The chapter draws upon
several sources: object-oriented programming, abstract data types, and
efficient algorithms. It lays out many of our major design decisions which 
we call LEDA axioms.

The third chapter is by far the largest. We tour LEDA. We discuss most of 
the data types and algorithms available in LEDA and illustrate their use by
small example programs. The programs are short but solve interesting problems.
They are meant to illustrate the versatility and elegance of LEDA and to
serve as starting points for more extensive programs. The sections and
subsections of this chapter can be read in almost any order. You should
however make sure that you have read the first paragraph of all sections 
containing the section you are interested in. For example, if you are
interested in section 3.1.8.4 read the introductory paragraphs of sections
3, 3.1, 3.1.8 first. They may contain pointers to prerequisites for section
3.1.8.4. We have also included pitfall sections and exercises. In the 
pitfall sections we discuss frequently made mistakes. The exercises 
suggest short programming tasks.

The case studies chapter contains four larger programs. We do matchings in
graphs, planarity testing, line segment intersection, and convex hulls in
arbitrary dimension\marginpar{check}. The purpose of this chapter is threefold.
Larger programs allow us to demonstrate the interplay of several LEDA
features, they allow us to demonstrate how programs should be documented, 
and they give more evidence of the expressive power of LEDA (since the 
programs are actually fairly short; it is the documentation which makes these
sections somewhat lengthy). We should mention that the two geometric
algorithms handle all inputs correctly. We recommend this chapter to the
intensive users of LEDA, and also to readers with a general interest in
combinatorial and geometric computing.

The implementation chapter discusses the inner workings of the LEDA system.
In particular, we treat the realization of parameterized data types, the use
of multiple inheritance for implementation parameters, memory management, the
realization of independent item types, documentation, and running time.
We also give complete implementations of priority queues and sorted sequences
to put everything together. This section is intended for the intensive user 
of LEDA, library designers, and software engineers.



\paragraph*{What this book is not:}
This book is not a textbook in data structures and algorithms, it is not a book
on object-oriented software construction, and it is not a book on 
\CC\  programming. We refer the reader to 
\cite{Aho-Hopcroft-Ullman2,Mehlhorn,Tarjan,Cormen-Leiserson-Rivest,ORourke,Wood,Sedgew,Kingston,VWyk,Nievergelt-Hinrichs} 
for the design and analysis of algorithms, to 
\cite{Meyer:object-oriented-software},\dots, for object-oriented
software construction, and to \cite{Stroustrup,Gorlen-Orlow-Plexico,Murray}
for software development in \CC. However, this book can be used as a companion
to all books mentioned above: It is a companion to algorithms books as LEDA
turns algorithms to running software, it is a companion to books on
object-oriented software construction as it describes the construction
of a successful software library, and it is a companion to \CC\  books as it 
shows how the features of \CC\ can be used for library construction.

\paragraph*{\LaTeX\ and WEB:}
This book is written using \LaTeX and WEB. Most readers have probably heard
of \TeX\ and \LaTeX, but only a few readers are probably familiar with WEB.
WEB is a system developed by D.E. Knuth \cite{Knuth:WEB} that allows to 
turn programs and their documentation into nicely typeset and integrated
documents. A WEB document consists of \LaTeX-sections and \CC\  sections. 
The \CC\  sections constitute the program and the \LaTeX-sections contain
the documentation. We use WEB to pretty-print \CC\  program fragments 
and to integrate \CC\  code and documentation of complete programs. We
explain the essentials of WEB when we first use it in a non-trivial way
in section \ref{The first WEB section}. At this point, we only mention that WEB
typesets some \CC\  operators in a more readable form:
$==$ is printed $\equiv$, \&\& is printed $\vee$, $^^7c ^^7c$ is printed $\wedge$, ! is
printed $\neg$, and != is printed $\neq$.

\paragraph*{Prerequisites:}
It is helpful to have some knowledge of \CC. You may read this book except 
for the chapter on implementation without knowing \CC. You will pick up 
a working knowledge of \CC\ bVT you will miss some fine points.
\cite{Stroustrup} and \cite{Gorlen} are excellent books on \CC.

}

\smallskip

The book contains many tables showing \emph{running times}. All running times were 
determined on an ULTRA-SPARC with
300 MHz CPU and 256 MByte main memory. LEDA and all programs were compiled with
CC (optimization flags -DLEDA\_CHECKING\_OFF and -O).


\smallskip

We welcome \emph{feedback} from our readers. A book of this length is certain 
to contain errors. If you find any errors or have other constructive
suggestions, we would appreciate hearing from you. Please send any comments 
concerning the book to
\begin{center}
{\tt ledabook@mpi-sb.mpg.de}
\end{center}
For comments concerning the system use
\begin{center}
{\tt ledares@mpi-sb.mpg.de}
\end{center}
or sign up for the LEDA discussion group. We will maintain a list of
corrections on the web. 

\smallskip

\hyphenation{Sonder-for-schungs-be-reich}
\hyphenation{Wei\3-kircher}

We received financial support from a number of sources. Of course, our home
institutions deserve to be mentioned first. We started LEDA at the
Universit\"at des Saarlandes in Saarbr\"ucken, in the winter 1990/1991 we both
moved to the Max-Planck-Institut f\"{u}r Informatik, also in 
Saarbr\"ucken, and in the fall of 1994 Stefan N\"aher moved to the 
Martin-Luther Universit\"at in Halle. Our work was also supported by the
Deutsche Forschungsgemeinschaft (Sonderforschungsbereich SFB 124 VLSI-Entwurf
und Parallelit\"at und Schwerpunktprogramm Effiziente Algorithmen und 
ihre Anwendungen), by the Bundesministerium f\"ur Forschung und Technologie
(project SOFTI), and by the European Community (projects ALCOM, ALCOM II,
ALCOM-IT, and CGAL).

Discussions with many colleagues, bug reports, experience reports (positive
and negative), suggestions for changes and extensions, and code contributions
helped to shape the project. 
Of course, we could not have built LEDA without the help of many other persons.
We want to thank 
David Alberts,
Ulrike Bartuschka,
Christoph Burnikel,
Ulrich Finkler,
Stefan Funke,
Evelyn Haak,
Jochen K\"onemann,
Ulrich Lauther, 
Andreas Luleich, 
Mathias Metzler,
Michael M\"uller, 
Michael Muth, 
Markus Neukirch,
Markus Paul,
Thomas Papanikolaou, 
Stefan Schirra,
Christian Schwarz, 
Michael Seel,
Jack Snoeyink,
Ken Thornton, 
Christian Uhrig,
Michael Wenzel, 
Joachim Ziegler,
Thomas Ziegler, 
and many others
for their contributions.

Special thanks go to Christian Uhrig, the chief officer
 of Algorithmic Solutions GmbH, to
Michael Seel, who is head of the LEDA-group at the MPI, and to Ulrich Lauther
from Siemens AG,
our first industrial user. 


\ignore{
single out: Christian Uhrig and Michael Seel

We want to mention Jean-Daniel Boissonnat,
Olivier Devillers, Harald Ganzinger, Thomas Lengauer, Jacques Loeckx, 
Mark Overmas, ???Papanikulaou, Jack Snoeyink, Ken Thornton, Athanasious
Tsakalidis, Reinhard Wilhelm\marginpar{wer noch?}. Special thanks go to
Ulrich Lauther, who was our first industrial user, for his many comments,
suggestions, and phone calls. The following persons worked on the project at
some point of time: Christoph Burnikel, Jochen Koenemanns, Stefan Schirra,
Christian Uhrig, \dots\marginpar{Stefan und Christian fragen}. Christian
Uhrig is managing the project since spring of 1994 and Stefan Schirra is
responsible for the future development in computational geometry.
}

Evelyn Haak typeset the book. Actually, she did a lot more. She made numerous
suggestions concerning the layout, she commented on the content, and she
suggested changes. Holger Blaar, Stefan Funke, Gunnar Klau, Volker Priebe, 
Michael Seel, Ren\'e Wei\3kircher, Mark Ziegelmann, and Joachim Ziegler
proof-read parts of the book. 
We want to thank them for their many constructive comments. Of course, all the
remaining errors are ours. 

Finally, we want to thank David Tranah from Cambridge University Press for his
support and patience.

\bigskip



\emph{We hope that you enjoy reading this book and that LEDA eases your life as a 
programmer.}

\vspace{4ex}

\parbox{4cm}{\begin{flushleft}
                {Stefan N\"aher\\
                 Halle, Germany\\
                 April, 1999}
               \end{flushleft}}\hfill
\parbox{4cm}{\begin{flushright}
                {Kurt Mehlhorn\\
                 Saarbr\"ucken, Germany\\
                 April, 1999}
               \end{flushright}}\hspace{\parindent}


\providecommand{\Prefacepostamble}
{
\bibliographystyle{alpha}
\bibliography{ref}

\end{document}
}

\Prefacepostamble
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
\nwfilename{Preface/Preface.nw}
